You may find
this text by Kleinberg and Tardos, and
this text by Dasgupta, Papadimitriou and Vazirani useful as references.
You can use the discussion board
here to ask questions. Signup for the discussion board
here.
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
gradescope (use code MVVNZE).
| 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 |
The old Schedule from Winter 2020
| Date |
Topics |
Links |
| January 6 |
Logistics, Stable Matchings
|
logistics, slides, video |
| January 8 |
Stable Matchings (contd.), Asymptotics
|
slides1, slides2, video |
| January 10 |
Homework 1
|
pdf, solutions |
| January 10 |
Graphs
|
slides1, slides2, video |
| January 13 |
Graphs 2
|
slides1, video |
| January 15 |
Graph Search
|
slides1, video |
| January 17 |
Dijkstra's Algorithm
|
slides1, video |
| January 17 |
Homework 2
|
pdf, solutions |
| January 22 |
Testing bipartitness, Bellman-Ford
|
slides1, slides2, video |
| January 24 |
Homework 3
|
pdf, solutions |
| January 24 |
Greedy Interval Scheduling
|
slides, video |
| January 27 |
Minimum spanning trees
|
slides1, slides2, video |
| January 29 |
Greedy Approximation algorithms
|
slides, video |
| January 31 |
Homework 4
|
pdf, solutions |
| January 31 |
Divide and Conquer
|
slides1, slides2, video |
| February 3 |
Solving Recurrences
|
slides, video |
| February 5 |
Fast Fourier Transform
|
slides, video |
| February 7 |
Sample Midterm
|
pdf, solutions |
| February 7 |
Median and Dynamic Programming
|
slides1, slides2, video |
| February 10 |
Knapsack, RNA structure and Edit Distance
|
slides, video |
| February 12 |
More Dynamic Programming
|
slides, video |
| February 14 |
Homework 5
|
pdf, solutions |
| February 19 |
More Dynamic Programming
|
slides, video |
| February 21 |
Homework 6
|
pdf, solutions |
| February 21 |
Max Flow and Min Cut
|
pdf, video |
| February 24 |
Ford-Fulkerson Algorithm
|
pdf, video |
| February 26 |
Capacity Scaling
|
pdf, video |
| February 28 |
Max Flow Applications
|
pdf, video |
| February 28 |
Homework 7
|
pdf, solutions |
| March 2 |
Max Flow Applications
|
pdf, video |
| March 4 |
NP
|
pdf, video |
| March 6 |
NP-completeness
|
pdf, video |
| March 7 |
Homework 8
|
pdf |
| March 9 |
Independent Set, Hamiltonian Cycle
|
pdf, video |
| March 11 |
Randomized Algorithms (not on final)
|
pdf, video |
pppp
| March 11 |
Practice Problems
p |
pdf |
| March 16 |
Final
|
pdf |