CS 627 – Advanced Algorithms (Summer 2025): videos
All lecture videos · module page · YouTube playlist
74 videos, 27 h 48 min
| Video | Date | Title | Length | Transcript |
|---|---|---|---|---|
| 0-1 | 2025-04-22 | Welcome, teaching mode, overview, assessment, academic integity, Campuswire, | 31:03 | transcript & video |
| 0-1 | 2025-04-22 | Hard problems, theory loopholes, outline of the module | 14:14 | transcript & video |
| 2-1 | 2025-04-22 | P and NP intuitively | 12:04 | transcript & video |
| 2-2 | 2025-04-22 | Models of computation: word-RAM | 14:46 | transcript & video |
| 2-3 | 2025-04-23 | Models of computation: Turing Machines | 35:40 | transcript & video |
| 2-4 | 2025-04-23 | P and NP formally | 11:57 | transcript & video |
| 2-5 | 2025-04-23 | Nondeterminism = Verification | 17:06 | transcript & video |
| 2-6 | 2025-04-23 | Karp-Reductions and NP completeness | 8:01 | transcript & video |
| 2-7 | 2025-04-23 | Example NP-completeness prooof (overview) | 4:54 | transcript & video |
| 2-8 | 2025-05-13 | Further hard problems | 12:12 | transcript & video |
| 2-9 | 2025-04-13 | Optimization problems | 31:28 | transcript & video |
| 3-1 | 2025-05-13 | Pseudopolynomial algorithms | 13:58 | transcript & video |
| 3-2 | 2025-05-13 | Knapsack | 11:55 | transcript & video |
| 3-3 | 2025-05-13 | Strong NP-hardness | 8:08 | transcript & video |
| 4-0 | 2025-05-14 | Parameterized problems | 14:46 | transcript & video |
| 4-1 | 2025-05-14 | Fixed-parameter tractability | 33:25 | transcript & video |
| 4-2 | 2025-05-14 | Depth-bounded search I | 11:11 | transcript & video |
| 4-3 | 2025-05-14 | Problem kernels | 24:28 | transcript & video |
| 4-4 | 2025-05-20 | Problem kernels: p-MaxSAT | 21:50 | transcript & video |
| 4-5 | 2025-05-20 | Depth-bounded search for p-PlanarIndependentSet | 43:13 | transcript & video |
| 4-6 | 2025-05-20 | Depth-bounded search for p-ClosestString | 11:22 | transcript & video |
| 4-7 | 2025-05-21 | Depth-bounded search for p-ClosestString (part 2) | 15:53 | transcript & video |
| 4-8 | 2025-05-21 | Better FPT Vertex Cover & Linear recurrences | 1:04:49 | transcript & video |
| 4-8 | 2025-05-27 | Interleaving | 42:13 | transcript & video |
| 5-1 | 2025-05-27 | Parameterized reductions | 16:34 | transcript & video |
| 5-2 | 2025-05-27 | para-NP | 18:07 | transcript & video |
| 5-3 | 2025-05-28 | Bounded nondeterminism & W[P] | 38:47 | transcript & video |
| 5-4 | 2025-05-28 | Tail-nondeterminism & W[1] | 41:47 | transcript & video |
| 5-5 | 2025-06-03 | Recap & W[1]-hardness | 8:22 | transcript & video |
| 6-1 | 2025-06-03 | Linear programs for modeling problems | 33:37 | transcript & video |
| 6-2 | 2025-06-03 | Linear program normal forms | 11:33 | transcript & video |
| 6-3 | 2025-06-03 | The simplex algorithm | 25:32 | transcript & video |
| 6-4 | 2025-06-04 | Integer programs | 17:48 | transcript & video |
| 6-5 | 2025-06-04 | LP-based kernelization | 39:04 | transcript & video |
| 6-6 | 2025-06-04 | Lower bounds based on the Exponential Time Hypothesis (ETH) | 19:30 | transcript & video |
| 6-7 | 2025-06-10 | Lower bounds based on the Exponential Time Hypothesis (ETH) part 2 | 27:44 | transcript & video |
| 7-1 | 2025-06-10 | Randomization motivation | 17:34 | transcript & video |
| 7-2 | 2025-06-10 | Randomized selection by rank (deterministic adversary lower bound, Floyd-Rivest algorithm) | 29:55 | transcript & video |
| 7-3 | 2025-06-11 | Probability theory recap | 36:46 | transcript & video |
| 7-4 | 2025-06-11 | Probabilistic Turing machines | 39:50 | transcript & video |
| 7-5 | 2025-06-17 | Las Vegas and Monte Carlo algorithms | 11:10 | transcript & video |
| 7-6 | 2025-06-17 | Contrenration Bounds: Markov, Chebyshev, Chernoff | 1:07:11 | transcript & video |
| 7-7 | 2025-06-18 | Concentration Bounds in Action | 1:01:20 | transcript & video |
| 8-1 | 2025-06-18 | Probabilistic complexity classes: ZPP, BPP, PP | 21:47 | transcript & video |
| 8-2 | 2025-06-24 | Probabilistic complexity classes: RP, co-RP | 5:58 | transcript & video |
| 8-3 | 2025-06-24 | Pseudorandom generators | 11:54 | transcript & video |
| 8-4 | 2025-06-24 | Boolean circuits | 29:42 | transcript & video |
| 8-5 | 2025-06-24 | Derandomization | 16:31 | transcript & video |
| 8-6 | 2025-06-24 | Nisan-Wigderson: Combinatorial designs | 17:18 | transcript & video |
| 8-7 | 2025-06-25 | Nisan-Wigderson construction | 51:07 | transcript & video |
| 8-8 | 2025-06-25 | Summary | 3:36 | transcript & video |
| 9-1 | 2025-06-25 | Random trick in Hashing | 18:33 | transcript & video |
| 9-2 | 2025-07-01 | Balls and bins | 45:58 | transcript & video |
| 9-3 | 2025-07-01 | Universal hashing | 17:16 | transcript & video |
| 9-4 | 2025-07-01 | Perfect hashing | 15:12 | transcript & video |
| 9-5 | 2025-07-02 | Perfect hashing analysis | 11:52 | transcript & video |
| 9-6 | 2025-07-02 | Primality testing | 33:55 | transcript & video |
| 9-7 | 2025-07-02 | Schöning’s SAT for 2SAT | 18:59 | transcript & video |
| 9-8 | 2025-07-08 | Schöning’s 3SAT algorithm | 49:49 | transcript & video |
| 10-1 | 2025-07-08 | Motivation & Definitions | 9:14 | transcript & video |
| 10-2 | 2025-07-08 | Vertex Covers & Matchings | 12:19 | transcript & video |
| 10-3 | 2025-07-09 | Greedy Set Cover | 19:45 | transcript & video |
| 10-4 | 2025-07-09 | Layering algorithm for Set Cover | 19:42 | transcript & video |
| 10-5 | 2025-07-09 | Shortest Superstrings via Set Cover | 20:25 | transcript & video |
| 10-6 | 2025-07-09 | Approximation Schemes, Knapsack | 21:48 | transcript & video |
| 10-8 | 2025-07-15 | Christofides’ TSP Algorithm | 18:49 | transcript & video |
| 10-8 | 2025-07-09 | Randomized Approximation Algorithms | 2:31 | transcript & video |
| 11-1 | 2025-07-15 | LP & ILP recap | 5:44 | transcript & video |
| 11-2 | 2025-07-15 | LP Rounding | 13:36 | transcript & video |
| 11-3 | 2025-07-15 | Randomized Rounding | 10:21 | transcript & video |
| 11-4 | 2025-07-15 | LP Duality | 14:23 | transcript & video |
| 11-5 | 2025-07-15 | Vertex Cover and Matching via Duality | 6:18 | transcript & video |
| 11-6 | 2025-07-16 | Dual Fitting | 31:23 | transcript & video |
| 11-7 | 2025-07-16 | Primal-Dual Schema | 19:45 | transcript & video |