by Dasgupta, Papadimitriou and Vazirani useful as references.
Homework will be due Friday 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 |
| September 29 |
Introductions, Stable Matchings
|
logistics, stable matchings, video |
| October 1 |
Homework 1
|
pdf, solutions |
| 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, solutions |
| 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, solutions |
| 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, solutions |
| 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
|
solutions |
| November 6 |
Homework 5
|
pdf, solutions |
| 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, solutions |
| 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, solutions |
| 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, solutions |
| December 8 |
Randomized algorithms (not on final)
|
pdf, video |
| December 10 |
Final review
|
pdf, video |
| December 13 |
Final Exam
|
|
| Date |
Topics |
Links |
| September 30 |
Introductions, Stable Matchings
|
logistics, MLvsAlgos, stable matchings, video |
| October 2 |
Stable Matchings (contd).
|
stable matchings, video |
| October 2 |
Homework 1
|
pdf, solutions |
| October 5 |
Asymptotic Analysis
|
analysis, video |
| October 7 |
Graphs
|
slides1, slides2, video |
| October 9 |
Breadth First Search
|
slides, video |
| October 10 |
Homework 2
|
pdf, solutions |
| October 12 |
Testing Bipartiteness and Dijkstra's Algorithm
|
BFS Applications, Dijkstra, video |
| October 14 |
Bellman Ford Algorithm
|
slides, video |
| October 16 |
Interval Scheduling
|
slides, video |
| October 17 |
Homework 3
|
pdf, solutions |
| October 19 |
Interval Partitioning and MST
|
slides, mst, mst2, video |
| October 21 |
MST (contd.)
|
mst, video |
| October 23 |
Greedy approximation algorithms
|
slides, video |
| October 23 |
Homework 4
|
pdf, solutions |
| October 26 |
Divide and Conquer, finding the closest pair.
|
slides1, slides2, video |
| October 28 |
Multiplication
|
slides2, video |
| October 30 |
Fast Fourier Transform
|
fft, video |
| October 31 |
Midterm (due November 6)
|
pdf |
| November 2 |
Linear time median
|
slides, video |
| November 4 |
Dynamic programming: scheduling
|
slides, video |
| November 6 |
Knapsack, RNA
|
slides, video |
| November 8 |
Homework 5
|
pdf, solutions |
| November 9 |
Edit distance, Longest increasing subsequence
|
slides, video |
| November 13 |
Homework 6
|
pdf, solutions |
| November 13 |
More dynamic programming
|
slides, video |
| November 16 |
Flows and Cuts
|
slides, slides2, video |
| November 18 |
Flows and Cuts (contd.)
|
slides, video |
| November 20 |
Homework 7
|
pdf, solutions |
| November 20 |
Floyd-Warshall Algorithm
|
slides, video |
| November 23 |
Capacity Scaling
|
slides, video |
| November 25 |
Bipartite matching
|
slides, video |
| November 30 |
Flow/cut applications
|
slides, video |
| December 3 |
P and NP
|
slides, video |
| December 5 |
P and NP (contd.)
|
slides, video |
| December 4 |
Homework 8
|
pdf |
| December 7 |
NP-complete problems
|
slides, video |
| December 9 |
NP-complete problems (contd.)
|
slides1, slides2, video |
| December 11 |
Randomized Algorithms, course summary (contd.)
|
slides1, slides2, video |
| December 11 |
Final (due Thursday, Decembe 17).
|
pdf |