Design and Analysis of Algorithms
When: 11:00am - 12:15pm MW
Where: ECCS 1B28
Professor: Rafael Frongillo, ECCS 111A
Office hours: 10:20am W outside CSEL, plus another time TBA each week
Mailing List: Piazza; sign up here
Syllabus, Assignments, Grades: Moodle
Textbook: Algorithms by Dasgupta, Papadimitriou, Vazirani
Schedule
| Date | Topic | Event | |
|---|---|---|---|
| Reading | Review: Chapters 0, 2.2, 2.3 |
||
| Video | |||
| Aug 22 | 1. Introduction + Mergesort | DUE: Moodle quiz, survey | |
| Reading | Chapter 2.4, Quicksort notes |
||
| Video | Quicksort analysis + 2 following; Review: basic probability |
||
| Aug 24 | 2. Median + Quicksort | ||
| Reading | Chapter 3 |
||
| Video | Graph representations and search + 7 following |
||
| Aug 29 | 3. Graphs: DFS, Topo sort, SCCs | ||
| Reading | Chapter 4 |
||
| Video | Dijkstra and the 3 following |
||
| Aug 31 | 4. BFS, Dijkstra, Bellman-Ford | ||
| Sep 5 | NO CLASS -- Labor day | ||
| Reading | Chapter 6 |
||
| Video | Sequence alignment and algorithm; Floyd-Warshall and following |
||
| Sep 7 | 5. Dynamic programming | DUE: Problem set 1 | |
| Video | |||
| Sep 12 | 6. Finish DP, Greedy algorithms | ||
| Video | P, Reductions, NP-completeness and 3 following |
||
| Reading | Chapter 5.4, 8, 9.2 |
||
| Sep 14 | 7. P vs NP, Greedy approximation | ||
| Sep 19 | Guest lecture by Jake Abernethy: Bipartite matching | ||
| Video | Kruskal and following |
||
| Reading | Chapter 5.1 |
||
| Sep 21 | 8. Minimum spanning trees | ||
| Video | ArrayStack and analysis |
||
| Sep 26 | 9. Amortized analysis | ||
| Video | Union-Find and following on path compression |
||
| Reading | Chapter 5.1.4, Karger notes from GA Tech |
||
| Sep 28 | 10. Union-Find, Randomized algorithms | DUE: Problem set 2 | |
| Reading | |||
| Oct 3 | 11. Karger-Stein, Hashing | ||
| Reading | Cool Bloom filter demo, Wikipedia |
||
| Oct 5 | 12. Bloom filters, Count-min sketch | ||
| Reading | |||
| Oct 10 | 13. Online learning | DUE: Project topic selection | |
| Reading | |||
| Oct 12 | 14. Online algorithms | Project topics assigned | |
| Oct 14 | DUE: Problem set 3 | ||
| Reading | |||
| Oct 17 | 15. Stable matching, game theory | ||
| Oct 19 | NO CLASS | ||
| Reading | |||
| Oct 24 | 16. Finish minimax, selfish routing | ||
| Reading | Chapter 7, LP Relaxations |
||
| Oct 26 | 17. Mechanism design, optimization | ||
| Oct 28 | DUE: Problem set 4 | ||
| Reading | Set cover IP and randomized rounding, some cool visualizations for IndepSet |
||
| Oct 31 | 18. Approximation algorithms via optimization | ||
| Nov 2 | 19. Midterm review | ||
| Nov 7 | Midterm | ||
| Reading | Extremely easy-to-follow notes on convex optimization (note: not easy to follow) |
||
| Nov 9 | 20. Convex optimization | ||
| Nov 14 |
21.
Zero-knowledge proofs
Matt Whitlock: Fortune's algorithm for Voronoi diagrams |
DUE: Problem set 5, end class around noon | |
| Nov 16 |
Jeff McMillan: B-Tree
Yi-Chen Kuo: Union-find Eirian Perkins: Fibonacci heap |
||
| Nov 28 |
Umakant Padhy: Ford-Fulkerson max-flow algorithm
Patrick Stover: Christofides' algorithm for traveling salesman problem |
end class around noon | |
| Nov 30 |
Max Hollingsworth: Fast Fourier Transform
Prasanna Kumar Srinivasachar: Simplex algorithm Jensen Dempsey: Nesterov's accelerated gradient descent |
||
| Dec 5 |
Ryan Hartsfield: Universal portfolio algorithm
William Diment: Differential privacy Megan Greening: Computational biology |
||
| Dec 7 |
Fan You: Resource constrained shortest path
Nikki Sanderson: State amalgamation problems Final words |
||
| Dec 9 | DUE: Project writeup | ||
Resources
Algorithms by Dasgupta, Papadimitriou, Vazirani -- textbook we will follow for part of the course.
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein ("CLRS") -- another classic algorithms reference.
Discrete Mathematics and Its Applications by Rosen -- nice introduction to proofs among other topics.
Tim Roughgarden's Coursera course Part 1 and Part 2 -- for brushing up on undergraduate material (enroll for free)
Mathematics for Computer Science, by Lehman, Leighton, Meyer. Chapters 1 and 2 especially.
Advice on writing proofs, by Cathy O'Neil. See also Book of Proof by Hammack. And another great reference, How to Prove It by Velleman.