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 27 | -- | Administrivia and Overview |
| Jan 29 | 2.3, Chapter 3, 4.1, 4.2 | Asymptotic Notation and Recurrences |
| Feb 2 | 4.3, 4.4 | The Master Method |
| Feb 4 | 4.3, 4.4 | More of the Master Method and Applications |
| Feb 10 | 5.1--5.3, 7.1--7.4, Appendix C.2, C.3 | Quicksort and Randomized Algorithms |
| Feb 12 | Chapter 9 | Randomized and Deterministic Selection |
| Feb 17 | 9.3, 28.2 | Deterministic Selection and Multiplication Algorithms |
| Feb 19 | 30.1, 30.2 | Convolutions and the Discrete Fourier Transform |
| Feb 24 | 30.1, 30.2, 6.1--6.4 | Discrete Fourier Transform |
| Feb 24 | 6.1--6.4, 16.1--16.3 | Greedy Sorting and Huffman Codes |
| Mar 3 | 16.1--16.3 | Huffman Codes and Greedy Scheduling |
| Mar 4 (Makeup) | 16.2, 16.5 | Unit-Time Scheduling and the Knapsack Problem |
| Mar 10 | -- | Review |
| Mar 12 | -- | In-class Midterm |
| Mar 17 | -- | Spring Break |
| Mar 19 | -- | Spring Break |
| Mar 24 | 15.2, 15.3 | Weighted Interval Scheduling and 0-1 Knapsack |
| Mar 26 | 15.4 | Matrix Chain Multiplication and Sequence Comparison |
| Apr 1 | 22.1 | Introduction to Graph Theory |
| Apr 3 | 22.2-22.3 | Breadth-First and Depth-First Search |
| Apr 7 | 22.3-22.5 | Topological Sorting and Strong Connectivity |
| Apr 9 | 23.1-23.2 | Minimum Spanning Trees |
| Apr 14 | 23.1-23.2 | More Minimimum Spanning Trees |
| Apr 16 | 24.1-24.3 | Single Source Shortest Paths in Weighted Graphs |
| Apr 22 | 24.1-24.3, 26.1 | Bellman-Ford, Negative Cycles and Network Flows |
| Apr 23 | 26.1-26.3 | Network Flows |
| Apr 28 | 26.2-26.3 | Network Flows and Bipartite Matching |
| Apr 30 | -- | No Class |
| May 5 | -- | Class Cancelled |
| May 7 | Ch. 34 | Computational Complexity |
| May 12 | The Fast Multipole Method and Course Review | |
| May 15 | 10a-12p, Studio A | Final Exam |
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 Introduction to Algorithms (2nd Edition) by Tom Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein (MIT Press/Addison-Wesley, ISBN 9780072970548).