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

Final Answers
© 2000-2020   Gérard P. Michon, Ph.D.

Cool  Algorithms

 Alan Turing 
 1789-1857
An algorithm must be seen to be believed.
Donald Knuth  (1938-)

Related articles on this site:

 Michon

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.

 
border
border

Combinatorial Algorithms


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

 Come back later, we're
 still working on this one...

Theoretical Considerations :

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

 Come back later, we're
 still working on this one...

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).

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

Wikipedia :   Priority queue   |   Heap   |   Heapsort


(2017-04-13)  Radix Sorting
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.

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

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.

Descartes ovum

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

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).

 Come back later, we're
 still working on this one...

Wikipedia :   Knuth-Morris-Pratt algorithm (KMP)


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

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

Wikipedia :   Spanning tree   |   Minimum spanning tree (MST)


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

 Come back later, we're
 still working on this one...

Weakly Polynomial Time :

 Come back later, we're
 still working on this one...

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

border
border
visits since March 29, 2017
 (c) Copyright 2000-2020, Gerard P. Michon, Ph.D.