CS 294-5, Spring 2006
Great Algorithms

Instructor:
  Richard Karp (karp AT cs, M 1:30-2:30, 621 Soda Hall, 642-5799)

Lectures MW 10:30-12:00, 310 Soda


Announcements
Course Overview
Lecture notes
Assignments

Announcements

announcements go here..

Course Overview

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)

Lectures

Date Topic Scribes
1 Jan 18 Euclidean Algorithm and Gaussian Elimination [ps]
2 Jan 23 Linear Programming [ps]
3 Jan 25 Linear Programming and FFT [ps]
4 Jan 30 FFT and Stable Matching [pdf]
5 Feb 1 Non-bipartite Matching [pdf]
6 Feb 6 Non-bipartite Matching, Assignment Problem [pdf]
7 Feb 8 The Miller-Rabin Randomized Primality Test (Guest Lecture by Robert Kleinberg) [not available]
8 Feb 13 Union-find algorithms [pdf]
9 Feb15 Analysis of Union-Find [ps]
10 Feb22 Lattice Basis Reduction [ps]
11 Feb27 Lattice Basis Reduction [pdf]
12 Mar1 Introduction to Groebner Bases [pdf]
13 Mar6 Groebner Bases [pdf]
14 Mar8 Sorting Networks [pdf]
15 Mar13 Patterson's version of the AKS Sorting Network [pdf]
16 Mar15 Approximate counting and sampling [pdf]
17 Mar20 Approximate counting and sampling [pdf]
18 Mar22 Sampling monomer-dimer configurations [pdf]
19 Apr3 Estimating volume [pdf]
20 Apr5 Competitive on-line algorithms [ps]
21 Apr10 Randomized paging algorithms [pdf]
22 Apr12 K-server problem [ps]
23 Apr17 Splay trees [pdf]
26 Apr26 LT codes [pdf]

Assignments