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

• Videos - intro
• Notes - intro

Module 1: Combinatorial and Graph Algorithms

Lecture 2: Depth-First-Search, Topological Sort

• Videos - DFS
• Notes - DFS

Lecture 3: Shortest Paths

• Videos - shortest paths
• Notes - shortest paths

Lecture 4: Dynamic Programming

• Videos - DP
• Notes - DP
• Additional notes - knapsack

Lecture 5: Max Flow and Min Cut

• Videos - max flow
• Notes - max flow

Module 2: Approximation, Online, and Randomized Algorithms

Lecture 6: Intro to Approximation Algorithms

• Videos - approximation algorithms
• Notes - approximation algorithm

Lecture 7: Intro to Online Algorithms

• Videos - online algorithms
• Notes - online algorithm

Lecture 8: Intro to Randomized Algorithms

• Videos - randomized algorithms
• Notes - randomized algorithm

Lecture 9: Hash Tables

• Videos - hash tables
• Notes - hash tables

Lecture 10: Streaming Algorithms

• Videos - streaming
• Notes - streaming

Module 3: Continuous, Linear, and Convex Methods

Lecture 11: Random Walks on Graphs

• Videos - random walks
• Notes - random walks

Lecture 12: Johnson-Lindenstrauss Transform

• Videos - Johnson-Lindenstrauss
• Notes - Johnson-Lindenstrauss

Lecture 13: Singular Value Decomposition

• Videos - SVD
• Notes - SVD

Lecture 14: Online No-Regret Learning

• Notes - no-regret learning

Lecture 15: Zero-Sum Games

• Notes - zero-sum games

Lecture 16: Linear Programming

• Notes - 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.

---