Design and Analysis of Algorithms
CSCI 5454, Spring 2016
Time: 10:00am - 10:50am MWF
Classroom: ECCS 1B12
Professor: Rafael Frongillo, ECCS 111A
Office hours: generally Mondays 11:00 to noon in the ECCS lobby (outside ECCS 111)
Webpage: https://www.cs.colorado.edu/~raf/teaching/5454-s16.html
Mailing List: Piazza; sign up here
Syllabus: PDF
Assignments and Grades: Moodle
Default textbook: Algorithms by Dasgupta, Papadimitriou, Vazirani
Schedule
| Date | Topic | Event | |
|---|---|---|---|
| Jan 11 | 0. Introduction | DUE: Moodle quiz, survey | |
| Reading | Review: Chapters 0, 2.2, 2.3 |
||
| Video | Review: Big-O definition, examples, and important variants; Mergesort algorithm and analysis |
||
| Jan 13 | 1. Mergesort | ||
| Reading | Chapter 2.4 |
||
| Jan 15 | 2. Median and Quicksort | ||
| Jan 18 | NO CLASS -- MLK day | ||
| Reading | Quicksort notes, Chapter 3 |
||
| Video | Quicksort analysis and the 2 videos which follow; |
||
| Jan 20 | 3. Quicksort take II; Graphs, DFS, Topological Sort | ||
| Reading | Chapter 4.1-4.5 |
||
| Video | Dijkstra and the 3 following |
||
| Jan 22 | 4. SCCs, BFS, Dijkstra | ||
| Reading | Chapters 4.6, 6.1 |
||
| Jan 25 | 5. Bellman-Ford, Intro to dynamic programming | ||
| Video | |||
| Reading | Chapter 6 |
||
| Jan 27 | 6. Dynamic programming in-class exercises | DUE: Problem set 1 | |
| Video | |||
| Jan 29 | 7. Debrief PS1, Greedy algorithms | ||
| Video | P, Reductions, NP-complete and follow-up |
||
| Reading | Chapter 8 |
||
| Feb 1 | 8. P and NP | ||
| Reading | Chapter 5.4, 9.2 |
||
| Feb 3 | 9. (Greedy) approximation algorithms | DUE: Project proposals | |
| Video | Cut property, Kruskal and its correctness; for fun, a fascinating video about open MST problems |
||
| Reading | Chapter 5.1 |
||
| Feb 5 | 10. Minimum spanning trees | Projects topics assigned | |
| Reading | |||
| Feb 8 | 11. Intro to amortized analysis | ||
| Video | Union-by-rank and 4 following (up to Hopcroft-Ullman analysis II) |
||
| Reading | Chapter 5.1.4 |
||
| Feb 10 | 12. Union-Find: iterated logarithm | ||
| Feb 12 | 13. Amortized analysis problems | ||
| Reading | |||
| Feb 15 | 14. Karger's min-cut algorithm | DUE: Problem set 2 | |
| Reading | |||
| Feb 17 | 15. Hashing, coupons, Bloom filters | ||
| Feb 19 | 16. Bloom and count-min | ||
| Feb 22 | NO CLASS -- out of town | ||
| Reading | |||
| Feb 26 | 17. Online learning | ||
| Reading | |||
| Feb 29 | 18. Hedge / exponential weights | ||
| Reading | |||
| Mar 2 | 19. Hedge analysis | DUE: Problem set 3 | |
| Reading | |||
| Mar 4 | 20. Hedge and actions | ||
| Reading | |||
| Mar 7 | 21. Secretary problem and online matching | ||
| Reading | |||
| Mar 9 | 22. Stable matching and kidney exchange | ||
| Reading | |||
| Mar 11 | 23. Nash, minimax, and Hedge | ||
| Reading | |||
| Mar 14 | 24. Finish minimax, start routing | ||
| Mar 16 | 25. More routing | ||
| Mar 18 | 26. Mechanism design | DUE: Problem set 4 | |
| Reading | Chapter 7, LP Relaxations |
||
| Mar 28 | 27. Optimization: IP and LP | ||
| Reading | Set cover IP and randomized rounding, some cool visualizations for IndepSet |
||
| Mar 30 | 28. In-class problems, start convex | ||
| Reading | Extremely easy-to-follow notes on convex optimization (note: not easy to follow) |
||
| Apr 1 | 29. Convex optimization | ||
| Apr 15 | DUE: Problem set 5 | ||
| Apr 29 | DUE: Project write-up | ||
April, week of | Monday | Wednesday | Friday |
4 | Merkle Patricia Tree, Sergey Frolov Fibonacci heap, Manjhunath Ravi | Fortune (Voronoi), Wayne Mitchell Iterated Closest Point, John Stetchschulte | Fast Multipole, Jay Stotsky Fast Fourier Transform, Patrick Heenan |
11 | Lecture: Zero-Knowledge Proofs | Sofic shift minimization, Harsh Ashar Incremental Computation, Trevor DiMartino | Christofides TSP, Yang Li Hungarian Algorithm, Carter Tillquist |
18 | Prediction markets, Aadish Gupta Differential privacy, Shruthi Sukumar | Online learning with Dropout, Parisa Rahimzadeh Learning in games, Andreas Wachter | Algebraic connectivity (small), Samantha Molnar Algebraic connectivity (big), Brett Israelsen |
25 | Nesterov AGD, Joey Azofeifa Simplex, Shirly Quesada | Ford-Fulkerson (max flow), Nachiket Bhagwat Bron-Kerbosch (max clique), Ram Das Diwakaran | Sudoku solver, Sushant Mittal Final words, Rafael Frongillo |
Resources
Algorithms by Dasgupta, Papadimitriou, Vazirani -- textbook we will follow for part of the course
Tim Roughgarden's Coursera course Part 1 and Part 2 -- for brushing up on undergraduate material
Mathematics for Computer Science, by Lehman, Leighton, Meyer. Chapters 1 and 2 especially.
Advice on writing proofs, by Cathy O'Neil.