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;
Review: Basic probability, Graph search and the 7 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

Sequence alignment and algorithm

Reading

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

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

Amortized analysis notes

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

Notes from GA Tech

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

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
Reading

Experts

Feb 26 17. Online learning
Reading

Weighted majority

Feb 29 18. Hedge / exponential weights
Reading

Hedge analysis

Mar 2 19. Hedge analysis DUE: Problem set 3
Reading

Action setting

Mar 4 20. Hedge and actions
Reading

Luca Trevisan's notes

Mar 7 21. Secretary problem and online matching
Reading

Tim Roughgarden's notes

Mar 9 22. Stable matching and kidney exchange
Reading

Jake Abernethy's notes

Mar 11 23. Nash, minimax, and Hedge
Reading

Selfish routing

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.

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