| |
Date |
Lecture Topic |
Homework/Exams |
| Week 1 |
7/5 |
Introduction, Stable Matching
Chapter 1.1 |
HW1 out |
| 7/6 |
Greedy Algorithms - Interval Scheduling: The Greedy Algorithm Stays Ahead
Chapter 4.1 |
|
| 7/7 |
Greedy Algorithms - Scheduling to Minimize Lateness: An Exchange Argument
Chapter 4.2 |
|
| 7/8 |
Greedy Algorithms - Minimum Spanning Trees
Chapter 4.4 |
HW1 due, HW2 out |
| Week 2 |
7/11 |
Divide and Conquer - Recurrence Relations, Merge Sort, and Counting Inversions
Chapters 5.1-5.3 |
|
| 7/12 |
Divide and Conquer - Finding the Closest Pair of Points, Integer Multiplication, and Linear Time Selection
Chapter 5.4-5.5
Link to CMU lecture notes:
Linear Time Selection
|
HW2 due, HW3 (short) out |
| 7/13 |
Dynamic Programming - Weighted Interval Scheduling
Chapters 6.1-6.3 |
|
| 7/14 | Dynamic Programming - Longest Increasing Subsequence
Dynamic Programming Handout 6.2 |
|
| 7/15 |
Dynamic Programming - Edit Distance
Dynamic Programming Handout 6.3 |
HW4 due |
| Week 3 |
7/18 |
Dynamic Programming - Knapsack
Chapter 6.4 and
Dynamic Programming Handout 6.4 |
HW3 due, HW4 out |
| 7/19 |
No lecture - Prelim 1
Three times: 8:00am-10:00am, 8:30am-10:30am, 2:00pm-4:00pm |
HW5 out |
| 7/20 |
Dynamic Programming - Shortest Paths in Graphs
Chapter 6.8 and Dynamic Programming Handout 6.6 |
|
| 7/21 |
Network Flow - The Ford-Fulkerson Algorithm
Chapter 7.1 |
|
| 7/22 |
Network Flow - The Max-flow Min-cut Theorem and Correctness of Ford-Fulkerson
Chapter 7.2 & 7.3 |
HW5 due, HW6 out |
| Week 4 |
7/25 |
Network Flow - Reducing to the Max-flow Problem: Bipartite Matching and Survey Design
Chapters 7.5 & 7.8 (modified to be a reduction to max-flow not circulations) |
|
| 7/26 |
Network Flow - Reducing to the Max-flow Problem: Baseball Elimination
Chapters 7.12 |
HW6 due, HW7 out |
| 7/27 |
Network Flow - Reducing to the Min-cut Problem: Image Segmentation and Project Selection
Chapters 7.10 & 7.11 |
|
| 7/28 |
NP completeness - First Reductions: SAT, Vertex Cover, Independent Set
Chapters 8.1 and 8.2 |
|
| 7/29 |
NP completeness - The complexity class NP and Definition of NP-completeness
Chapter 8.3 and 8.4 |
HW7 due, HW8 out |
| Week 5 |
8/1 |
NP completeness - Sequencing Problems
Chapter 8.5 |
|
| 8/2 |
NP completeness - Numerical Problems
Chapter 8.8 |
|
| 8/3 |
NP completeness - The flow saturation problem |
HW8due, Prelim2 out |
| 8/4 |
Theory of Computation: Turing Machines
Lecture notes on Turing machines |
|
| 8/5 |
Theory of Computation: Decideability
Lecture notes on Turing machines |
Prelim2 due at 9:00PM, HW9 out |
| Week 6 |
8/8 |
Theory of Computation: The Halting Problem and Rice's Theorem
Lecture notes on Turing machines |
|
| 8/9 |
Finish Undecidability
Approximation Algorithms: linear programming based approximation algorithms for vertex cover |
|
| 8/10 |
LP Duality and LP based approximation algorithms for vertex cover continued
Randomized max-SAT approximation algorithm |
HW9 due |
| 8/11 |
Review |
|
| 8/12 |
No Lecture
Final Exam is from 8:30-11:30am or 1:00-4:00pm |
|