| Date | Topics | Reading |
|---|---|---|
| Tuesday, January 21 |
Administrivia, overview, motivation, graph basics, DFS | Chapter 0, section 1.1 and 1.2 from Dasgupta etal, Jeff Erickson's notes on induction/proofs |
| Thursday, January 23 |
DFS in Directed Graphs, Strong Connected Components, DAGs | Chapter 3 of Dasgupta etal book |
| Tuesday, January 28 |
BFS, Single-source Shortest Paths | Chapter 3 of Dasgupta etal book |
| Thursday, January 30 |
Shortest Paths with Negative Edge Lengths | Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
| Tuesday, February 4 |
Reductions, Recursion, Divide and Conquer | Chapter 2 of Dasgupta etal, Chapter 5 of Kleinberg-Tardos, Jeff Erickson's notes on recurrences |
| Thursday, February 6 |
Recurrences, Closest Pair, Quick Sort and Quick Selection | Chapter 2 of Dasgupta etal, Chapter 5 of Kleinberg-Tardos, Jeff Erickson's notes on recurrences |
| Tuesday, February 11 |
Exponentiation, Binary Search, Intro to Dynamic Programming | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Thursday, February 13 |
Dynamic Programming: Longest Increasing Subsequence, Interval Scheduling | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Tuesday, February 18 |
Dynamic Programming: Independent Set in Trees, Edit Distance | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Thursday, February 20 |
Dynamic Programming: Shortest Paths and Knapsack | |
| Tuesday, February 25 |
Greedy Algorithms: Examples and Proof Techniques | Chapter 5 of Dasgupta etal, Chapter 4 of Kleinberg-Tardos |
| Thursday, February 27 |
Midterm 1: 7-9pm, 1MH 103 and 1BEV 180 | |
| Tuesday, March 4 |
Greedy Algorithms for Minimum Spanning Tree | Chapter 5 of Dasgupta etal, Chapter 4 of Kleinberg-Tardos |
| Thursday, March 6 |
Introduction to Randomized Algorithms | Lecture Notes, Jeff Erickson's notes |
| Tuesday, March 11 |
Randomized Quick Sort and Selection | Lecture Notes, Jeff Erickson's notes |
| Thursday, March 13 |
Hash Tables | Lecture Notes, Jeff Erickson's notes |
| Friday, March 14 | Drop Deadline | |
| Tuesday, March 18 |
No lecture due to instructor travel | |
| Thursday, March 20 |
Introduction to Network Flows | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| March 24 - 28 | Spring Break | |
| Tuesday, April 1 |
Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Thursday, April 3 |
Applications of Network Flow: Disjoint Paths and Bipartite Matchings | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Tuesday, April 8 |
More Applications of Network Flow | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Thursday, April 10 |
Midterm 2: 7-9pm, 1MH 103 and 1BEV 180 | |
| Tuesday, April 15 |
Polynomial time Reductions | |
| Thursday, April 17 |
SAT and Definition of NP | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Tuesday, April 22 |
NP-Completeness, Circuit Sat and Cook-Levin Theorem | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Thursday, April 24 |
More NP-Complete Problems | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Tuesday, April 29 |
P, NP, co-NP, Self Reductions | |
| Thursday, May 1 |
Introduction to Linear Programming | Chapter 7 of Dasgupta etal book |
| Tuesday, May 6 |
Heuristics, Closing Thoughts | Chapter 9 of Dasgupta etal book, Chapters 10,11,12 of Kleinberg-Tardos |
| Friday, May 9 |
Final Exam 7-10pm, 1DCL-1320, 1MSEB-100 |