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 with respect to particular application areas. (more)
Date |
Reading |
Class Topic |
| Jan 19 | -- | Administrivia and Overview |
| Jan 24 | 2.3, Chapter 3, 4.3--4.6 | Asymptotic Notation and Recurrences |
| Jan 24 | 2.3, Chapter 3, 4.3--4.6 | Sorting, Correctness and Recurrences |
| Jan 28 | 2.3, Chapter 3, 4.3--4.6 | Merge Sort and Master Method |
| Jan 31 | Chapter 4 | Proof of the Master Method |
| Feb 4 | Chapter 4 | More of the Master Method and Divide-and-Conquer |
| Feb 7 | 4.2 | Divide-and-Conquer Multiplication |
| Feb 9 | 4.2, 30.1, 30.2 | More Multiplication and Convolutions |
| Feb 11 | 30.1, 30.2 | Evaluating Polynomials and the Discrete Fourier Transform |
| Feb 14 | 30.1, 30.2 | More DFT |
| Feb 16 | Chapter 7 | Quicksort and Randomized Algorithms |
| Feb 18 | Chapter 7 | Analysis of Quicksort |
| Feb 22 | Chapter 9 | Randomized and Deterministic Selection |
| Feb 23 | Chapter 9 | Worst-case Linear Time Deterministic Selection |
| Feb 25 | 6.1--6.4 | Heaps and Greedy Sorting |
| Feb 28 | 16.1--16.3 | The Greedy Approach for Interval Scheduling |
| Mar 2 | 16.1--16.3 | Huffman Codes |
| Mar 4 | Chapter 23 | Minimum Spanning Trees |
| Mar 7 | Chapter 23 | More Minimum Spanning Trees |
| Mar 9 | -- | Exam Review |
| Mar 23 | 24.3 | Shortest Paths in Weighted Graphs |
| Mar 25 | -- | Weighted Interval Scheduling |
| Mar 30 | 16.2 | Knapsack Problems and Dynamic Programming |
| Apr 1 | 15.2--15.4 | Longest Common Subsequence and Matrix Chain Multiplication |
| Apr 4 | 15.2--15.4 | Longest Common Subsequence and Sequence Alignment |
| Apr 6 | 24.1 | Bellman-Ford Shortest Paths and Routing |
| Apr 8 | 24.1 | Bellman-Ford, Negative Cycles and Arbitrage |
| Apr 11 | -- | Statistical Inference and Dynamic Programming |
| Apr 13 | 26.1--26.2 | Network Flows and the Ford-Fulkerson Method |
| Apr 15 | 26.2--26.3 | The Max-Cut Min-Flow Theorem and Bipartite Matching |
| Apr 20 | Chapter 29 | Introduction to Linear Programming |
| Apr 22 | Chapter 29 | The Simplex Method and LP Duality |
| Apr 25 | Chapter 34 | Computational Complexity |
| Apr 29 | Chapter 35 | Approximation and Complexity |
| May 2 | -- | Course 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 (roughly) weekly 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 Introduction to Algorithms (3rd Edition) by Tom Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein (MIT Press).