home | index | units | counting | geometry | algebra | trigonometry & functions | calculus analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

# Cool  Algorithms

An algorithm must be seen to be believed.
Donald Knuth  (1938-)

### Related Links  (Outside this Site)

The Stony Brook Algorithm Repository  by  Steven Skiena  (2008-07-10).
Algorithms, etc.  by  Jeff Erickson  (Illinois, 2015-01).

Wikipedia :     Algorithm   |   Greedy algorithm   |   Dynamic programming   |   Algorithmic game theory

3 beautiful quicksorts (53:52)  by  Jon Bentley  (Google Tech Talks, 2007-08-09).
Se;ection sort = Insertion sort (9:44)  by  Graham Hutton  (Computerphile, 2016-11-18).

Introduction to Algorithms (MIT 6.046J / 18410J, SMA 5503, Fall 2005) by Charles Leiserson, Erik Demaine & David Hsu :   1 | 2 | 3 | 4 | 5 | 6 | 7 | ...

Advanced Algorithms (Harvard CS224, 2014) by Jelani Nelson.

Big Data Algorithms (Harvard CS229r, 2016) by Jelani Nelson.

## Combinatorial Algorithms

(2014-09-20)   Stable Marriages.  Gale-Shapley Algorithm  (1962).
No unmarried couple should prefer each other to their respective spouses.

### Theoretical Considerations :

Donald Knuth showed that the number of stable matchings may grow exponentially with the size of the dating pool.  He attributed to John Conway the remark that the set of stable matchings forms a  distributive lattice.

David Gale (1921-2008)   |   Lloyd S. Shapley (1923-2016, Nobel 2012)

Stable Marriage Problem (8:36)  and  Proofs (11:36)  by  Emily Riehl  (Numberphile, 2014-09-04).
Sex and Marriage Theorems  by  Burkard Polster  (Mathologer, 2017-03-04).

(2017-03-28)  Ford-Fulkerson algorithm  (digraphs with edge-capacities)
Greedy method  maximizing the flow from a source (s) to a sink (t).

Menger's theorem (1927)   |   Max-flow problem (1954)   |   Strong duality: max-flow / min-cut theorem (1956)
Ford-Fulkerson algorithm (1955)   |   Edmonds-Karp algorithm (1972)   |   Dinic's algorithm (1970)
Karl Menger (1902-1985)   |   Lester R. Ford, Jr. (1927-)   |   Delbert R. Fulkerson (1924-1976)
Jack R. Edmonds (1934-)   |   Richard M. Karp (1927-)   |   Yefim (Chaim) A. Dinitz (19??-)
Dinitz's algorithm  was modified by  Shimon Even (1935-2004).

Ford-Fulkerson in 5 minutes (5:14)  by  Michael Sambol  (2015-07-07).

(2017-03-29)  Heap  Data Structure for Priority Queues  (1964)
Bulk insertions can be more efficient than consecutive single insertions.

Wikipedia :   Priority queue   |   Heap   |   Heapsort  (1964, by  J.W.J. Wilson, 1930-2012)

(2017-04-13)  Sorting strings in alphabetical order the  human  way...
Manually,  people  don't use pairwise comparisons to sort strings.

To put a messed-up sequence of libray cards in alphabetical order,  most people won't resort to pairwise comparisons at the ouset.  Instead, they'll make 26 sets of cards sharing the same first letter and then sort each of those sets  (using the same method recursively)  according to the rest of the word.  (Think of what  you  would do if faced with such a situation.)

The  N+1st  stage requires a total time proportional to the number of cards which coincide with at least one other card in the first  N  letters.

Wikipedia :   Priority queue   |   Heap   |   Heapsort

To sort  N  integers,  use  radix-N  numeration.

Using numeration in some base  B,  nonnegative integers can be considered to be strings in a alphabet of size  b.

Wikipedia :   Radix sort (1887)   |   Herman Hollerith (1860-1929)

(2017-04-07)   Best path in a  network  (digraph whose edges have costs).
The Bellman-Ford algorithm handles negative costs.  Dijkstra's doesn't.

Dijkstra's Algorithm (10:42)  by  Mike Pound   (Computerphile, 2017-01-04).

Wikipedia :   Dijkstra's algorithm (1956)   |   Bellman-Ford algorithm (1955, 1956, 1957, 1958))

(2017-03-29)   A*  Algorithm   ( best-first  search,  1968)
Finding the best path to a goal using heuristical lower-bounds of all costs.

A* (A Star) Search Algorithm (14:03)  by  Mike Pound   (Computerphile, 2017-02-17).

Wikipedia :   Pathfinding   |   A* search algorithm (1968)
Nils Nilsson (1933-)   |   Bertram Raphael (1936-)   |   Peter Hart (c. 1940-)

(2017-03-29)  Alpha-Beta Pruning
A tree's  minimax  value needn't depend on the values of all its branches.

Wikipedia :   Minimax   |   Alpha-beta pruning (1968)

(2017-03-29)  String-Matching in Sublinear Time
The longer the pattern, the faster the search.
This is a result from a thesis I submitted at Polytechnique  (1979).  I had effectively rediscovered the Knuth-Morris-Pratt algorithm  (published in 1977)  as was soon pointed out to me by  Philippe Flajolet (1948-2011).

Wikipedia :   Knuth-Morris-Pratt algorithm (KMP)

(2017-03-29)  Union-Find operations on disjoint-set forests
Path compression (FIND) combined with rank heuristic (UNION).

Wikipedia :   Disjoint-set forests (1964)

(2017-03-29)  Dynamic Programming
Storing the results of partial computations for multiple uses.

Richard Bellman (1920-1984)  coined the term  dynamic programming  in 1940.  He started using it with its current meaning in 1953.

Wikipedia :   Dynamic programming   |   Bellman equation   |   Richard E. Bellman (1920-1984)

(2017-01-01)  Minimum Spanning Tree
Retaning the connectivity of a network with the least-costly set of edges.

Wikipedia :   Spanning tree   |   Minimum spanning tree (MST)

(2017-01-01)  Linear Programming in Weakly Polynomial Time  (1980)
Overtaking George Dantzig's  simplex algorithm  (1947).

### Weakly Polynomial Time :

Wikipedia :   Linear programming   |   Simplex algorithm   |   George Dantzig (1914-2005).