Elementary Algorithms

While there have been already a lot of wonderful books about algorithms, data structures and math, however, few of them provide the comparison between the procedural solution and the functional solution. It can be found that functional solution sometimes is very expressive and they are close to what we are familiar in mathematics.

This series of post focus on providing both imperative and functional algo-rithms and data structures. Many functional data structures can be referenced from Okasaki’s book. While the imperative ones can be founded in classic text books or even in WIKIpedia. Multiple programming languages, includ-ing, C, C++, Python, Haskell, and Scheme/Lisp will be used. In order to make it easy to read by programmers with different background, pseudo code and mathematical function are the regular descriptions of each post.

The author will first introduce about elementary data structures before algorithms, because many algorithms need knowledge of data structures as prerequisite.

The ‘hello world’ data structure, binary search tree is the first topic; Then we introduce how to solve the balance problem of binary search tree. After that, the author will show other interesting trees. Trie, Patricia, suffix trees are useful in text manipulation. While B-trees are commonly used in file system and data base implementation.

The second part of data structures is about heaps. We’ll provide a general Heap definition and introduce about binary heaps by array and by explicit binary trees. Then we’ll extend to K-ary heaps including Binomial heaps, Fibonacci heaps, and pairing heaps.

Array and queues are considered among the easiest data structures typically, However, we’ll show how difficult to implement them in the third part. As the elementary sort algorithms, we’ll introduce insertion sort, quick sort, merge sort etc in both imperative way and functional way. The final part is about searching, besides the element searching, we’ll also show string matching algorithms such as KMP.