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