[Haskell-cafe] Elementary algorithms - (Haskell language is used)

Xinyu LIU liuxinyu95 at gmail.com
Tue Jul 22 03:01:10 UTC 2014


I spent 6 years to write the book ‘Elementary Algorithms’. I finally
completed it yesterday.
This book is open and free, the PDF version can be downloaded from:

There are plenty of books about algorithms, such as ‘Introduction to
algorithms’, ‘The art of computer programming’, ‘structure and
interpretation of computer programs’… why another book? Is it reinvention
of wheel?
This book can’t compare with the above classic bibles at all. It has some
features like:
1.    All algorithms are described in math formulas and pseudo codes. I
hope it bring some taste of elegant by using algebraic symbols.
2.    All algorithms are realized in both purely functional and imperative
3.    The examples are provided in multiple programming languages,
including C, Haskell, Python, C++, Scheme/Lisp. Haskell is the main
language for all functional implementations.

The following content are covered in this book (in the order of appearance)
•    Binary search tree, insertion sort, red-black tree, AVL tree, Trie,
Patricia, suffix tree, B-tree;
•    Binary heap, Leftist heap, skew heap, splay heap, selection sort,
binomial heap, Fibonacci heap, pairing heap;
•    Queue, Finger tree based sequence, quick sort, merge sort, binary
search, saddle-back search, KMP, Boyer-Moore, DFS, BFS, Greedy algorithm,
Dynamic programming.
There are two books influenced me most, one is ‘Purely functional data
structure’ by Chris Okasaki, the other is ‘Introduction to algorithms’.

I always don’t have enough time in writing this book during the past 6
years. I am not a native speaker, the biggest problem is about English. It
is lack of proof reading by native speakers. I used some result directly,
if I had time, I should add more proof for those results.

Future work
Ideally, I think a serious algorithm book should be written in a stable
environment. I planned to write this book in 10 years. But everything
changes so fast in modern society. I experienced lay-offs once in 2012 due
to Symbian business cut off, and now again in MS. I am not sure if I can
continue this work. I think the best way is to open this book to the
community. Some future work in my mind:
•    Proof reading and review
•    Provide answers to the exercises
•    Provide proof for the directly referenced result
The whole manuscript is available at github:

Best regards
Larry, LIU Xinyu

*e*^(*π*i)+1 = 0
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140722/cd308b84/attachment.html>

More information about the Haskell-Cafe mailing list