COMP 526 – Efficient Algorithms (Fall 2023): videos
All lecture videos · module page · YouTube playlist
64 videos, 23 h 08 min
| Video | Date | Title | Length | Transcript |
|---|---|---|---|---|
| 0-0 | 2023-09-28 | Welcome, teaching mode, overview, assessment, academic integity, Campuswire, prior knowledge survey | 1:11:35 | transcript & video |
| 0-1 | 2023-09-29 | §0.1 Random shuffle motivation | 14:56 | transcript & video |
| 0-2 | 2023-09-29 | §0.2 Proof templates, random shuffle motivation | 16:18 | transcript & video |
| 0-3 | 2023-09-29 | §0.3 Mathematical induction, Towers of Hanoi | 9:29 | transcript & video |
| 0-4 | 2023-09-29 | §0.4 Correctness proofs | 31:07 | transcript & video |
| 1-1 | 2023-10-05 | §1.1 Algorithm analysis | 14:46 | transcript & video |
| 1-2 | 2023-10-05 | §1.2 The RAM model | 23:45 | transcript & video |
| 1-3 | 2023-10-05 | §1.3 Asymptotics and Big-Oh | 35:48 | transcript & video |
| 2-1 | 2023-10-06 | §2.1 ADTs, Stacks and Queues | 22:58 | transcript & video |
| 2-2 | 2023-10-06 | §2.2 Resizable arrays | 25:57 | transcript & video |
| 2-3 | 2023-10-06 | §2.3 Priority queues & binary heaps | 16:34 | transcript & video |
| 2-4 | 2023-10-06 | §2.4 Operations on binary heaps | 14:41 | transcript & video |
| 2-5 | 2023-10-12 | §2.5 Symbol tables | 14:33 | transcript & video |
| 2-6 | 2023-10-12 | §2.6 Binary search trees | 25:11 | transcript & video |
| 2-7 | 2023-10-12 | §2.7 Ordered symbol tables | 21:10 | transcript & video |
| 2-8 | 2023-10-12 | §2.8 Balanced binary search trees | 10:43 | transcript & video |
| 3-0 | 2023-10-13 | §3.0 Sorting introduction | 14:39 | transcript & video |
| 3-1 | 2023-10-13 | §3.1 Mergesort | 18:50 | transcript & video |
| 3-2 | 2023-10-13 | §3.2 Quicksort | 23:11 | transcript & video |
| 3-3 | 2023-10-13 | §3.3 Comparison-based lower bound | 15:27 | transcript & video |
| 3-4 | 2023-10-19 | §3.4 Integer sorting | 16:04 | transcript & video |
| 3-5 | 2023-10-19 | §3.5 Adaptive sorting & Peeksort | 34:22 | transcript & video |
| 3-6 | 2023-10-19 | §3.6 Python’s list sort & Powersort | 15:06 | transcript & video |
| 3-7 | 2023-10-20 | §3.7 Order statistics, quickselect, median of medians | 32:50 | transcript & video |
| 3-8 | 2023-10-20 | §3.8 Further divide & conquer algorithms | 15:04 | transcript & video |
| 4-1 | 2023-10-20 | §4.1 Introduction | 16:53 | transcript & video |
| 4-2 | 2023-10-20 | §4.2 Brute force string matching | 8:15 | transcript & video |
| 4-3 | 2023-10-26 | §4.3 String matching with finite automata | 26:40 | transcript & video |
| 4-4 | 2023-10-26 | §4.4 Constructing string matching DFAs | 24:08 | transcript & video |
| 4-5 | 2023-10-26 | §4.5 The Knuth-Morris-Pratt algorithm | 29:06 | transcript & video |
| 4-6 | 2022-10-31 | §4.6 The Boyer-Moore algorithm | 17:10 | transcript & video |
| 4-7 | 2022-10-31 | §4.7 The Rabin-Karp algorithm | 16:49 | transcript & video |
| 5-1 | 2023-10-27 | §5.1 Compression context: terminology, Kolmogorov complexity | 22:30 | transcript & video |
| 5-2 | 2023-10-27 | §5.2 Character Encodings | 20:39 | transcript & video |
| 5-3 | 2023-11-02 | §5.3 Huffman codes | 30:07 | transcript & video |
| 5-4 | 2023-11-02 | §5.4 Entropy and Huffman codes | 36:03 | transcript & video |
| 5-5 | 2023-11-03 | §5.5 Run-length encoding | 26:41 | transcript & video |
| 5-6 | 2023-11-03 | §5.6 Lempel-Ziv-Welch encoding | 18:09 | transcript & video |
| 5-8 | 2023-11-03 | §5.7 Lempel Ziv Welch decoding | 20:52 | transcript & video |
| 5-9 | 2023-11-03 | §5.8 Move-to-front transform | 15:02 | transcript & video |
| 5-9 | 2023-11-16 | §5.9 Burrows-Wheeler transform | 26:15 | transcript & video |
| 5-10 | 2023-11-16 | §5.10 Inverse BWT | 16:00 | transcript & video |
| 6-1 | 2023-11-16 | §6.1 Error correcting codes introduction | 13:43 | transcript & video |
| 6-2 | 2023-11-17 | §6.2 Lower bounds for error correcting codes | 28:05 | transcript & video |
| 6-3 | 2023-11-17 | §6.3 Hamming codes introduction | 29:48 | transcript & video |
| 7-1 | 2023-11-17 | §7.1 Parallel computation, PRAM | 15:30 | transcript & video |
| 7-2 | 2023-11-23 | §7.1 Brent’s Theorem | 12:37 | transcript & video |
| 7-3 | 2023-11-23 | §7.2 Parallel string matching | 18:27 | transcript & video |
| 7-4 | 2023-11-23 | §7.3 Parallel primitives, prefix sum, compaction | 34:27 | transcript & video |
| 7-5 | 2023-11-23 | §7.4 Parallel sorting | 18:25 | transcript & video |
| 8-1 | 2023-11-24 | §8.1 Motivation, inverted indices, tries | 41:09 | transcript & video |
| 8-2 | 2023-11-24 | §8.2 Suffix trees | 18:50 | transcript & video |
| 8-3 | 2023-11-24 | §8.3 Applications of suffix trees: string matching | 13:44 | transcript & video |
| 8-4 | 2023-11-30 | §8.3 Applications of suffix trees (part 2): longest repeated substring, longest common substring | 25:30 | transcript & video |
| 8-5 | 2023-11-30 | §8.4 Longest common extensions | 21:45 | transcript & video |
| 8-6 | 2023-11-30 | §8.5 Suffix arrays | 27:17 | transcript & video |
| 8-7 | 2023-12-01 | §8.6 Linear-time suffix sorting – Induced sorting and merging | 28:54 | transcript & video |
| 8-8 | 2023-12-01 | §8.7 Linear-time suffix sorting – DC3 algorithm | 11:29 | transcript & video |
| 8-9 | 2023-12-01 | §8.8 The LCP array | 25:48 | transcript & video |
| 9-1 | 2023-12-07 | §9.1 RMQ introduction | 10:06 | transcript & video |
| 9-2 | 2023-12-07 | §9.2 LCE using RMQ | 12:45 | transcript & video |
| 9-3 | 2023-12-07 | §9.3 Primitive RMQ & Sparse Tables | 17:20 | transcript & video |
| 9-4 | 2023-12-07 | §9.4 Cartesian trees | 23:37 | transcript & video |
| 9-5 | 2023-12-07 | §9.5 Exhaustive tabulation | 13:20 | transcript & video |