My website has moved to https://raf.prof. If you are not redirected within 2 seconds, click here.

## 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)
Syllabus: PDF
Default textbook: Algorithms by Dasgupta, Papadimitriou, Vazirani

### Schedule

Date Topic Event
Jan 11 0. Introduction DUE: Moodle quiz, survey

Review: Chapters 0, 2.2, 2.3

Video

Review: Big-O definition, examples, and important variants; Mergesort algorithm and analysis

Jan 13 1. Mergesort

Chapter 2.4

Jan 15 2. Median and Quicksort
Jan 18 NO CLASS -- MLK day

Quicksort notes, Chapter 3

Video

Quicksort analysis and the 2 videos which follow;
Review: Basic probability, Graph search and the 7 videos which follow

Jan 20 3. Quicksort take II; Graphs, DFS, Topological Sort

Chapter 4.1-4.5

Video

Dijkstra and the 3 following

Jan 22 4. SCCs, BFS, Dijkstra

Chapters 4.6, 6.1

Jan 25 5. Bellman-Ford, Intro to dynamic programming
Video

Chapter 6

Jan 27 6. Dynamic programming in-class exercises DUE: Problem set 1
Video

Greedy algorithms

Jan 29 7. Debrief PS1, Greedy algorithms
Video

Chapter 8

Feb 1 8. P and NP

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

Chapter 5.1

Feb 5 10. Minimum spanning trees Projects topics assigned

Amortized analysis notes

Feb 8 11. Intro to amortized analysis
Video

Union-by-rank and 4 following (up to Hopcroft-Ullman analysis II)

Chapter 5.1.4

Feb 10 12. Union-Find: iterated logarithm
Feb 12 13. Amortized analysis problems

Notes from GA Tech

Feb 15 14. Karger's min-cut algorithm DUE: Problem set 2

Prof. Clauset's notes

Feb 17 15. Hashing, coupons, Bloom filters
Feb 19 16. Bloom and count-min
Feb 22 NO CLASS -- out of town

Experts

Feb 26 17. Online learning

Weighted majority

Feb 29 18. Hedge / exponential weights

Hedge analysis

Mar 2 19. Hedge analysis DUE: Problem set 3

Action setting

Mar 4 20. Hedge and actions

Luca Trevisan's notes

Mar 7 21. Secretary problem and online matching

Tim Roughgarden's notes

Mar 9 22. Stable matching and kidney exchange

Jake Abernethy's notes

Mar 11 23. Nash, minimax, and Hedge

Selfish routing

Mar 14 24. Finish minimax, start routing
Mar 16 25. More routing
Mar 18 26. Mechanism design DUE: Problem set 4

Chapter 7, LP Relaxations

Mar 28 27. Optimization: IP and LP

Set cover IP and randomized rounding, some cool visualizations for IndepSet

Mar 30 28. In-class problems, start convex

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 FrolovFibonacci heap, Manjhunath Ravi Fortune (Voronoi), Wayne MitchellIterated Closest Point, John Stetchschulte Fast Multipole, Jay StotskyFast Fourier Transform, Patrick Heenan 11 Lecture: Zero-Knowledge Proofs​ Sofic shift minimization, Harsh AsharIncremental Computation, Trevor DiMartino​ Christofides TSP, Yang LiHungarian Algorithm, Carter Tillquist 18 Prediction markets, Aadish GuptaDifferential privacy, Shruthi Sukumar​ Online learning with Dropout, Parisa RahimzadehLearning in games, Andreas Wachter Algebraic connectivity (small), Samantha MolnarAlgebraic connectivity (big), Brett Israelsen 25 Nesterov AGD, Joey AzofeifaSimplex, Shirly Quesada Ford-Fulkerson (max flow), Nachiket BhagwatBron-Kerbosch (max clique), Ram Das Diwakaran Sudoku solver, Sushant MittalFinal 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.

LaTeX resources and guides: one, two, three, four