# A Course in Graduate Algorithms

## Lecture Notes and Videos

Developed by Bo Waggoner for the University of Colorado, Boulder CSCI 5454: Design and Analysis of Algorithms.

Last updated: 2022.

Sample class: CSCI 5454, Fall 2022.

This page contains lecture notes and videos for a rigorous, proof-based second course in algorithms. It is intended to also be accessible (with work) to students who are a bit rusty or never took undergrad algorithms but have programming and mathematics backgrounds. The first module contains classical material usually encountered in undergrad, while the next two modules introduce more advanced topics.

The "lectures" are different lengths; some are usually covered in one day while others take two or three.

Notes and videos cover the same material, with the notes having a bit more detail (e.g. some proofs omitted from the videos).

Lecture 1: Intro, Word-RAM Model, Big-O

### Module 1: Combinatorial and Graph Algorithms

Lecture 2: Depth-First-Search, Topological Sort

Lecture 3: Shortest Paths

Lecture 4: Dynamic Programming

Lecture 5: Max Flow and Min Cut

### Module 2: Approximation, Online, and Randomized Algorithms

Lecture 6: Intro to Approximation Algorithms

Lecture 7: Intro to Online Algorithms

Lecture 8: Intro to Randomized Algorithms

Lecture 9: Hash Tables

Lecture 10: Streaming Algorithms

### Module 3: Continuous, Linear, and Convex Methods

Lecture 11: Random Walks on Graphs

Lecture 12: Johnson-Lindenstrauss Transform

Lecture 13: Singular Value Decomposition

Lecture 14: Online No-Regret Learning

Lecture 15: Zero-Sum Games

Lecture 16: Linear Programming

Sample schedule for 15-week semester, two classes per week:

• Week 1: Lecture 1-2. Intro, Big-O, DFS, Topological sort.
• Week 2: Lecture 3-4. Shortest paths, dynamic programming (day 1).
• Week 3: Lecture 4-5. Dynamic programming (day 2), max flow (day 1).
• Week 4: Lecture 5. Max flow (days 2 and 3).
• Week 5: Lecture 6-7. Approximation and online algorithms.
• Week 6: Lecture 8. Randomized algorithms (days 1 and 2).
• Week 7: Lecture 8. Randomized algorithms (day 3), midterm review.
• Week 8: Midterm, lecture 9. Hash tables.
• Week 9: Lecture 10-11. Streaming algorithms, random walks (day 1).
• Week 10: Lecture 11. Random walks (days 2 and 3).
• Week 11: Lecture 12-13. Johnson-Lindenstrauss, singular value decomposition (day 1).
• Week 12: Lecture 13-14. SVD (day 2), online learning.
• Week 13: Lecture 15. Zero-sum games and minimax (day 1).
• Week 14: Lecture 15-16. Zero-sum games (day 2), linear programming (day 1).
• Week 15: Lecture 16. Linear programming (day 2), review, final exam.