Algorithms

Hello! My name is Alex Skidanov. Currently I work at MemSQL. I have recently read an article about calculating the Nth Fibonacci number in O(log N) arithmetic operations. But why would we need it in practice? — you may ask. By itself, the calculation N-th Fibonacci number may not be very interesting, but the approach with the matrices used in the article, in practice, can be applied to a much wider range of tasks.

Young tableaux are widely known objects studied in combinatorics and related sciences. Today we are going to review how to apply Young tableaux in the context of such standard algorithmic tasks as searching and sorting. From this perspective, Young tableaux are quite close to pyramids. That’s how they are actually called in a book by T. Cormen and others. Young Tableau Notion Let’s consider a Young tableau as a partially ordered and almost filled numerical matrix.

Reading an article about getting a job in ABBYY, I came across the following task: Find the Nth Fibonacci Number in O(N) time of arithmetic operations. Thinking about it, I realized that the only solutions coming to my mind were those operating in O(n) time. But I found a better solution later. I am going to use the following denotation of sets: - non-negative integers — positive integers

Since I have recently become interested in convex hulls, I decided to go on telling you about the algorithmic geometry. Today we are going to review the building of the so-called minimal convex hulls. Though the picture on the right provides an exhaustive explanation of what they actually are, you will find more formal definitions and two classical examples below. Minimal Convex Hull Notion Let the plane have a given finite number of A points.

I have recently come across a post dedicated to solving the task of locating a point in a polygon: there is a polygon (a closed broken line with no self-intersections) and we are to determine, whether the given A point is inside the polygon or not. You may wonder, how such purely mathematic task can be related to the theory of algorithms. But it actually can. Localization is a classic task in computational geometry (do not confuse with computer graphics).

Having read some articles about tries (aka prefix trees aka radix trees), I decided to write one of my own. Today we are going to talk about a trie implementation in C++. We will also compare a string search with AVL and Radix tree. Intro A trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

Today we’re going to review an algorithm that was invented 11 years ago. Its “prototype” is a counting device with three thousand years of history. Authors The sort was presented in 2002 by three mathematicians from the University of Auckland, New Zealand. They are Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen. They work in such fields as discrete mathematics, the theory of number, quantum computations, the information theory and combinatorial algorithms.