by Dasgupta, Papadimitriou and Vazirani useful as references.
Homework will be due Sunday at midnight. It can be submitted a day late for a 25% penalty. Problem sets will be posted below. Remember: you can discuss homework with others in your class, but write all solutions by yourself. Submit your homework on
| Date |
Topics |
Links |
| March 27 |
Introductions, Stable Matchings
|
logistics, stable matchings, video |
| March 29 |
Stable matchings(contd), graphs
|
pdf, pdf, pdf, video |
| March 31 |
Graphs, Analysis
|
pdf, pdf, video |
| March 31 |
Homework 1
|
pdf
|
| April 3 |
Analysis and Breadth First Search
|
pdf, pdf, video |
| April 5 |
Breadth first Search and applications
|
pdf, video |
| April 7 |
Dijkstra's algorithm
|
pdf, video |
| April 8 |
Homework 2
|
pdf
|
| April 10 |
Bellman-Ford and greedy algorithms
|
pdf, pdf, video |
| April 12 |
Greedy algorithms and MST
|
pdf, pdf, video |
| April 14 |
MST
|
pdf, pdf, video |
| April 16 |
Homework 3
|
pdf
|
| April 14 |
MST
|
pdf, pdf, video |
| April 17 |
Greedy approximation algorithms
|
pdf, video |
| April 19 |
Divide and conquer
|
pdf, pdf, video |
| April 21 |
Karatsuba and Strassen
|
pdf, video |
| April 24 |
Homework 4
|
pdf
|
| April 24 |
FFT
|
pdf, video |
| April 26 |
Linear time median, Dynamic programming
|
pdf, pdf, video |
| April 28 |
Dynamic programming
|
pdf, video |
| May 1 |
Dynamic programming
|
pdf, pdf, video |
| April 30 |
Sample midterm
|
pdf, solutions |
| May 3 |
Midterm exam
|
| May 5 |
Homework 5
|
pdf
|
| May 5 |
Dynamic programming
|
pdf, video |
| May 8 |
Max-Flow, Min-Cut
|
pdf, video |
| May 10 |
Max-Flow, Min-Cut
|
pdf, video |
| May 12 |
Homework 6
|
pdf
|
| May 12 |
Capacity Scaling
|
pdf, pdf, video |
| May 15 |
Flow applications
|
pdf, video |
| May 17 |
Flow applications 2, Linear programming
|
pdf, pdf, video |
| May 19 |
Linear programming
|
pdf, video |
| May 21 |
Homework 7
|
pdf
|
| May 22 |
Linear programming (contd)
|
pdf, video |
| May 24 |
Simplex and Ellipsoid algorithms
|
pdf, video |
| May 26 |
NP
|
pdf, video |
| May 31 |
NP-completeness
|
pdf, pdf, video |
| June 2 |
Wrapping up, course summary
|
pdf, pdf, pdf, video |
| June 3 |
Sample Final exam |
sample final, solved sample |
| June 5 |
Final exam |
|
| Date |
Topics |
Links |
| September 29 |
Introductions, Stable Matchings
|
logistics, stable matchings, video |
| October 1 |
Homework 1
|
pdf
|
| October 1 |
Stable matchings (contd.)
|
pdf, video |
| October 4 |
Analysis, Graphs
|
pdf, pdf, pdf, video |
| October 6 |
Breadth first search
|
pdf, pdf, video |
| October 8 |
Graph search, Testing Bipartiteness
|
pdf, pdf, video |
| October 8 |
Homework 2
|
pdf |
| October 11 |
Graph search (contd.), Greedy Algorithms
|
pdf, pdf, video |
| October 13 |
Interval Scheduling, MST
|
pdf, pdf, video |
| October 15 |
MST (contd.)
|
pdf, pdf, pdf, video |
| October 15 |
Homework 3
|
pdf,
|
| October 18 |
Approximation algorithms (contd.), Divide and Conquer
|
pdf, pdf, pdf, video |
| October 20 |
Divide and Conquer (contd.)
|
pdf, video |
| October 22 |
Fast Fourier Transform
|
pdf, video |
| October 22 |
Homework 4
|
pdf
|
| October 25 |
Linear time median, Dynamic Programming
|
pdf, pdf, video |
| October 27 |
Dynamic Programming
|
pdf, video |
| October 27 |
More Dynamic Programming
|
pdf, video |
| November 1 |
Sample Midterm
|
pdf, solutions |
| November 1 |
Max-Flow, Min-Cut
|
pdf, video |
| November 3 |
Max-Flow, Min-Cut (contd.)
|
pdf, video |
| November 5 |
Midterm exam
|
| November 6 |
Homework 5
|
pdf
|
| November 8 |
Bipartite Matching
|
pdf, video |
| November 10 |
Applications of Flows/Cuts
|
pdf, video |
| November 12 |
Linear programming
|
pdf, video |
| November 12 |
Homework 6
|
pdf
|
| November 15 |
Linear programming (contd.)
|
pdf, video |
| November 17 |
Linear programming Duality
|
pdf, video |
| November 19 |
Games and Simplex
|
pdf, video |
| November 22 |
Ellipsoid algorithm
|
pdf, video |
| November 29 |
Wrapping up linear programming
|
pdf, video |
| November 26 |
Homework 7
|
pdf
|
| December 1 |
NP
|
pdf, video |
| December 3 |
NP-completeness
|
pdf, video |
| December 4 |
Homework 8
|
pdf |
| December 5 |
NP-completeness of Vertex Cover, Hamiltonian cycle
|
pdf, video |
| December 6 |
Sample final
|
pdf
|
| December 8 |
Randomized algorithms (not on final)
|
pdf, video |
| December 10 |
Final review
|
pdf, video |
| December 13 |
Final Exam
|
|