CS 566 – Efficient Algorithms (Winter 2025-26): videos
All lecture videos · module page · YouTube playlist
102 videos, 34 h 13 min
| Video | Date | Title | Length | Transcript |
|---|---|---|---|---|
| 0-1 | 2025-10-13 | Welcome, teaching mode, overview, assessment, academic integity, Campuswire, Slido, exam question gallery | 42:01 | transcript & video |
| 0-1 | 2025-10-13 | §1.1 Random shuffle motivation | 12:52 | YouTube |
| 0-2 | 2025-10-13 | §1.2 Proof templates | 16:15 | YouTube |
| 0-3 | 2025-10-13 | §1.3 Mathematical induction | 7:04 | YouTube |
| 0-4 | 2025-10-14 | §1.4 Correctness proofs | 35:03 | YouTube |
| 2-1 | 2025-10-14 | §2.1 Algorithm analysis | 13:09 | YouTube |
| 2-2 | 2025-10-14 | §2.2 The word-RAM model | 20:53 | YouTube |
| 2-3 | 2025-10-20 | §2.3 Asymptotics and Big-Oh | 34:09 | YouTube |
| 2-4 | 2025-10-20 | §2.4 Asymptotic pitfalls | 12:42 | YouTube |
| 2-5 | 2025-10-20 | §2.5 Teaser: Maximum subarray problem | 30:52 | YouTube |
| 2-6 | 2025-10-21 | §2.6 Teaser: Algorithm design; efficient solutions for the maximum subarray problem | 23:19 | YouTube |
| 3-0 | 2025-10-21 | §3.0 word-RAM vs Python & Java | 8:37 | YouTube |
| 3-1 | 2025-10-21 | §3.1 ADTs, Stacks and Queues | 16:07 | YouTube |
| 3-2 | 2025-10-21 | §3.2 Resizable arrays | 28:32 | YouTube |
| 3-3 | 2025-10-27 | §3.2 Resizable arrays deamortized & optimal space | 10:20 | YouTube |
| 3-4 | 2025-10-27 | §3.3 Priority queues & binary heaps | 16:26 | YouTube |
| 3-5 | 2025-10-27 | §3.4 Operations on binary heaps | 17:56 | YouTube |
| 3-6 | 2025-10-27 | §3.5 Symbol tables | 7:07 | YouTube |
| 3-7 | 2025-10-29 | §3.6 Binary search trees | 23:10 | YouTube |
| 3-8 | 2025-11-03 | §3.6 Binary search trees average case analysis | 20:35 | YouTube |
| 3-7 | 2025-11-03 | §3.7 Ordered symbol tables | 15:32 | YouTube |
| 3-8 | 2025-11-03 | §3.8 Balanced binary search trees recap | 4:50 | YouTube |
| 3-9 | 2025-11-03 | §3.9 Hashing recap | 12:48 | YouTube |
| 4-0 | 2025-11-03 | §4.0 Sorting introduction | 8:36 | YouTube |
| 4-1 | 2025-11-03 | §4.1 Mergesort | 11:32 | YouTube |
| 4-2 | 2025-11-04 | §4.2 Quicksort | 28:27 | YouTube |
| 4-3 | 2025-11-05 | §4.3 Comparison-based lower bound | 21:25 | YouTube |
| 4-4 | 2025-11-05 | §4.4 Integer sorting | 15:18 | YouTube |
| 4-5 | 2025-11-05 | §4.5 Adaptive sorting | 9:16 | YouTube |
| 4-6 | 2025-11-10 | §4.5 Adaptive sorting & Peeksort | 26:06 | YouTube |
| 4-7 | 2025-11-10 | §4.6 Python’s list sort & Powersort | 16:04 | YouTube |
| 5-1 | 2025-11-10 | §5.1 Divide & Conquer algorithms | 4:36 | YouTube |
| 5-2 | 2025-11-10 | §5.1 Divide & Conquer recurrences, Master Theorem | 29:42 | YouTube |
| 5-3 | 2025-11-11 | §5.2 Order statistics, quickselect | 38:09 | YouTube |
| 5-4 | 2025-11-11 | §5.3 Linear-time selection, median of medians | 16:34 | YouTube |
| 5-5 | 2025-11-11 | §5.4 Fast multiplication: Karatsuba and Strassen | 24:45 | YouTube |
| 5-6 | 2025-11-17 | §5.5 Majority: divide and conquer, Boyer-Moore MJRTY | 19:38 | YouTube |
| 5-7 | 2025-11-17 | §5.6 Closest pair of points in the plane | 34:24 | YouTube |
| 6-1 | 2025-11-17 | §6.1 String definitions | 11:31 | YouTube |
| 6-2 | 2025-11-17 | §6.2 Brute force string matching | 7:09 | YouTube |
| 6-3 | 2025-11-17 | §6.3 String matching with finite automata | 8:06 | YouTube |
| 6-4 | 2025-11-17 | §6.3 String matching with finite automata (part 2) | 8:06 | YouTube |
| 6-5 | 2025-11-18 | §6.4 Constructing string matching DFAs | 36:01 | YouTube |
| 6-6 | 2025-11-18 | §6.5 The Knuth-Morris-Pratt algorithm | 26:14 | YouTube |
| 6-7 | 2025-11-19 | §6.6 The Boyer-Moore algorithm | 15:47 | YouTube |
| 6-8 | 2025-11-24 | §6.7 The Rabin-Karp algorithm | 21:04 | YouTube |
| 7-1 | 2025-11-24 | §7.1 Compression context: terminology, Kolmogorov complexity | 26:23 | YouTube |
| 7-2 | 2025-11-24 | §7.2 Character Encodings | 27:53 | YouTube |
| 7-3 | 2025-11-25 | §7.3 Huffman codes | 26:16 | YouTube |
| 7-4 | 2025-11-25 | §7.4 Entropy and Huffman codes | 38:36 | YouTube |
| 7-5 | 2025-11-25 | §7.5 Run-length encoding | 17:55 | YouTube |
| 7-6 | 2025-12-01 | §7.6 Lempel-Ziv-Welch encoding | 19:38 | YouTube |
| 7-7 | 2025-12-01 | §7.7 Lempel Ziv Welch decoding | 20:35 | YouTube |
| 7-8 | 2025-12-01 | §7.8 Move-to-front transform | 16:00 | YouTube |
| 7-9 | 2025-12-01 | §7.9 Burrows-Wheeler transform | 23:27 | YouTube |
| 7-10 | 2025-12-02 | §7.10 Inverse BWT | 18:00 | YouTube |
| 8-1 | 2025-12-02 | §8.1 Arithmetic coding | 22:06 | YouTube |
| 8-2 | 2025-12-02 | §8.2 Practical arithmetic beyond trits | 16:13 | YouTube |
| 8-3 | 2025-12-02 | §8.3 Practical arithmetic coding | 10:55 | YouTube |
| 8-4 | 2025-12-02 | §8.4 Error correcting codes introduction | 8:47 | YouTube |
| 8-5 | 2025-12-08 | §8.5 Lower bounds for error correcting codes | 23:16 | YouTube |
| 8-6 | 2025-12-08 | §8.6 Hamming codes | 29:13 | YouTube |
| 9-1 | 2025-12-08 | §9.1 Introduction & Graph Theory Definitions | 21:20 | YouTube |
| 9-2 | 2025-12-09 | §9.2 Graph Representations | 10:03 | YouTube |
| 9-3 | 2025-12-09 | §9.3 Graph Traversal | 21:20 | YouTube |
| 9-4 | 2025-12-09 | §9.4 BFS | 21:57 | YouTube |
| 9-5 | 2025-12-09 | §9.5 DFS | 13:46 | YouTube |
| 9-6 | 2025-12-09 | §9.6 DFS Lemmas | 6:36 | YouTube |
| 9-7 | 2025-12-15 | §9.6 DFS edge types, Cycle detection | 39:27 | YouTube |
| 9-8 | 2025-12-15 | §9.7 Hierholzer’s algorithm, Kosaraju-Sharir | 39:00 | YouTube |
| 9-9 | 2025-12-16 | §9.8 The max flow problem | 27:06 | YouTube |
| 9-10 | 2025-12-16 | §9.9 The Ford-Fulkerson method | 38:54 | YouTube |
| 9-11 | 2025-12-17 | §9.10 The Edmonds-Karp algorithm | 7:48 | YouTube |
| 9-12 | 2024-01-12 | §9.10 Edmonds-Karp analysis | 21:53 | YouTube |
| 10-1 | 2026-01-12 | §10.1 Parallel computation, PRAM | 24:49 | YouTube |
| 10-2 | 2026-01-13 | §10.2 Parallel string matching | 18:30 | YouTube |
| 10-3 | 2026-01-13 | §10.3 Parallel primitives, prefix sum, compaction | 32:30 | YouTube |
| 10-4 | 2026-01-13 | §10.4 Parallel sorting | 21:59 | YouTube |
| 11-1 | 2026-01-13 | §11.1 Greedy Introduction | 9:49 | YouTube |
| 11-2 | 2026-01-13 | §11.2 The Making-changing problem part 1 | 4:28 | YouTube |
| 11-3 | 2026-01-19 | §11.2 The Making-changing problem part 2 | 16:50 | YouTube |
| 11-4 | 2026-01-19 | §11.3 Minimum Spanning Trees: Kruskal’s Algorithm | 38:54 | YouTube |
| 11-5 | 2026-01-19 | §11.4 Minimum Spanning Trees: Prim’s Algorithm | 17:19 | YouTube |
| 11-5 | 2026-01-20 | §11.5 Shortest Path: Dijkstra’s Algorithm | 31:26 | YouTube |
| 11-6 | 2026-01-20 | §11.6 Greedy Scheduling: Activity Selection | 20:15 | YouTube |
| 11-7 | 2026-01-20 | §11.7 Matroids | 33:05 | YouTube |
| 12-1 | 2025-01-21 | §12.1 Introduction (last year’s video due to snow storm) |
16:22 | YouTube |
| 12-2 | 2025-01-27 | §12.2 Matrix-Chain Multiplication (last year’s video due to snow storm) |
55:45 | YouTube |
| 12-3 | 2025-01-27 | §12.3 Greedy as DP (last year’s video due to snow storm) |
6:57 | YouTube |
| 12-4 | 2025-01-27 | §12.4 Bellman-Ford (last year’s video due to snow storm) |
21:12 | YouTube |
| 12-5 | 2026-01-27 | §12.4 Bellman-Ford implementation | 8:28 | YouTube |
| 12-6 | 2026-01-27 | §12.5 Change-making by DP | 18:14 | YouTube |
| 12-7 | 2026-01-27 | §12.6 Optimal binary search trees | 17:35 | YouTube |
| 12-8 | 2026-01-27 | §12.7 Edit distance | 19:32 | YouTube |
| 13-1 | 2026-02-02 | §13.1 Motivation, inverted indexes, tries | 28:21 | YouTube |
| 13-2 | 2026-02-02 | §13.2 Suffix trees | 13:29 | YouTube |
| 13-3 | 2026-02-02 | §13.3 Applications of suffix trees: string matching, longest repeated substring | 21:37 | YouTube |
| 13-4 | 2026-02-02 | §13.4 Generalized suffix trees, longest common substring | 11:11 | YouTube |
| 13-5 | 2026-02-02 | §13.5 Suffix arrays | 3:22 | YouTube |
| 13-6 | 2026-02-03 | §13.5 Suffix array via string sorting | 23:56 | YouTube |
| 13-7 | 2025-02-03 | §13.6 Linear-time suffix sorting – Induced sorting and merging | 23:22 | YouTube |
| 13-8 | 2025-02-03 | §13.7 Linear-time suffix sorting – DC3 algorithm | 11:18 | YouTube |