This course will survey the design and analysis of algorithms. We will study several basic algorithmic paradigms (e.g. divide-and-conquer, dynamic programming, the greedy approach and randomization), their application to core problems in graph theory and optimization, as well as analysis of time and space complexity. Our focus will be on understanding these paradigms and studying the algorithmic problems that can be solved using that particular paradigm. (more)
Date |
Reading |
Class Topic |
| Jan 29 | Chapter 1 | Administrivia and Overview |
| Feb 1 | Sec 2.1--2.4 | Computational Model and Asymptotic Notation |
| Feb 6 | 3.1--3.3 | Connectivity and Shortest Paths in Undirected Graphs |
| Feb 8 | 3.4--3.6 | Graph Representations, DAGs and Topological Ordering |
| Feb 13 | 4.3--4.6 | Shortest Paths in Weighted Graphs |
| Feb 15 | 4.3--4.6 | Minimum Spanning Trees |
| Feb 20 | 4.6--4.7 | Minimum Spanning Trees and Clustering |
| Feb 22 | 4.8 | Huffman Codes |
| Feb 27 | CLR | Matroids and Minimum Spanning Trees |
| Mar 1 | CLR and 4.1 | Scheduling and Sorting |
| Mar 6 | CLR or 5.2 | Recurrence Relations and a Master Theorem |
| Mar 8 | 5.5, 5.6 | Multiplication Algorithms and Convolution |
| Mar 13 | Exam Review | -- |
| Mar 15 | Midterm Exam | -- |
| Mar 20 | — | Spring Break |
| Mar 22 | — | Spring Break |
| Mar 27 | 6.1-6.3 | Weighted Interval Scheduling and Segmented Least Squares |
| Mar 29 | 6.4-6.5 | Knapsack Scheduling and Sequence Alignment |
| Apr 3 | 6.6 | RNA Secondary Structure |
| Apr 5 | 6.8-6.10 | Bellman-Ford Algorithm for Shortest Paths |
| Apr 10 | 7.1, 7.2 | Network Flows and the Ford-Fulkerson Algorithm |
| Apr 12 | 7.3, 7.4 | Faster Algorithms for Max-Flow |
| Apr 17 | — | No Class due to Monday Schedule |
| Apr 19 | 7.5, 7.6 | Bipartite Matching |
| Apr 24 | (Guest Lecturer: Prof. Tilman Wolf) | Network Flows and Routing |
| Apr 30 | 8.1, 8.2 | Polynomial-Time Reducibility |
| May 1 | 8.3, 8.4, 8.9 | NP-completeness and Complexity Classes |
| May 3 | 11.3, 11.4 | Approximation Algorithms: Set and Vertex Cover |
| May 8 | 13.3, 13.5 | Randomization in Algorithms |
| May 10 | 13.9 | Chernoff Bounds |
| May 15 | — | Review |
Prior experience with some basic tools from discrete mathematics will be useful; we will make use of standard proof techniques (e.g. induction), counting, and some discrete probability.
We will have biweekly homework assignments (30% of total grade), one midterm exam (30%), an optional final project (15%), and a final exam (25% with optional final project, 40% without). The optional final project will be an experimental comparison of two algorithms; you will have propose and get approval for your project from me.
Homework is due at the beginning of class; late submissions will not be accepted. Makeup exams must be scheduled at least one week in advance.
The textbook for this course is Algorithm Design by Jon Kleinberg and Éva Tardos (Addison-Wesley, ISBN 0-321-29535-8).