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