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