“great algorithms” trong KHMT

Prof. Richard Karp chuẩn bị dạy một lớp bậc cao học về những thuật toán quan trọng và nổi tiếng trong KHMT. Lời giới thiệu của syllabus:

From time to time a new algorithm comes along that causes a sensation in
theoretical computer science or in an area of application because of
its resolution of a long-standing open question, its surprising efficiency,
the novelty of its setting or approach, the elegance of its structure, the
subtlety of its analysis or its range of applications.

Không phải là tất cả (tất nhiên!), nhưng dây là một danh sách của Prof. Karp để ta tham khảo. Một số đã được nhắc tới đâu đó trong blog này:

• Elementary examples: Binary arithmetic, sorting, Euclidean algorithm,
  greedy algorithm, Dijkstra shortest-path algorithm, Gaussian elimination
• Simplex algorithm for linear programming (1947)
• Fast Fourier Transform (1959)
• Gale-Shapley proposal algorithm (1962)
• Edmonds’ nonbipartite matching algorithm (1965)
• Union-find algorithm (1975)
• Lattice basis reduction algorithm (1982)
• Buchberger’s Grobner basis algorithm (1982)
• Ajtai-Komlos-Szemeredi sorting network (1983)
• Randomized algorithms for approximating volume (1989)
• Koutsoupias-Papadimitriou k-server algorithm (1994)
• Shor’s quantum factoring algorithm (1994)
• The Winnow (1988) and Adaboost (1995) algorithms for statistical
  classification
• Interior-point algorithms for linear programming(1984) and semidefinite
  programming (1995)
• Streaming algorithms for computing moments (1995)
• Sudan’s list decoding algorithm (1997)
• LT codes and Raptor codes for data distribution (2002, 2003)
• Reingold’s logspace algorithm for st-connectivity (2004)