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