| Date | Topics | Reading |
|---|---|---|
| Tuesday, August 26 | Administrivia, overview, primality, reduction, recursion | Chapters 1-3 from text book, Jeff Erickson's notes on recurrences |
| Thursday, August 28 | Divide and Conquer, Merge Sort, Multiplication, Recurrences | Chapter 5, Jeff's notes on recurrences |
| Tuesday, September 2 | Recurrences, Divide and Conquer contd: Closest Pair, Selection | Chapter 5, Jeff's notes on recurrences |
| Thursday, September 4 | Graphs, Connectivity, DFS, Directed Graphs | Chapter 3 |
| Tuesday, September 9 | DAGs, Topological Sort, Linear time algorithm for Strong Connected Components | Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
| Thursday, September 11 | BFS and application to Bipartite Graphs, Dijkstra's Algorithm for Shortest Paths | Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
| Tuesday, September 16 | Shortest Paths with Negative Lengths, Bellman-Ford Algorithm | Chapter 3 of Dasgupta etal book |
| Thursday, September 18 | Greedy Algorithms: Examples and Proof Techniques | Chapter 4 of text book |
| Tuesday, September 23 | Greedy Algorithms for Minimum Spanning Trees, Implementation Issues | Chapter 4 of text book |
| Thursday, September 25 | Finish Union-Find for MST, Huffman Codes | Chapter 4 of text book |
| Tuesday, September 30 | Finish Huffman Codes. Introduction to Dynamic Programming | Chapters 4, 6 of text book |
| Thursday, October 2 | Dynamic Programming: Weighted Interval Scheduling, Longest Increasing Subsequence | Chapter 6 of text book |
| Tuesday, October 7 | Midterm 1: 7-9pm, 1404 Siebel | |
| Thursday, October 9 | Dynamic Programming: Recap, Edit Distance and Sequence Alignment | Chapter 6 of text book |
| Tuesday, October 14 | More Dynamic Programming: Chain Matrix Multiplication, All-Pairs Shortest Paths | Chapter 6 of text book |
| Thursday, October 16 | Some More Dynamic Programming: MWIS in Trees, Knapsack, TSP | Chapter 6 of text book |
| Friday, October 17 | Drop Deadline | |
| Tuesday, October 21 | Introduction to Network Flows | Chapter 7 of text book |
| Thursday, October 23 | Ford-Fulkerson Algorithm and Correctness | Chapter 7 of text book |
| Tuesday, October 28 | Applications of Network Flow | Chapter 8 of text book |
| Thursday, October 30 | More Applications of Network Flow | Chapter 8 of text book |
| Tuesday, November 4 | Introduction to Linear Programming | Lecture Notes |
| Thursday, November 6 | Polynomial Time Reductions | Chapter 8 |
| Tuesday, November 11 | Midterm 2: : 7-9pm, 1404 Siebel | |
| Thursday, November 13 | SAT, More Reductions, Definition of NP | Chapter 8 |
| Tuesday, November 18 | NP-Completeness, Cook-Levin Theorem, Circuit-SAT | Chapter 8 |
| Thursday, November 20 | NP-Completeness of Hamiltonian Cycle and 3-Coloring Problems | Chapter 8 |
| Tue/Thu, November 25, 27 | Turkey time | |
| Tuesday, December 2 | ||
| Thursday, December 4 | ||
| Tuesday, December 9 | Closing thoughts, review, course evaluation | |
| Wednesday, December 17 | Final: 7-10pm, 1404 Siebel |