Tim Roughgarden's Online Courses

Recent (2020--) Online Courses

• Foundations of Blockchains, derived from my Columbia course with the same name.
  • Topics include classical consensus (the Dolev-Strong protocol, the FLP impossibility theorem, the Tendermint protocol), longest-chain consensus, proof-of-work-based permissionless consensus, selfish mining, transaction fee mechansim design, and the design and analysis of proof-of-stake blockchain protocols.

• Incentives in Computer Science, a short course derived from the most accessible material in Stanford's CS269I course. Lecture notes are here and here.
  • Topics include: Markets in computer science, with applications to online platforms; the Prisoner's Dilemma, with a case study on BitTorrent; asymmetric information (adverse selection and moral hazard), with a case study on eBay's reputation system; auctions, with a case study on Google's sponsored search auctions; voting in computer science, with a case study on participatory budgeting; and game theory in blockchains, with a deep dive on Bitcoin.

MOOCs on Coursera

Algorithms Specialization based on Stanford's undergraduate algorithms course (CS161). See also the accompanying Algorithms Illuminated book series. YouTube playlists are here and here. Comprises four 4-week courses:
• Part 1: Divide and Conquer, Sorting and Searching, and Randomized Algorithms
  • Covers asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

• Part 2: Graph Search, Shortest Paths, and Data Structures
  • Covers data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

• Part 3: Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
  • Covers greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

• Part 4: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
  • Covers shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

These courses have appeared on various "top MOOCs of all time" lists, like here and here. New sessions begin every few weeks.

MOOCs on EdX

The specialization above subsumes the following older versions:
• Algorithms: Design and Analysis (Part I).
  • A YouTube playlist of all the lecture videos is available, among other places, here.
  • Slides are here.

• Algorithms: Design and Analysis (Part II).
  • A YouTube playlist of all the lecture videos is available here.
  • Slides are here.

Stanford lectures on YouTube

• 20 Video Lectures on the Design and Analysis of Algorithms, covering most of the above Coursera MOOCs, for those of you who prefer blackboard lectures (from Stanford's CS161, Winter 2011).
  • Warning/apology: the audio is suboptimal on a few segements of these lectures.

• 20 Video Lectures from A Second Course in Algorithms (Stanford's CS261, Winter 2016). Lecture notes are here
  • Topics include: algorithms for maximum flow and minimum cuts (augmenting paths, push-relabel etc.); bipartite matching and generalizations; linear programming; duality; online regret-minimization and the multiplicative weights algorithm; online algorithms; design and analysis of approximation algorithms; the traveling salesman problem; essential tools for the analysis of randomized algorithms; beating brute-force search for NP-hard problems.

• 20 Video Lectures on Algorithmic Game Theory (from Stanford's CS364A, Fall 2013). Lecture notes are here
  • Topics include: auction and mechanism design (Vickrey and Myerson auctions, VCG mechanism, etc.); the "price of anarchy" (selfish routing, smoothness, etc.); learning in games (no-regret algorithms, etc.); complexity of Nash equilibria (PLS- and PPAD-completeness). Case studies include: keyword search auctions, combinatorial auctions for spectrum, kidney exchange, and communication network management.

• 20 Video Lectures on Advanced Mechanism Design (from Stanford's CS364B, Winter 2014). Lecture notes are here
  • Topics include: combinatorial auctions; Walrasian equilibria and the gross substitutes condition; ascending and ex post implementations; truthful approximation mechanisms; black-box reductions; simple auctions and equilibrium guarantees for them (Bayes-Nash smoothness, etc.); Border's theorem; multi-parameter revenue-maximization.

• 20 Video Lectures on Beyond Worst-Case Analysis (from Stanford's CS264, Fall 2014). Lecture notes are here
  • Topics include: instance optimality; parameterized analysis and condition numbers; stable clustering; models of data (pseudorandomness, locality, diffuse adversaries, etc.); distributional models; smoothed analysis; planted and semi-random graph models; exact recovery (compressive sensing, LP decoding). Motivating problems drawn from online algorithms, machine learning, computational geometry, graph partitioning, linear programming, hashing, etc.

Home