Advanced Algorithms and Complexity
CS G526 | Aug-Dec 2026
This course explores advanced paradigms in algorithm design and analysis beyond the core curriculum, coupled with a serious study of complexity theory. It covers randomized algorithms, approximation algorithms, online algorithms, and a focused introduction to two-player matrix games (von Neumann’s minimax theorem and the multiplicative weights update), alongside parallel & distributed algorithms. Complexity theory is treated in depth — NP-completeness and reductions, the polynomial hierarchy, counting (#P), and interactive & zero-knowledge proofs — showing both what is computationally hard and what can still be achieved for hard problems.
Design and Analysis of Algorithms (CS F364) or equivalent.
Instructor: Tulasimohan Molli (TA: Hans Krupakar) Venue: I114 (lectures), I015 (lab) Venue: I114 (lectures), I015 (lab) Lectures: Monday 2:00–3:00 PM (I114) · Tuesday 12:00–1:00 PM (I114) · Thursday 12:00–1:00 PM (I114) Lab: Thursday 9:00–11:00 AM (I015) Lab: Thursday 9:00–11:00 AM (I015) Midsem: 06/10 Endsem: 04/12
Chamber Consultation: Monday 3:00–4:00 PM @ H-134
| Component | Weight |
|---|---|
| Midterm | 25% |
| Comprehensive Exam | 35% |
| Term Project (Proposal + Presentation + Report) | 20% |
| Lab Interaction | 10% |
| Class Interaction | 10% |
| # | Date | Topic | Slides |
|---|---|---|---|
| Lecture 1 | 2026-08-03 | Course Overview |  |
| Lecture 2 | 2026-08-04 | Probability Review I: Foundations & Expectation | |
| Lecture 3 | 2026-08-06 | Probability Review II: Tail Bounds | |
| Lecture 4 | 2026-08-10 | Applications of Tail Bounds | |
| Lecture 5 | 2026-08-11 | Applications of Tail Bounds II | |
| Lecture 6 | 2026-08-13 | Randomized Algorithms: Foundations | |
| Lecture 7 | 2026-08-18 | Las Vegas to Monte Carlo and Back | |
| Lecture 8 | 2026-08-20 | Randomized Complexity Classes | |
| Lecture 9 | 2026-08-24 | Graphs and Algebraic Matchings | |
| Lecture 10 | 2026-08-27 | Randomized Global Min-Cut (Karger’s Algorithm) | |
| Lecture 11 | 2026-08-31 | Randomized Data Structures: Skip Lists | |
| Lecture 12 & 13 | 2026-09-01 | Hash Tables, Universal Hashing & Perfect Hashing (FKS) | |
| Week | Module | Learning Objectives | Topics | Reference |
|---|---|---|---|---|
| 1 | M1 | Course scope and landscape; probability & complexity refresher | Introduction — Advanced Algorithms & Complexity; Review of Probability & Complexity Classes | T1 Ch1 |
| 2 | M1 | Classify randomized algorithms; verify matrix products, identities, min-cuts | Las Vegas & Monte Carlo, Freivalds, Min-Cut; PIT, Schwartz–Zippel | T1 Ch1 |
| 3 | M2 | Bound deviations via tail inequalities | Tail Inequalities, Chebyshev, Chernoff Bounds & Applications | T1 Ch3–4 |
| 4 | M3 | Expected-time data structures | Skip Lists, Hash Tables, Cuckoo Hashing | T1 Ch8 |
| 5 | M3 | Randomize classic graph algorithms | Randomized Graph Algorithms: MST, Shortest Paths, Matching | T1 Ch10 |
| 6 | M4 | Two-player matrix games: minimax and multiplicative weights | Two-Player Matrix Games; von Neumann’s Minimax Theorem; Multiplicative Weights Update | T1 Ch4 |
| 7 | M5 | Online decision-making under uncertainty | Competitive Ratio, Ski Rental, Paging, Secretary Problem | T1 Ch13 |
| 8 | M6 | Number-theoretic algorithms | Euclid, Euler’s φ, Primality Testing | T1 Ch14 |
| 9 | M7 | Parallel and distributed algorithms | PRAM, Prefix, MIS; Byzantine Agreement, Consensus | T1 Ch12 |
| 10 | M8 | NP-completeness framework and the polynomial hierarchy | NP-Completeness & Reductions: Decision Problems, Cook–Levin, Polynomial Hierarchy | T3 Ch2–4 |
| 11 | M9 | Approximation by greedy, LP rounding, primal-dual, local search | Greedy, LP Rounding, Primal-Dual, Local Search; Set Cover, TSP | R1, R3 |
| 12 | M9/M10 | Approximation schemes and limits of approximability; interactive proofs | PTAS, APX; Inapproximability, Gap Technique; Interactive Proofs | R4, T3 Ch8, 11 |
| 13 | M10 | Advanced complexity: interactive & zero-knowledge proofs, counting, algebraic methods | Interactive & Zero-Knowledge Proofs; #P & Counting; Algebraic Counting Methods | T3 Ch8–9, T1 Ch1 |
| 14 | M11 | Student project proposal presentations | Student Project Proposal Presentations | — |