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