| Date | Topics | Reading |
|---|---|---|
| Tuesday, January 17 |
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 19 |
DFS in Directed Graphs, Strong Connected Components, DAGs | Chapter 3 of Dasgupta etal book |
| Tuesday, January 24 |
BFS, Single-source Shortest Paths | Chapter 3 of Dasgupta etal book |
| Thursday, January 26 |
Shortest Paths with Negative Edge Lengths | Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
| Tuesday, January 31 |
Catch up lecture | |
| Thursday, February 2 |
Reductions, Recursion, Divide and Conquer | Chapter 2 of Dasgupta etal, Chapter 5 of Kleinberg-Tardos, Jeff Erickson's notes on recurrences |
| Tuesday, February 7 |
Recurrences, Closest Pair, Quick Sort and Quick Selection | Chapter 2 of Dasgupta etal, Chapter 5 of Kleinberg-Tardos, Jeff Erickson's notes on recurrences |
| Thursday, February 9 |
Exponentiation, Binary Search, Intro to Dynamic Programming | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Tuesday, February 14 |
Dynamic Programming: Longest Increasing Subsequence, Interval Scheduling | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Thursday, February 16 |
Dynamic Programming: Independent Set in Trees, Edit Distance | Chap. 6 of Dasgupta etal, Chap 6 of Kleinberg-Tardos, Jeff Erickson's notes on DP |
| Tuesday, February 21 |
Dynamic Programming: Shortest Paths and Knapsack | |
| Thursday, February 23 |
Midterm 1: 7-9pm, Everitt 269 and 151 | |
| Tuesday, February 28 |
Greedy Algorithms: Examples and Proof Techniques | Chapter 5 of Dasgupta etal, Chapter 4 of Kleinberg-Tardos |
| Thursday, March 1 |
Greedy Algorithms for Minimum Spanning Tree | Chapter 5 of Dasgupta etal, Chapter 4 of Kleinberg-Tardos |
| Tuesday, March 3 |
Introduction to Randomized Algorithms | Lecture Notes, Jeff Erickson's notes |
| Thursday, March 8 |
Randomized Quick Sort and Selection | Lecture Notes, Jeff Erickson's notes |
| Friday, March 9 | Drop Deadline | |
| Tuesday, March 13 |
Hash Tables | Lecture Notes, Jeff Erickson's notes |
| Thursday, March 15 |
Introduction to Network Flows | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| March 19-March 23 | Spring Break | |
| Tuesday, March 27 |
Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Thursday, March 29 |
Applications of Network Flow: Disjoint Paths and Bipartite Matchings | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Tuesday, April 3 |
More Applications of Network Flow | Lecture Notes, Chapter 7 of Kleinberg-Tardos |
| Thursday, April 5 |
Midterm 2: 7-9pm, Everitt 269 and 151 | |
| Tuesday, April 10 |
Polynomial time Reductions | |
| Thursday, April 12 |
SAT and Definition of NP | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Tuesday, April 17 |
NP-Completeness, Circuit Sat and Cook-Levin Theorem | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Thursday, April 19 |
More NP-Complete Problems | Chapter 8 of Dasgupta etal and Chapter 8 of Kleinberg-Tardos |
| Tuesday, April 24 |
P, NP, co-NP, Self Reductions | |
| Thursday, April 26 |
Introduction to Linear Programming | Chapter 7 of Dasgupta etal book |
| Tuesday, May 1 |
Heuristics, Closing Thoughts | Chapter 9 of Dasgupta etal book, Chapters 10,11,12 of Kleinberg-Tardos |
| Monday, May 7 |
Final Exam: 1:30-4:30 pm, Gregory Hall 112 |