Algorithms From THE BOOK
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Introduction
This book is inspired by the book Proofs From THE BOOK which is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps all of the most elegant proofs of mathematical theorems. Following the same spirit, the wikibook "Algorithms From THE BOOK" contains the "greatest" algorithms.
What do we mean by "greatest" and by "algorithms" ? First "algorithms" means blah blah... "Greatest" means:
- elegant: simple and surprising from an intellectual point of view
- powerful: sufficiently efficient to solve hard problem
- useful : used with success in current industrial applications, changed our everyday life.
These two restrictions are the only ones, in particular the algorithms can come from any scientific field as mathematic, computer science (what else ?)...
A typical presentation of an algorithm is given by a brief history of its discovery that may contains a description of the problem to solve, a description of the algorithm and then main intuition behind it, (optionally) a proof that the algorithm succeeds in solving the problem, a precise and detailed explanation of an application where this algorithms works well. Humor, numerical illustrations, drawings are strongly encouraged. The overall description must be contained in a few pages (say 5 max).
[edit] RSA
[edit] Wavelet transforms
Jpeg 2000, stephane Mallat...
[edit] Kalman Filter
[edit] Q learning
Nerological idea of R. Sutton and A. Barto
Q = max()
Tesauro and his backgammon
[edit] (Matrix inversion)
[edit] Quicksort
The basic idea is to sort around a single element called "the partition point". This creates a single element in its final form and two sublists both of which need to be sorted. So a simple quicksort (using a functional style) could look like the following:
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) qsort [] = []
More efficient quicksorts uses the same idea.
- For large lists choose the partition element by median of 3 (first element, last element, middle element).
- This avoids getting a bad sort on (almost) sorted, or reverse sorted lists.
- Perform a quicksort on the list and make recursive calls for any list with more than about 4 elements.
- In a quicksort each pass will on average double the number of calls and half the number of elements. By cutting off the last few calls you end avoiding about 80% of the recursions. Since these calls are expensive this saves a considerable amount of CPU.
- Make one final pass with insertion sort on the entire list
- At this point you have an almost sorted list. Insertion sort runs in linear time on almost sorted lists.
[edit] Huffman compression
The basic idea is that rather than storing every letter using an 8 bit representation, use (for example) a short 3-bit representation for common letters like "e" and "t". Since 3 bits isn't enough to represent all 26 letters, use a much longer representation (for example, 9 bits) for infrequent letters like "j".
What representation is optimal, allowing us to store a particular file in the least amount of bits?
