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, polynomialtime 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.
NPcompleteness.
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 comparisonbased 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 "PCmodel" vs. the Turingmachine 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, 133] 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. Singlesource shortest paths: Dijkstra's algorithm, BellmanFord algorithm. 
[CLRS 24]  
October 17  Finish analysis of BellmanFord algorithm. Allpairs shortest paths: matrixmultiplicationlike, FloydWarshall, Johnson.  [CLRS 24, 25]  
October 21  Maximum flow: FordFulkerson, maxflow mincut.  Unusual office hours due to PhD committee: 56 [CLRS 26]  
October 24  Maximum flow: EdmondsKarp, application to Maximum bipartite matching.  Problem set 3 out. Solutions to problem set 2 out. (*) Problem set 2 due.  [CLRS 26] Midsemester survey. 
October 28  Finish EdmondsKarp Start linear programming  Michel Goemans' notes on linear programming.
Recent research on linear programming: A Randomized PolynomialTime 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: 56  
November 7  Polynomials, coefficient and pointvalue 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: minimumweight vertexcover problem.  [CLRS 35]  
November 21  Randomization: MAX3CNF, MAXCUT. Derandomization: MAXCUT.  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 MAXCUT and MAX2SAT.  [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  NPcompleteness. The CookLevin 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 writeup due.  [CLRS 34] 
December 12  Students' presentations  
December 16  Students' presentations  Problem set 5 due. 