Instructor: Emanuele Viola
Office Hours: Tuesday after class, 3:15 - 4:15; Thursday 4:00 - 5:00.
Meetings: Tuesday and Fridays, 1:35 PM, 210 Shillman Hall map
This course presents advanced mathematical techniques for designing and analyzing computer algorithms. It reviews some of the material covered in CS G113 and then covers advanced topics. It emphasizes theoretical underpinnings of techniques used to solve problems arising in diverse domains. Topics include asymptotic analysis, advanced data structures, dynamic programming, greedy algorithms and matroid theory, amortized analysis, randomization, string matching, algebraic algorithms, and approximation algorithms. Introduces Turing machines, P and NP classes, polynomial-time reducibility, and NP completeness.
A tentative syllabus follows (one/two lectures per topic):
Divide and conquer. Sorting: Merge sort, quicksort, counting sort lower bound for sorting.
Median and order statistics.
Dynamic programming. Counting knapsack solutions.
Greedy algorithms.
Amortized analysis. Incrementing a binary counter.
Data structures: Balanced trees, skip lists.
Graph algorithms: BFS, DFS, Dijkstra's algorithm.
Minimum spanning trees: Prim, Kruskal.
Network flow.
Linear programming.
NP-completeness.
Other topics will be determined depending on class interest, and might include: random walks, expander graphs, derandomization, and Fourier Transform.
No textbook is required, but classical texbooks on algorithms covering overlapping subjects are:
[CLRS] Cormen, Leiserson, Rivest and Stein, Introduction
to Algorithms,
[MR] Motwani, Raghavan, Randomized Algorithms.
| Lecture | Content | Problem
Sets |
Extra |
| Sep 12 | Administrivia, overview of the course. | Problem set 0 out | |
| Sep 16 | Review of basics of probability theory and randomized algorithms. | Problem set 0 due | [CLRS Appendix C] |
| Sep 19 | Divide and conquer. Sorting: Merge sort, quicksort, randomized quick sort, counting sort. Lower bound for comparison-based sorting. | [CLRS 2.3, 7, 8.1, 8.2] | |
| Sep 23 | Finding the median in linear time. Dynamic programming: counting knapsack solutions, the coin changing problem. Remarks on computational model: the "PC-model" vs. the Turing-machine model. |
[CLRS 9, 15] | |
| Sep 26 | Greedy algorithms. Knapsack, activity scheduling. Minimum spanning tree: Prim, Kruskal. |
Problem set 1 out | [CLRS 16.1, 16.2, 23] Recent research on the power of greedy algorithms: Paper 1, Paper 2, Paper 3. |
| Sep 30 | Data structures: Heaps, AVL trees, skip lists. | [CLRS 6, 13-3] Most recent research on succinct arrays: Paper. Applet to play with common data structures. |
|
| October 3 | Analysis of skip lists. Amortized analysis. |
[MR 8.3], [CLRS 17]. | |
| October 7 | Amortized analysis: The potential method, dynamic tables. Basics of hashing. |
[CLRS 17, 11], [MR 8.4] | |
| October 10 | Hash tables: Construction of universal hash functions, perfect hashing. | Problem set 1 due. Solutions to problem set 1 out. (*) Problem set 2 out. |
[CLRS 11], [M 8.4] Recent research on Bloom filters: Paper, paper, paper. A survey on Bloom filters: Survey. |
| October 14 | Finish perfect hashing. Single-source shortest paths: Dijkstra's algorithm, Bellman-Ford algorithm. |
[CLRS 24] | |
| October 17 | Finish analysis of Bellman-Ford algorithm. All-pairs shortest paths: matrix-multiplication-like, Floyd-Warshall, Johnson. | [CLRS 24, 25] | |
| October 21 | Maximum flow: Ford-Fulkerson, max-flow min-cut. | Unusual office hours due to PhD committee: 5-6 [CLRS 26] | |
| October 24 | Maximum flow: Edmonds-Karp, application to Maximum bipartite matching. | Problem set 3 out. Solutions to problem set 2 out. (*) Problem set 2 due. | [CLRS 26] Mid-semester survey. |
| October 28 | Finish Edmonds-Karp Start linear programming | Michel Goemans' notes on linear programming.
Recent research on linear programming: A Randomized Polynomial-Time Simplex Algorithm for Linear Programming, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. | |
| October 31 | Linear programming: the simplex algorithm | ||
| November 4 | Linear programming: duality | A
slew of results similar to Farkas'. Unusual office hours due to PhD committee: 5-6 | |
| November 7 | Polynomials, coefficient and point-value representation, intuition behind Fast Fourier Transform. | Problem set 4 out. Solutions to problem set 3 out. (*) Problem set 3 due. | [CLRS 30] The fastest integer multiplication algorithm known (see also this). |
| November 11 | Veteran's day, no class | ||
| November 14 | Fast Fourier Transform. | Deadline for picking a topic for the project. | [CLRS 30] |
| November 18 | Approximation algorithms: Vertex cover, set cover. Linear programming relaxation: minimum-weight vertex-cover problem. | [CLRS 35] | |
| November 21 | Randomization: MAX-3-CNF, MAX-CUT. Derandomization: MAX-CUT. | Solutions to problem set 4 out. (*) Problem set 4 due. | [CLRS 35] Survey on derandomization by Luby and Wigderson. (Lectures 1 - 3) |
| November 25 | Randomized pattern matching. Semidefinite programming, randomized rounding. Better approximation algorithms for MAX-CUT and MAX-2SAT. | [MR 7.6] The paper by Goemans and Williamson. | |
| November 28 | Thanksgiving recess, no class | ||
| December 2 | P and NP | Problem set 5 out.
Deadline for meeting with the instructor about your project. (Extended until Thursday) | [CLRS 34] |
| December 5 | NP-completeness. The Cook-Levin theorem. | [CLRS 34] | |
| December 9 | Reductions. A glimpse at some of the things what we have not seen: Quantum computing, Parallel algorithms, property testing. | Project write-up due. | [CLRS 34] |
| December 12 | Students' presentations | ||
| December 16 | Students' presentations | Problem set 5 due. |