Pull to refresh
181.66

Algorithms *

Everything about algorithms

Show first
Rating limit
Level of difficulty

Data Science Digest — 21.04.21

Reading time 3 min
Views 982

Hi All,

I’m pleased to invite you all to enroll in the Lviv Data Science Summer School, to delve into advanced methods and tools of Data Science and Machine Learning, including such domains as CV, NLP, Healthcare, Social Network Analysis, and Urban Data Science. The courses are practice-oriented and are geared towards undergraduates, Ph.D. students, and young professionals (intermediate level). The studies begin July 19–30 and will be hosted online. Make sure to apply — Spots are running fast!

If you’re more used to getting updates every day, follow us on social media:

Telegram
Twitter
LinkedIn
Facebook

Regards,
Dmitry Spodarets.

Read more
Total votes 3: ↑2 and ↓1 +1
Comments 0

Data Science Digest — We Are Back

Reading time 5 min
Views 1.1K

Hi All,

I have some good news for you…

Data Science Digest is back! We’ve been “offline” for a while, but no worries — You’ll receive regular digest updates with top news and resources on AI/ML/DS every Wednesday, starting today.

If you’re more used to getting updates every day, follow us on social media:

Telegram - https://t.me/DataScienceDigest
Twitter - https://twitter.com/Data_Digest
LinkedIn - https://www.linkedin.com/company/data-science-digest/
Facebook - https://www.facebook.com/DataScienceDigest/

And finally, your feedback is very much appreciated. Feel free to share any ideas with me and the team, and we’ll do our best to make Data Science Digest a better place for all.

Regards,
Dmitry Spodarets.

Read more
Rating 0
Comments 0

Algebra of text. Examples

Reading time 5 min
Views 1.7K

The previous work from ref [1] describes the method of transforming a sign sequence into algebra through an example of a linguistic text. Two other examples of algebraic structuring of texts of a different nature are given to illustrate the method.

Читать далее
Total votes 1: ↑1 and ↓0 +1
Comments 0

Algorithms in Go: Bit Manipulation

Reading time 5 min
Views 3.2K

This article is a part of Algorithms in Go series where we discuss common algorithmic problems and their solution patterns.


In this edition, we take a closer look at bit manipulations. Bit operations can be extremely powerful and useful in an entire class of algorithmic problems, including problems that at first glance does not have to do anything with bits.


Let's consider the following problem: six friends meet in the bar and decide who pays for the next round. They would like to select a random person among them for that. How can they do a random selection using only a single coin?



The solution to this problem is not particularly obvious (for me:), so let's simplify a problem for a moment to develop our understanding. How would we do the selection if there were only three friends? In other words, how would we "mimic" a three-sided coin with a two-sided coin?

Read more →
Total votes 2: ↑2 and ↓0 +2
Comments 0

Converting text into algebra

Reading time 10 min
Views 1.5K

Algebra and language (writing) are two different learning tools. When they are combined, we can expect new methods of machine understanding to emerge. To determine the meaning (to understand) is to calculate how the part relates to the whole. Modern search algorithms already perform the task of meaning recognition, and Google’s tensor processors perform matrix multiplications (convolutions) necessary in an algebraic approach. At the same time, semantic analysis mainly uses statistical methods. Using statistics in algebra, for instance, when looking for signs of numbers divisibility, would simply be strange. Algebraic apparatus is also useful for interpreting the calculations results when recognizing the meaning of a text.

Читать далее
Total votes 1: ↑1 and ↓0 +1
Comments 0

Compilation of math functions into Linq.Expression

Reading time 12 min
Views 5.5K

Here I am going to cover my own approach to compilation of mathematical functions into Linq.Expression. What we are going to have implemented at the end:

1. Arithmetical operations, trigonometry, and other numerical functions

2. Boolean algebra (logic), less/greater and other operators

3. Arbitrary types as the function's input, output, and those intermediate

Hope it's going to be interesting!

Read more →
Total votes 4: ↑4 and ↓0 +4
Comments 1

Algorithms in Go

Reading time 2 min
Views 5.2K

Most solutions to algorithmic problems can be grouped into a rather small number of patterns. When we start to solve some problem, we need to think about how we would classify them. For example, can we apply fast and slow аlgorithmic pattern or do we need to use cyclic sortpattern? Some of the problems have several solutions based on different patterns. In this series, we discuss the most popular algorithmic patterns that cover more than 90% of the usual problems.

It is different from High-School Algorithms 101 Course, as it is not intended to cover things like Karatsuba algorithm (fast multiplication algorithm) or prove different methods of sorting. Instead, Algorithmic Patterns focused on practical skills needed for the solution of common problems. For example, when we set up a Prometheus alert for high request latency we are dealing with Sliding Window Pattern. Or let say, we organize a team event and need to find an available time slot for every participant. At the first glance, it is not obvious that in this case, we are actually solving an algorithmic problem. Actually, during our day we usually solve a bunch of algorithmic problems without realizing that we dealing with algorithms.

The knowledge about Algorithmic Patterns helps one to classify a problem and then apply the appropriate method.

But probably most importantly learning algorithmic patterns boost general programming skills. It is especially helpful when you are debugging some production code, as it trains you to understand the execution flow.

Patterns covered so far:

Sliding Window I

Sliding Window II

Merge Intervals

Dutch National Flag

Matrix Spiral

Iterative Postorder Traversal

Bit Manipulation

Stay tuned :)

<Promo> If you interested to work as a backend engineer, there is an open position in my squad. Prior knowledge of Golang is not required. I am NOT an HR and DO NOT represent the company in any capacity. However, I can share my personal experience as a backend engineer working in the company. </Promo>

Read more
Total votes 7: ↑6 and ↓1 +5
Comments 0

Algorithms in Go: Iterative Postorder Traversal

Reading time 3 min
Views 2.6K

In this article, we discuss the postorder traversal of a binary tree. What does postorder traversal mean? It means that at first, we process the left subtree of the node, then the right subtree of the node, and only after that we process the node itself.

Why would we need to do it in this order? This approach solves an entire class of algorithmic problems related to the binary trees. For example, to find the longest path between two nodes we need to traverse the tree in a postorder manner. In general, postorder traversal is needed when we cannot process the node without processing its children first. In this manner, for example, we can calculate the height of the tree. To know the height of a node, we need to calculate the height of its children and increment it by one.

Let's start with a recursive approach. We need to process the left child, then the right child and finally we can process the node itself. For simplicity, let's just save the values into slice out.

Read more
Total votes 1: ↑1 and ↓0 +1
Comments 0

Algorithms in Go: Matrix Spiral

Reading time 5 min
Views 2.4K

Most solutions to algorithmic problems can be grouped into a rather small number of patterns. When we start to solve some problem, we need to think about how we would classify them. For example, can we apply fast and slowalgorithmic pattern or do we need to use cyclic sortpattern? Some of the problems have several solutions with different patterns. In this article of series Algorithms in Go we consider an algorithmic pattern that solves an entire class of the problems related to a matrix. Let's take one of such problems and see how we can handle it.

How can we traverse a matrix in a spiral order?

Read more
Total votes 3: ↑3 and ↓0 +3
Comments 0

Why PVS-Studio Uses Data Flow Analysis: Based on Gripping Error in Open Asset Import Library

Reading time 5 min
Views 653

Why PVS-Studio Uses Data Flow Analysis
An essential part of any modern static code analyzer is data flow analysis. However, from an outside perspective, the use of data flow analysis and its benefit is unclear. Some people still consider static analysis a tool searching for something in code according to a certain pattern. Thus, we occasionally write blog posts to show how this or that technology, used in the PVS-Studio analyzer, helps to identify another interesting error. Today, we have such an article about the bug found in the Base64, one of the encoding standard implementations of binary data.

Read more →
Total votes 2: ↑2 and ↓0 +2
Comments 0

Algorithms in Go: Dutch National Flag

Reading time 3 min
Views 2.7K

The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

For simplicity instead of colors red, white, and blue we will be dealing with ones, twos and zeroes.

Let's start with our intuition. We have an array of zeroth, ones, and twos. How would we sort it? Well, we could put aside all zeroes into some bucket, all ones into another bucket, and all twos into the third. Then we can fetch all items from the first bucket, then from the second, and from the last bucket, and restore all the items. This approach is perfectly fine and has a great performance. We touch all the elements when we iterate through the array, and then we iterate through all the elements once more when we "reassamble" the array. So, the overall time complexity is O(n) + O(n) ~= O(n). The space complexity is also O(n) as we need to store all items in the buckets.

Can we do better than that? There is no way to improve our time complexity. However, we can think of a more efficient algorithm in regard to space complexity. How would we solve the problem without the additional buckets?

Let's make a leap of faith and pretend that somehow we were able to process a part of the array. We iterate through part of the array and put encountered zeroes and ones at the beginning of the array, and twos at the end of the array. Now, we switched to the next index i with some unprocessed value x. What should we do there?

Read more
Total votes 8: ↑8 and ↓0 +8
Comments 4

Algorithms in Go: Merge Intervals

Reading time 4 min
Views 3.5K

This is the third part of a series covering the implementation of algorithms in Go. In this article, we discuss the Merge Interval algorithm. Usually, when you start learning algorithms you have to deal with some problems like finding the least common denominator or finding the next Fibonacci number. While these are indeed important problems, it is not something that we solve every day. What I like about the Merge Interval algorithm is that we apply it in our everyday life, usually without even noticing that we are solving an algorithmic problem.

Let's say that we need to organize a meeting for our team. We have three colleagues Jay, May, and Ray and their time schedule look as follows (a colored line represents an occupied timeslot):

Read more
Total votes 2: ↑2 and ↓0 +2
Comments 0

Doing «Data Science» even if you have never heard the words before

Reading time 12 min
Views 1.3K

There’s a lot of talk about machine learning nowadays. A big topic – but, for a lot of people, covered by this terrible layer of mystery. Like black magic – the chosen ones’ art, above the mere mortal for sure. One keeps hearing the words “numpy”, “pandas”, “scikit-learn” - and looking each up produces an equivalent of a three-tome work in documentation.

I’d like to shatter some of this mystery today. Let’s do some machine learning, find some patterns in our data – perhaps even make some predictions. With good old Python only – no 2-gigabyte library, and no arcane knowledge needed beforehand.

Interested? Come join us.

Read more
Rating 0
Comments 0

Algorithms in Go: Sliding Window Pattern (Part II)

Reading time 4 min
Views 5.9K

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/adf4f836-dc81-4a3d-8a84-9c1d9c81fd66/algo_-_Starting_Picture.jpg


This is the second part of the article covering the Sliding Window Pattern and its implementation in Go, the first part can be found here.


Let's have a look at the following problem: we have an array of words, and we want to check whether a concatenation of these words is present in the given string. The length of all words is the same, and the concatenation must include all the words without any overlapping. Would it be possible to solve the problem with linear time complexity?


Let's start with string catdogcat and target words cat and dog.


https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a49a78c7-5177-401b-9d30-3f02d3d8db49/algo_-_Input_string.jpg


two concat


How can we handle this problem?

Read more →
Rating 0
Comments 0

Algorithms in Go: Sliding Window Pattern

Reading time 3 min
Views 5.4K

Let's consider the following problem: we have an array of integers and we need to find out the length of the smallest subarray the sum of which is no less than the target number. If we don't have such a subarray we shall return -1.

We can start with a naive approach and consider every possible subarray in the input:

Continue reading
Total votes 5: ↑5 and ↓0 +5
Comments 4

How to build a high-performance application on Tarantool from scratch

Reading time 33 min
Views 2.8K
image

I came to Mail.ru Group in 2013, and I required a queue for one task. First of all, I decided to check what the company had already got. They told me they had this Tarantool product, and I checked how it worked and decided that adding a queue broker to it could work perfectly well.

I contacted Kostja Osipov, the senior expert in Tarantool, and the next day he gave me a 250-string script that was capable of managing almost everything I needed. Since that moment, I have been in love with Tarantool. It turned out that a small amount of code written with a quite simple script language was capable of ensuring some totally new performance for this DBMS.

Today, I’m going to tell you how to instantiate your own queue in Tarantool 2.2.
Read more →
Total votes 18: ↑18 and ↓0 +18
Comments 0

Implementation of Linked List in PHP

Reading time 3 min
Views 7K

A linked list is a linear data structure, which contains node structure and each node contains two elements. A data part that stores the value at that node and next part that stores the link to the next node as shown in the below image:


Linked List Node

The first node also known as HEAD is usually used to traverse through the linked list. The last node (next part of the last node) points to NULL. The list can be visualized as a chain of nodes, where every node points to the next node.


Linked List

Implementation of Singly Linked List


Representation:


In PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.


//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  //constructor to create an empty LinkedList
  public function __construct(){
    $this->head = null;
  }
};

Read more →
Total votes 7: ↑5 and ↓2 +3
Comments 4

MEMS accelerometers, magnetometers and orientation angles

Reading time 8 min
Views 12K


When it's necessary to evaluate the orientation angles of an object you may have the question — which MEMS sensor to choose. Sensors manufacturers provide a great amount of different parameters and it may be hard to understand if the sensor fit your needs.

Brief: this article is the description of the Octave/Matlab script which allows to estimate the orientation angles evaluation errors, derived from MEMS accelerometers and magnetometers measurements. The input data for the script are datasheet parameters for the sensors. Article can be useful for those who start using MEMS sensors in their devices. You can find the project on GitHub.
Read more →
Total votes 5: ↑5 and ↓0 +5
Comments 0

Queue Implementation in JavaScript / Algorithm and Data Structure

Reading time 4 min
Views 7.7K
What do you imagine when you hear the word "Queue"? If you are not familiar with Programming you maybe think about the queue in shop or hospital. But if you are a programmer you associate it 99% with Data Structures and Algorithms. Whoever you are, today we will discuss how to implement Queue Data Structure in JavaScript and what are its differences with a simple Array. Let's get started!


Read more →
Total votes 5: ↑0 and ↓5 -5
Comments 0

Authors' contribution