COMP 526 – Efficient Algorithms (Spring 2021): videos
All lecture videos · module page · YouTube playlist
67 videos, 23 h 55 min
| Video | Date | Title | Length | Transcript |
|---|---|---|---|---|
| 0-1 | 2021-02-08 | Welcome, teaching mode, prior knowledge survey | 27:14 | transcript & video |
| 0-2 | 2021-02-10 | Overview, assessment, Campuswire, video presentation | 33:45 | transcript & video |
| 0-3 | 2021-02-10 | §0.1 Proof templates | 27:33 | transcript & video |
| 0-4 | 2021-02-10 | §0.2 Mathematical induction | 8:20 | transcript & video |
| 0-5 | 2021-02-10 | §0.3 Correctness proofs (part 1) | 7:41 | transcript & video |
| 0-6 | 2021-02-16 | §0.3 Correctness proofs (part 2) | 18:53 | transcript & video |
| 1-1 | 2021-02-16 | §1.1 Algorithm analysis | 13:17 | transcript & video |
| 1-2 | 2021-02-16 | §1.2 The RAM model | 18:09 | transcript & video |
| 1-3 | 2021-02-16 | §1.3 Asymptotics | 32:36 | transcript & video |
| 2-1 | 2021-02-17 | §2.1 Stacks and Queues | 22:26 | transcript & video |
| 2-2 | 2021-02-17 | §2.2 Resizable arrays | 25:50 | transcript & video |
| 2-3 | 2021-02-17 | §2.3 Binary heaps (part 1) | 34:47 | transcript & video |
| 2-4 | 2021-02-23 | §2.3 Binary heaps (part 2) | 10:41 | transcript & video |
| 2-5 | 2021-02-23 | §2.4 Binary seach | 18:47 | transcript & video |
| 2-6 | 2021-02-23 | §2.4 Binary search trees | 29:37 | transcript & video |
| 2-7 | 2021-02-23 | §2.5 Ordered symbol tables | 22:41 | transcript & video |
| 2-8 | 2021-02-23 | §2.6 Balanced binary search trees | 13:25 | transcript & video |
| 3-1 | 2021-02-24 | §3.0 Sorting introduction | 12:56 | transcript & video |
| 3-2 | 2021-02-24 | §3.1 Mergesort | 17:23 | transcript & video |
| 3-3 | 2021-02-24 | §3.2 Quicksort | 27:40 | transcript & video |
| 3-4 | 2021-03-02 | §3.3 Comparison-based lower bound | 21:48 | transcript & video |
| 3-5 | 2021-03-02 | §3.4 Integer sorting | 22:08 | transcript & video |
| 3-6 | 2021-03-02 | §3.5 Parallel computation, PRAM | 34:49 | transcript & video |
| 3-7 | 2021-03-03 | §3.6 Parallel primitives, prefix sum | 38:49 | transcript & video |
| 3-8 | 2021-03-03 | §3.7 Parallel sorting | 18:31 | transcript & video |
| 4-1 | 2021-03-03 | §4.1 Introduction | 14:57 | transcript & video |
| 4-2 | 2021-03-09 | §4.2 Brute force string matching | 12:32 | transcript & video |
| 4-3 | 2021-03-09 | §4.3 String matching with finite automata | 15:26 | transcript & video |
| 4-4 | 2021-03-09 | §4.3 Constructing string matching DFAs | 23:12 | transcript & video |
| 4-5 | 2021-03-09 | §4.4 The Knuth-Morris-Pratt algorithm | 25:01 | transcript & video |
| 4-6 | 2021-03-10 | §4.5 The Boyer-Moore algorithm | 31:01 | transcript & video |
| 4-7 | 2021-03-10 | §4.6 The Rabin-Karp algorithm | 20:18 | transcript & video |
| 5-1 | 2021-03-10 | §5.1 Elementary parallel string matching | 17:37 | transcript & video |
| 5-2 | 2021-03-10 | §5.2 Periodicity | 5:37 | transcript & video |
| 5-3 | 2021-03-16 | §5.2 Periodicity (part 2) | 10:16 | transcript & video |
| 5-4 | 2021-03-16 | §5.3 String matching with duels | 28:22 | transcript & video |
| 6-1 | 2021-03-16 | §6.1 Motivation, inverted indices | 31:10 | transcript & video |
| 6-2 | 2021-03-17 | §6.2 Suffix trees | 21:49 | transcript & video |
| 6-3 | 2021-03-17 | §6.3 Applications of suffix trees | 36:00 | transcript & video |
| 6-4 | 2021-03-17 | §6.4 Longest common extensions | 10:32 | transcript & video |
| 6-5 | 2021-04-13 | §6.4 Longest common extensions (part 2) | 20:47 | transcript & video |
| 6-6 | 2021-04-13 | §6.5 Suffix arrays | 27:35 | transcript & video |
| 6-6a | 2021-04-14 | Addendum to §6.5 Suffix arrays | 1:34 | transcript & video |
| 6-7 | 2021-04-13 | §6.6 Linear-time suffix sorting | 19:23 | transcript & video |
| 6-8 | 2021-04-14 | §6.6 Linear-time suffix sorting (part 2) | 25:24 | transcript & video |
| 6-9 | 2021-04-14 | §6.7 LCP arrays | 12:06 | transcript & video |
| 6-10 | 2021-04-14 | §6.7 LCP array construction & back to suffix trees | 21:48 | transcript & video |
| 7-1 | 2021-04-20 | §7.1 Compression context | 24:55 | transcript & video |
| 7-2 | 2021-04-20 | §7.2 Character Encodings | 25:03 | transcript & video |
| 7-3 | 2021-04-20 | §7.3 Huffman codes | 25:10 | transcript & video |
| 7-4 | 2021-04-21 | §7.3 Entropy | 41:46 | transcript & video |
| 7-5 | 2021-04-21 | §7.4 Run-length encoding | 26:37 | transcript & video |
| 7-6 | 2021-04-21 | §7.5 Lempel Ziv Welch introduction | 9:14 | transcript & video |
| 7-7 | 2021-04-27 | §7.5 Lempel Ziv Welch | 41:12 | transcript & video |
| 7-8 | 2021-04-27 | §7.6 Move to front text transformation | 18:00 | transcript & video |
| 7-9 | 2021-04-27 | §7.7 Burrows Wheeler transform | 21:18 | transcript & video |
| 7-10 | 2021-04-28 | §7.7 Inverse BWT | 25:02 | transcript & video |
| 8-1 | 2021-04-28 | §8.1 Error correcting codes introduction | 15:31 | transcript & video |
| 8-2 | 2021-04-28 | §8.2 Lower bounds for error correcting codes | 22:00 | transcript & video |
| 8-3 | 2021-04-28 | §8.3 Hamming codes introduction | 6:32 | transcript & video |
| 8-4 | 2021-05-04 | §8.3 Hamming codes | 36:52 | transcript & video |
| 9-1 | 2021-05-04 | §9.1 RMQ introduction | 15:01 | transcript & video |
| 9-2 | 2021-05-04 | §9.2 LCE using RMQ | 13:08 | transcript & video |
| 9-3 | 2021-05-04 | §9.3 Primitive RMQ solutions | 3:54 | transcript & video |
| 9-4 | 2021-05-05 | §9.3 Sparse table RMQ | 12:44 | transcript & video |
| 9-5 | 2021-05-05 | §9.4 Cartesian trees | 37:33 | transcript & video |
| 9-6 | 2021-05-05 | §9.5 Four Russians lookup table | 21:29 | transcript & video |