COMP 526 – Efficient Algorithms (Spring 2022): videos
All lecture videos · module page · YouTube playlist
63 videos, 22 h 42 min
| Video | Date | Title | Length | Transcript |
|---|---|---|---|---|
| 0-1 | 2022-01-31 | Welcome, teaching mode, overview, assessment, Campuswire, video presentation, prior knowledge survey | 43:23 | transcript & video |
| 0-2 | 2022-02-03 | §0.1 Proof templates | 24:42 | transcript & video |
| 0-3 | 2022-02-03 | §0.2 Mathematical induction | 14:08 | transcript & video |
| 0-4 | 2022-02-03 | §0.3 Correctness proofs | 36:16 | transcript & video |
| 1-1 | 2022-02-07 | §1.1 Algorithm analysis | 17:16 | transcript & video |
| 1-2 | 2022-02-07 | §1.2 The RAM model | 18:48 | transcript & video |
| 1-3 | 2022-02-07 | §1.3 Asymptotics | 37:40 | transcript & video |
| 2-1 | 2022-02-10 | §2.1 ADTs, Stacks and Queues | 21:03 | transcript & video |
| 2-2 | 2022-02-10 | §2.2 Resizable arrays | 29:26 | transcript & video |
| 2-3 | 2022-02-10 | §2.3 Priority queues & binary heaps | 16:42 | transcript & video |
| 2-4 | 2022-02-14 | §2.4 Operations on binary heaps Unfortunately, the first 8min of the recording have no sound; the same content is covered in the video from last year (part 1, part 2). |
22:01 | transcript & video |
| 2-5 | 2022-02-14 | §2.5 Symbol tables | 9:50 | transcript & video |
| 2-6 | 2022-02-14 | §2.6 Binary search trees | 17:30 | transcript & video |
| 2-7 | 2022-02-14 | §2.7 Ordered symbol tables | 17:35 | transcript & video |
| 2-8 | 2022-02-14 | §2.8 Balanced binary search trees | 4:22 | transcript & video |
| 3-1 | 2022-02-17 | §3.0 Sorting introduction | 13:18 | transcript & video |
| 3-2 | 2022-02-17 | §3.1 Mergesort | 17:47 | transcript & video |
| 3-3 | 2022-02-17 | §3.2 Quicksort | 19:18 | transcript & video |
| 3-4 | 2022-02-17 | §3.3 Comparison-based lower bound | 15:11 | transcript & video |
| 3-5 | 2022-02-17 | §3.4 Integer sorting | 10:18 | transcript & video |
| 3-6 | 2022-02-21 | §3.5 Adaptive sorting | 39:20 | transcript & video |
| 3-7 | 2022-02-21 | §3.6 Python’s list sort & Powersort | 21:21 | transcript & video |
| 3-8 | 2022-02-24 | §3.7 Parallel computation, PRAM | 34:47 | transcript & video |
| 3-9 | 2022-02-24 | §3.8 Parallel primitives, prefix sum | 33:32 | transcript & video |
| 3-10 | 2022-02-24 | §3.9 Parallel sorting | 14:14 | transcript & video |
| 4-1 | 2022-02-28 | §4.1 Introduction | 18:56 | transcript & video |
| 4-2 | 2022-02-28 | §4.2 Brute force string matching | 9:49 | transcript & video |
| 4-3 | 2022-02-28 | §4.3 String matching with finite automata | 13:47 | transcript & video |
| 4-4 | 2022-02-28 | §4.4 Constructing string matching DFAs | 24:10 | transcript & video |
| 4-5 | 2022-03-03 | §4.5 The Knuth-Morris-Pratt algorithm | 27:03 | transcript & video |
| 4-6 | 2022-03-03 | §4.6 The Boyer-Moore algorithm | 22:38 | transcript & video |
| 4-7 | 2022-03-03 | §4.7 The Rabin-Karp algorithm | 16:47 | transcript & video |
| 5-1 | 2022-03-07 | §5.1 Elementary parallel string matching | 21:16 | transcript & video |
| 5-2 | 2022-03-07 | §5.2 Periodicity | 15:21 | transcript & video |
| 5-3 | 2022-03-07 | §5.3 String matching with duels | 22:30 | transcript & video |
| 6-1 | 2022-03-07 | §6.1 Motivation, inverted indices | 15:27 | transcript & video |
| 6-2 | 2022-03-10 | §6.1 Tries | 27:54 | transcript & video |
| 6-3 | 2022-03-10 | §6.2 Suffix trees | 16:58 | transcript & video |
| 6-4 | 2022-03-10 | §6.3 Applications of suffix trees | 33:37 | transcript & video |
| 6-5 | 2022-03-14 | §6.4 Longest common extensions | 32:53 | transcript & video |
| 6-6 | 2022-03-14 | §6.5 Suffix arrays | 30:01 | transcript & video |
| 6-7 | 2022-03-17 | §6.6 Linear-time suffix sorting – Overview | 32:08 | transcript & video |
| 6-8 | 2022-03-17 | §6.7 Linear-time suffix sorting – DC3 recursion | 11:59 | transcript & video |
| 6-9 | 2022-03-17 | §6.8 LCP arrays | 11:29 | transcript & video |
| 6-10 | 2022-03-17 | §6.9 LCP array construction & back to suffix trees | 18:12 | transcript & video |
| 7-1 | 2022-03-21 | §7.1 Compression context | 25:37 | transcript & video |
| 7-2 | 2022-03-21 | §7.2 Character Encodings | 25:46 | transcript & video |
| 7-3 | 2022-03-21 | §7.3 Huffman codes | 25:05 | transcript & video |
| 7-4 | 2022-03-24 | §7.4 Entropy and Huffman codes | 36:39 | transcript & video |
| 7-5 | 2022-03-24 | §7.5 Run-length encoding | 23:17 | transcript & video |
| 7-6 | 2022-03-24 | §7.6 Lempel-Ziv-Welch encoding | 14:50 | transcript & video |
| 7-7 | 2022-03-28 | §7.7 Lempel Ziv Welch decoding | 28:01 | transcript & video |
| 7-8 | 2022-03-28 | §7.8 Move-to-front transform | 17:24 | transcript & video |
| 7-9 | 2022-03-28 | §7.9 Burrows Wheeler transform | 21:01 | transcript & video |
| 7-10 | 2022-03-28 | §7.10 Inverse BWT | 8:26 | transcript & video |
| 8-1 | 2022-03-31 | §8.1 Error correcting codes introduction | 13:03 | transcript & video |
| 8-2 | 2022-03-31 | §8.2 Lower bounds for error correcting codes | 23:15 | transcript & video |
| 8-3 | 2022-03-31 | §8.3 Hamming codes introduction | 36:17 | transcript & video |
| 9-1 | 2022-04-25 | §9.1 RMQ introduction | 11:50 | transcript & video |
| 9-2 | 2022-04-25 | §9.2 LCE using RMQ | 12:43 | transcript & video |
| 9-3 | 2022-04-25 | §9.3 Primitive RMQ & Sparse Tables | 16:09 | transcript & video |
| 9-4 | 2022-04-25 | §9.4 Cartesian trees | 28:24 | transcript & video |
| 9-5 | 2022-04-28 | §9.5 Exhaustive tabulation | 21:56 | transcript & video |