| Date | Topics | Reading |
|---|---|---|
| Tuesday, August 24 | Administrivia, overview, motivation, graph basics, DFS | Chapters 1-3 from textbook, Jeff Erickson's notes on induction/proofs |
| Thursday, August 26 | DFS in Directed Graphs, Strong Connected Components, DAGs | Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
| Tuesday, August 31 | BFS, Single-source Shortest Paths | Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
| Thursday, September 2 | Shortest Paths with Negative Edge Lengths | Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
| Tuesday, September 7 | Reductions, Recursion, Divide and Conquer | Chapter 5, Jeff Erickson's notes on recurrences |
| Thursday, September 9 | Recurrences, Closest Pair, Quick Sort and Quick Selection | Chapter 5, Jeff Erickson's notes on recurrences |
| Tuesday, September 14 | Catch up lecture | |
| Thursday, September 16 | Exponentiation, Binary Search, Intro to Dynamic Programming | Chapter 6 |
| Tuesday, September 21 | Dynamic Programming: Longest Increasing Subsequence, Weighted Interval Scheduling | Chapter 6 |
| Thursday, September 23 | Dynamic Programming: Independent Sets in Trees, Edit Distance | Chapter 6 |
| Tuesday, September 28 | Dynamic Programming: Shortest Paths, Knapsack | Chapter 6 |
| Thursday, September 30 | Midterm 1: 7-9pm, 151 Everitt Lab | Topics |
| Tuesday, October 5 | Greedy Algorithms: Examples and Proof Techniques | Chapter 4 |
| Thursday, October 7 | Greedy Algorithms for Minimum Spanning Tree | Chapter 4 |
| Tuesday, October 12 | Introduction to Randomized Algorithms | Lecture Notes, Jeff Erickson's notes, Chapter 13 |
| Thursday, October 14 | Randomized Quick Sort and Selection | Lecture Notes, Jeff Erickson's notes, Chapter 13 |
| Friday, October 15 | Drop Deadline | |
| Tuesday, October 19 | Hash Tables | Lecture Notes, Jeff Erickson's notes |
| Thursday, October 21 | Introduction to Network Flows | Chapter 7 |
| Tuesday, October 26 | Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut | Chapter 7 |
| Thursday, October 28 | Applications of Network Flow: Disjoint Paths and Bipartite Matchings | Chapter 7 |
| Tuesday, November 2 | More Applications of Network Flow | Chapter 7 |
| Thursday, November 4 | Midterm 2: 7-9pm, 1404 Siebel | Topics |
| Tuesday, November 9 | Polynomial time Reductions | Chapter 8 |
| Thursday, November 11 | SAT and Definition of NP | Chapter 8 |
| Tuesday, November 16 | NP-Completeness, Circuit Sat and Cook-Levin Theorem | Chapter 8 |
| Thursday, November 18 | More NP-Complete Problems | Chapter 8 |
| Tue/Thu, November 23, 25 | Thanksgiving Break | |
| Tuesday, November 30 | P, NP, co-NP, Self Reductions | Chapter 8 |
| Thursday, December 2 | Catch up lecture | |
| Tuesday, December 7 | Heuristics, Closing thoughts | Chapter 9 in Dasgupta etal book |
| Tuesday, December 14 | Final Exam: 1.30-4.30pm in 1404 Siebel (1302 is overflow room) |