| Lec. | Date | Handouts | Topics | Reading | Homework and exams |
|---|
| 1 | Mon, Aug 27 | General Course Information, Lecture 1 Notes | Introduction. Why study algorithms? | Chapter 1.1 | Angel: (1) survey, (2) post a RECOGNIZABLE photo of your face |
| 2 | Wed, Aug 29 | Hw 1 (in latex), Lecture 2 Notes | Stable Matching Problem | Chapter 1.2 | Hw 1 out |
| 3 | Fri, Aug 31 | Demo
of Propose-and-Reject Algorithm, Lecture 3 Notes, Propose-and-reject pseudocode: PDF, latex | Analysis of Propose-and-Reject; Review of Asymptotic Notation | Chapters
2.1--2.4 | |
| | Mon, Sep 3 | | Labor Day (no class) |
| 4 | Wed, Sep 5 | Hw 2 (in latex) | Graph Representation. Graph traversal: BFS,DFS | Chapter 3 | Hw 1 due; Hw 2 out |
| 5 | Fri, Sep 7 | Lecture Notes on DFS, provided by Piotr Berman. Animation works ONLY
if viewed using gv. | Guest lecture by Piotr Berman. Applications of DFS: topological sort; articulation points and biconnected components. | Chapter 3 | |
| 6 | Mon, Sep 10 | Demo
of Interval Scheduling Algorithm, Lecture 6 Notes | Greedy Algorithms. Interval Scheduling and Interval Partitioning Problems. Greedy Analysis: Greedy Stays Ahead; Structural Argument. | Chapter 4.1, review (1) priority queues: Chapter 2.5 and (2) sorting | |
| 7 | Wed, Sep 12 | Lecture 7 Notes; Hw 3 (in latex) | Greedy Analysis: An Exchange Argument | Chapters 4.2-4.3 | Hw 2 due; Hw 3 out |
| 8 | Fri, Sep 14 | Lecture 8 Notes | Greedy Graph Algorithms: Sortest Paths (Dijkstra) and MST (Prim, Kruskal, Reverse-Delete) | Chapter 4.4-4.5 | |
| 9 | Mon, Sep 17 | Lecture 9 Notes | Implementing Prim and Kruskal. Union-Find Data Structure. Clustering. | Chapter 4.5-4.7 | |
| 10 | Wed, Sep 19 | Lecture 10 Notes, Demo
of Mergesort, Demo
of Counting Inversions; Hw 4 (in latex) | Divide and Conquer: Mergesort, Counting Inversions, Binary Search. Recursion Tree Method. | Ch. 5.1-5.3 | Hw 3 due; Hw 4 out |
| 11 | Fri, Sep 21 | Lecture 11 Notes | Exponentiation. Master Theorem. | | |
| 12 | Mon, Sep 24 | Exam 1 Announcement | Review. | | |
| 13 | Wed, Sep 26 | Lecture 13 Notes | Finding the Closest Pair of Points. | Chapter 5.4 | Hw 4 due |
| 14 | Fri, Sep 28 | Lecture 14 Notes | Median and Order Statistics. | | Midterm: 8:15-10:15pm, 158 Willard |
| 15 | Mon, Oct 1 | Lecture 15 Notes | Karatsuba's algorithm for integer multiplicatiplication. Strassen's algorithm for matrix multiplication. | Chapter 5.5 | |
| 16 | Wed, Oct 3 | Hw 5 (in latex) | Midterm follow up. | | Hw 5 out |
| 17 | Fri, Oct 5 | Lecture 17 and 18 Notes on FFT | FFT | Chapter 5.6 | |
| 18 | Mon, Oct 8 | Lecture 18--20 Notes on WIS | FFT (continued). Dynamic programming. | Chapter 6.1 | |
| 19 | Wed, Oct 10 | Hw 6 (in latex) | Dynamic programming: Weighted Interval Scheduling. Review questions on Strassen and recursion trees. | Chapter 6.2 | Hw 5 due; Hw 6 out |
| 20 | Fri, Oct 12 | Lecture 20 notes on LCS | Dynamic Programming: WIS (continued), Longest Common Subsequence | Chapter 6.6 | |
| 21 | Mon, Oct 15 | Lecture 21 notes | Dynamic Programming: Knapsack | Chapter 6.4 | |
| 22 | Wed, Oct 17 | Hw 7 (in latex), Lecture 22 notes | Dynamic Programming: RNA Secondary Structure | Chapter 6.5 | Hw 6 due; Hw 7 out |
| 23 | Fri, Oct 19 | | Guest lecture by Martin Furer. Dynamic Programming:
shortest paths (Bellman-Ford) | Chapters 6.8-6.10 | |
| 24 | Mon, Oct 22 | Lectures 23 adn 24 notes | Guest lecture by Martin Furer. Dynamic Programming | | |
| 25 | Wed, Oct 24 | Hw 8 (in latex) | Network flow: max flow and min cut | Chapter 7.1 | Hw 7 due; Hw 8 out |
| 26 | Fri, Oct 26 | Lectures 25 and 26 notes | Ford-Fulkerson Algorithm | Chapter 7.2 | |
| 27 | Mon, Oct 29 | Lecture 27 notes | Choosing good augmenting paths | Chapter 7.3 | |
| 28 | Wed, Oct 31 | | Review | | Hw 8 due |
| 29 | Fri, Nov 2 | Lecture 29 notes | Review + Maximum Matching | Chapter 7.5 | Midterm: 8:15-10:15pm, 158 Willard |
| 30 | Mon, Nov 5 | | Maximum Matching | Chapter 7.6 | |
| 31 | Wed, Nov 7 | Lectures 31, 32 notes, Hw 9 (in latex) | Edge-Disjoint Paths; Extensions of Max Flow | Chapter 7.7 | Hw 9 out |
| 32 | Fri, Nov 9 | | Extensions of Max Flow | Chapter 7.8 | |
| 33 | Mon, Nov 12 | Lectures 33, 34 notes | Applications of Max Flow | Chapters 7.9-7.10 | |
| 34 | Wed, Nov 14 | | Applications of Max Flow | Chapters 7.11-7.12 | Hw 9 due |
| 35 | Fri, Nov 16 | Lectures 35, 36 notes, Hw 10 (in latex) | Computational Intractability: Polynomial Time Reductions, Decision vs. Search Problems | Chapter 8.1 | Hw 10 out |
| Nov 19--23 | | Happy Thanksgiving Holiday! | | |
| 36 | Mon, Nov 26 | | Polynomial Time Reductions: Basic Techniques. Self-Reducibility | Chapter 8.2 | |
| 37 | Wed, Nov 28 | Lecture 37 notes, Hw 11 (in latex) | Computational intractability. Classes P and NP. NP-completeness | Chapters 8.3, 8.4 | Hw 10 due; Hw 11 out |
| 38 | Fri, Nov 30 | Lectures 38 and 39 (first half) notes | Extending the limits of tractability. Finding Small Vertex Covers. | Chapters 10.1-10.2 | |
| 39 | Mon, Dec 3 | Lectures 39 (second half) and 40 notes | Extending the limits of tractability: Solving NP-hard graph problems on trees. Approximation algorithms | Chapter 11.1 | |
| 40 | Wed, Dec 5 | Hw 12 (in latex) | SRTE. Approximation Algorithms: Load balancing. | Review basic probability | Hw 11 due; Hw 12 out |
| 41 | Fri, Dec 7 | Lecture 41 notes | The pricing method: Vertex Cover | Chapter 11.4 | |
| 42 | Mon, Dec 10 | Lecture 42 notes + notes on Linearity of Expectation | Randomized Algorithms: Contention Resolution, Global Min Cut | Chapters 13.1-13.3 | |
| 43 | Wed, Dec 12 | | | | Hw 12 due |
| 44 | Fri, Dec 14 | | | | |
| Mon, Dec 17 | | | | Final exam: 4:40-6:30pm, 201 Thomas |