Number of Units: 3
Schedule: Monday and Wednesday 10:30-12:00pm in 310 Soda
Description:
--------------------------------------------------------------------------------
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. We will present a variety of such algorithms, mostly drawn from the following list, in the chronological order of their appearance.
Elementary examples: Binary arithmetic, Euclidean algorithm, greedy algorithm,
Dijkstra shortest-path algorithm, Gaussian elimination, bipartite matching.
Simplex algorithm for linear programming (1947)
Fast Fourier Transform (1959)
Gale-Shapley proposal algorithm (1962)
Edmonds' nonbipartite matching algorithm (1965)
Union-find algorithm (1975)
The LLL 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)
Reingold's logspace algorithm for st-connectivity (2004)