See the previous offering
Instructor: Emanuele Viola
Office Hours: Tuesday after class (5-6) and Thursday (5-6).
Meetings: Tuesday and Fridays, 3:25-5:05 PM, Ryder Hall 433
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.
Succinct data
structures.
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 11 | Administrivia, overview of the course. Probability theory. | ||
| Sep 15 | Divide and conquer. Sorting: Merge sort, quicksort, randomized quick sort. | [CLRS 2.3, 7, 8.1, 8.2] | |
| Sep 18 | Comparison lower bound. Counting & radix sort. Median in linear time. Dynamic programming | [CLRS 2.3, 7, 8.1, 8.2, 9, 15] | |
| Sep 22 | Dynamic programming, greedy algorithms | Problem set 1 out. | [CLRS 15,16] |
| Sep 25 | Minimum spanning tree: Prim, Kruskal. Heaps, AVL trees. | [CLRS 23, 6] | |
| Sep 29 | Skip lists. Amortized analysis. | [MR 8.3] [CLRS 17] | |
| Oct 2 | Succinct non-binary arrays | Notes (Lecture 23-24). | |
| Oct 6 | Succinct non-binary arrays. Are bitvectors optimal? (#) | PS 1 due. Problem set 2 out. | The paper. |
| Oct 9 | Are bitvectors optimal? Storing sets so that membership can be decided by probing 1 bit. | ||
| Oct 13 | Hash functions (#) | [CLRS 11] | |
| Oct 16 | No class | ||
| Oct 20 | Perfect hashing. Single-source shortest path. | Ps2 due. | [CLRS 24] |
| Oct 23 | All-pairs shortest path. | Problem set 3 out. | [CLRS 24,25] |
| Oct 27 | Random-walk algorithm for connectivity | Notes (Lecture 15-18, sections 1,2). | |
| Oct 30 | Maximum flow. Ford-Fulkerson. | [CLRS 26] | |
| Nov 3 | Maximum flow. Edmonds-Karp | [CLRS 26] | |
| Nov 6 | Linear programming (#) | Problem set 3 due. | |
| Nov 10 | Linear programming | Problem set 4 out. | |
| Nov 13 | Fast fourier transform | [CLRS 30] | |
| Nov 17 | No class | ||
| Nov 20 | No class | ||
| Nov 24 | Fast fourier transform | Problem set 4 due. | [CLRS 30] |
| Nov 27 | Thanksgiving recess, No class | ||
| Dec 1 | Approximation algorithms: Vertex cover, set cover. Linear programming relaxation, quadratic programming relaxation. | [CLRS 35] | |
| Dec 4 | Approximation algorithms. Derandomization | ||
| Dec 8 | Strings: Randomized pattern matching | Problem set 5 out. | [MR 7] |
| Dec 11 | Strings: Suffix array | The paper. | |
| Dec 15 | Polynomial identities and perfect matchings. A quick tour of areas we have not seen. | [MR 7] | |
| Dec 18 | No Class | Problem set 5 due. |