23,558

## Using the Quick Raise of Matrices to a Power to Write a Very Fast Interpreter of a Simple Programming Language

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.
8,861

## Young Tableaux in the Tasks of Searching and Sorting

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.
88,646

## The Nth Fibonacci Number in O(log N)

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
16,982

## Building a Minimal Convex Hull

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.
8,816

## A Point Localization in a Polygon

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).
33,319