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

Review: big-oh + 2 following; mergesort + 2 following

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

Greedy algorithms

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

Prof. Clauset's notes

Oct 3 11. Karger-Stein, Hashing
Reading

Cool Bloom filter demo, Wikipedia

Oct 5 12. Bloom filters, Count-min sketch
Reading

Experts, Weighted majority, Hedge analysis, Action setting

Oct 10 13. Online learning DUE: Project topic selection
Reading

Luca Trevisan's notes

Oct 12 14. Online algorithms Project topics assigned
Oct 14 DUE: Problem set 3
Reading

Tim Roughgarden's notes, Jake Abernethy's notes

Oct 17 15. Stable matching, game theory
Oct 19 NO CLASS
Reading

Selfish routing

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.

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