CS G7800: Advanced Algorithms; Fall 2009

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

Course Description

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.

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.

Class schedule

 Lecture  Content Problem Sets
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.  

Note: Solutions to problem sets are distributed in class and available upon request.

(#) Note: Scribes for these lectures are distributed in class and available upon request.