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.

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 (add code 2RWYEZ).

### Sample Schedule

You can use the discussion board here to ask questions.

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 (add code 2RWYEZ).

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 | |

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) | |

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 | |

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). |