| Date | Topics | Reading |
|---|---|---|
| Thursday, August 23 | Administrivia, overview, primality, stable marriage | Chapters 1,2,3 from textbook |
| Tuesday, August 28 | Greedy Algorithms: interval selection and partitioning, scheduling to minimize lateness | 4.1, 4.2 from textbook |
| Thursday, August 30 | Greedy Algorithms contd: Two Simple Problems and MST | 4.3-4.5 from textbook |
| Tuesday, September 4 | Data Structures for MST Computation: Priority Queues and Union-Find | 2.5, 4.5, 4.6 |
| Thursday, September 6 | Huffman Codes via Recursion | 4.8 |
| Tuesday, September 11 | Merge Sort, Recurrences, Selection | 5.1, 5.2 |
| Thursday, September 13 | Closest Pair, Multiplication, Matrix Multiplication | 5.4,5.5 |
| Tuesday, September 18 | Convolutions, Polynomials, Fast Fourier Transform | 5.6 |
| Thursday, September 20 | DFS, Connectivity in Directed Graphs | 3.5, 3.6, lecture notes |
| Tuesday, September 25 | Finding all Strong Components using DFS | Chapter 3 in Dasgupta etal book |
| Thursday, September 27 | BFS and Dijkstra's Algorithm for Shortest Paths | 3.2--3.4, 4.4 |
| Tuesday, October 2 | Midterm 1: 7-9pm, Location: Main Library Room 66 | TBA |
| Thursday, October 4 | Shortest Paths with Negative Lengths: Bellman-Ford Algorithm | Lecture notes, Chapter 6.8--6.10 |
| Tuesday, October 9 | Dynamic Programming: Introduction | Chapter 6 |
| Thursday, October 11 | Dynamic Programming: More Examples | Chapter 6 |
| Friday, October 12 | Drop Deadline | TBA |
| Tuesday, October 16 | Dynamic Programming: Some More Examples | Chapter 6 |
| Thursday, October 18 | Network Flows: Introduction | Chapter 7 |
| Tuesday, October 23 | Network Flow Algorithms | Chapter 7 |
| Thursday, October 25 | Applications of Network Flows | Chapter 7 |
| Tuesday, October 30 | Circulations, lower bounds on flow and Applications | Chapter 7 |
| Thursday, November 1 | Introduction to Linear Programming | Lecture Notes |
| Tuesday, November 6 | Midterm 2: 7-9pm, Location: Main Library Room 66 | TBA |
| Thursday, November 8 | Polynomial Time Reductions | Chapter 8 |
| Tuesday, November 13 | Reductions and NP | Chapter 8 |
| Thursday, November 15 | NP-Completeness and Cook-Levin Theorem | Chapter 8 |
| Tue/Thu, November 20, 22 | Turkey time | TBA |
| Tuesday, November 27 | More NP-Complete Problems | Chapter 8 |
| Thursday, November 29 | co-NP, Self-Reducibility, and Approximation Algorithms | Chapter 8, Chapter 11 |
| Tuesday, December 4 | More Approximation Algorithms | Chapter 11 |
| Thursday, December 6 | Closing thoughts, review, course evaluation | |
| Tuesday, December 11 | Final, 1.30--4.30pm: 1404 Siebel Center | Lecture Notes, Chapters 1-9 of Text Book |