Movatterモバイル変換

Cool Algorithms

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

Stable marriages: Two people shouldn't prefer each other to their spouses.
Ford-Fulkerson algorithm. Best network flow from source to sink (1956).
Heap priority queues allow sorting in O( n Log n ) worst time (1964).
Alphabetic sorting is often not performed by pairwise comparisons.
Radix sorting: Sorting n integers in linear time with radix-n numeration.
Best path in a network: Dijkstra's algorithm and Bellman-Ford algorithm.
" A* " best-first search uses aheuristicalunderestimate of the cost to a goal.
Alpha-Beta Prunning Algorithm: Finding a minimax value in optimal time.
String-matching in sublinear time. The Knuth-Morris-Pratt algorithm.
Union-find: Linked partitions allow component merging and fast retrievals.
Dynamic programming. Store partial results to avoid duplication of efforts.
Minimum spanning tree. Least costly set of edges retaining connectivity.
Linear programming in polynomial time. Foregoing the simplex algorithm.

Related articles on this site:

Rounding.
Numeration.
Graph theory.
Computer science.
Two-player games.
Euclid's algorithm.
Modular reciprocal.
Fast Fourier transform.
NP-complete problems.
Prime factorization algorithms.
Raising a number to a large power.
Rabin-Miller stochastic primality.
Lucas-Lehmer test: p-2 modular squarings suffice to prove 2^p-1 is prime.
Floyd's cycle-finding algorithm memorizes only 2 states (hare & tortoise).
Shors's algorithm would work in polynomial time on a quantum computer.
Blockchain, hashpuzzles, Merkle trees, public/private-key cryptography.

Related Links (Outside this Site)

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

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) 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 matchingsmay grow exponentially with the size of the dating pool. He attributed toJohn Conway (1937-2020) the remark thatthe set of stable matchings forms a distributive lattice.

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

(2017-03-28) Greedy method maximizing the flow from a source (s) to a sink (t).

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

(2017-03-29) Bulk insertions can be more efficient than consecutive single insertions.

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

(2017-04-13) 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 topairwise comparisons at the ouset. Instead, they'll make 26 sets of cards sharing the same first letterand 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 withat least one other card in the first N letters.

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

(2017-04-13) To sort N integers, use radix-N numeration.

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

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

(2017-04-07) The Bellman-Ford algorithm handles negative costs. Dijkstra's doesn't.

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

(2017-03-29) Finding the best path to a goal usingheuristical lower-bounds of all costs.

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

(2017-03-29) 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...

(2017-03-29) The longer the pattern, the faster the search.

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

(2017-03-29) Path compression (FIND) combined with rank heuristic (UNION).

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

(2017-03-29) 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...

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

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

(2017-01-01) 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...

visits since March 29, 2017

[8]ページ先頭

©2009-2025 Movatter.jp