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

---

(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+1^st 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).