15-750: Graduate Algorithms, Spring 2020

Lecturer: Anupam Gupta, GHC 7203.

TAs: Andrii Riazanov (ariazano@andrew), Paul Gölz (pgoelz@andrew), and Roie Levin (roiel@andrew).

Office hours: Anupam: Tuesday 4-5pm (GHC 7203), Andrii: Wednesday 5-6pm (GHC 9009), Paul: Monday 3:30-4:30pm (GHC 6211), Roie: Wednesday 2-3pm (GHC 9219).

Location: NSH 1305, TR 10:30-11:50am.

Piazza: http://piazza.com/cmu/spring2020/15750/

Gradescope: https://www.gradescope.com/ (use your andrew ID to login please, and code 9RD3ZD if needed)

Course Details and Policies

• Here are some jupyter notebooks, for SVD and compressive sensing.
• Please read over the course policies here.
• The policies page also links to background resources on basic algorithms, probability, linear algebra, etc.
• Here is the current lecture schedule for the course (and the list of topics).

Homeworks

• Homework 0 (due Monday, Jan 20), solutions (CMU only)
• Homework 1 (due Thursday, Feb 6), solutions (CMU only)
• Homework 2 (due Thursday, Feb 20), solutions (CMU only)
• Homework 3 (due Sunday, Mar 15, end of spring break), solutions (CMU only)
• Homework 4 (due Thursday, Apr 2) solutions (CMU only)
• Homework 5 (due Saturday, Apr 18) solutions (CMU only)
• Homework 6 (due Saturday, May 2)


• Two practice midterms
  The Midterm will be in Rashid (GHC 4401), 6-9pm on Thursday Feb 27th.

Lectures

• Lecture 1 (Jan 14). Introduction + Strassen's Algorithm (my handwritten notes)
  • Handout on big-O and recurrences from 15-451/651.
  • Chapter 1 from Kozen (WebISO access only).
  • Optional: Strassen's paper, some intuition for his formulas (1,2,3), CACM article on low-communication MatMult (and video)


• Lecture 2 (Jan 16). Minimum Spanning Trees and Amortized Analysis (my handwritten notes)
  • Scans of chapters on Kruskal and MSTs (coming soon).
  • Notes on the two union-find data structures, we only covered the first one.
  • Optional: Wayne's slides on the tree-based data structures, and a proof that any (reasonable) union-find data structure takes inverse Ackermann-time.


• Lecture 3 (Jan 21). Shortest Paths: Binary and Binomial Heaps (my handwritten notes, (yet un)annotated slides)
  • Chapter from Kozen on Dijkstra, binomial heaps.
  • Kevin Wayne's original slides on binary and binomial heaps and (optional) Fibonacci heaps.


• Lecture 4 (Jan 23). Randomized Data Structures: Binary Search Trees and Treaps (tree-heaps) (my handwritten notes)
  • A little exercise in probabilistic reasoning.
  • Chapter from Kozen on treaps.


• Lecture 5 (Jan 28). Dynamic Programming
  • Lecture notes (and a recitation worksheet) from the 15-451 course, discussing several problems, via memoization and table-filling.
  • Some notes for the Talk Scheduling (aka Max-Weight Interval Packing) problem.
  • Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).


• Lecture 6 (Jan 30). Hashing for Fun and Profit: Universal Hashing and Perfect (Two-Level) Hashing (Notes (updated Feb 4))
  • Optional: A tutorial by Mikkel Thorup on basic hashing schemes (from this hashing summer school).
  • Optional: A blog post on choosing good hash functions in practice.


• Lecture 7 (Feb 4). Hashing II: Streaming Computation for Big Data (Notes (updated Feb 4))
  • The beginning of this chapter (sections 4.1-4.4) from the Mining Massive Datasets book gives a good introduction to some issues; see associated Stanford course.
  • Optional: Courses on data streaming - David Woodruff's course on data streaming has many link at the bottom, McGregor/Guha tutorial at KDD18/ICML16.
  • Optional: A survey on Network applications of Bloom filters by Broder and Mitzenmacher
  • Optional: Bloom filters and two-choice hashing feature on Jennifer Rexford's top 10 "practical theory" papers list at SIGCOMM.


• Lecture 8 (Feb 6). Hashing III: Load Balancing and Power of Two Choices (notes (updated Feb 6))
  • A couple of detailed examples/exercises on Chernoff bounds.
    Please try to become comfortable with using concentration bounds, exercises in HW2 will help. These will be crucial in the course.
  • Handwritten notes for Consistent Hashing
  • Notes on consistent hashing from Stanford's Modern Algorithmic Toolbox course (Roughgarden/Valiant).
  • Optional: SIGCOMM editorial note by Maggs/Sitaraman talking about implementation details for consistent hashing.
  • Optional: Akamai stories by Tom Leighton (video), and from CNET.


• Lecture 9 (Feb 11). Hashing IV: Locality Sensitive Hashing and Near-Neighbor Search (handwritten notes (updated Feb 11))
  • Chapter on LSH/NN search from the MMDS book (you can skip Section 3.8 onwards).
  • Lecture on Practice of NN Search by Ilya Razenshteyn (and other lectures in this series).
  • CACM technical perspective on LSH/NN search by Chazelle, and technical review (author copy) by Andoni and Indyk.


• Lecture 10 (Feb 13). Dimension Reduction I: Preserving Distances/Inner Products. (handwritten notes, older more technical notes)
  • Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Each of these proofs is a bit different.
  • Using J-L for learning applications: robust concept learning and mixtures of Gaussians. There are many other application papers: these are the pioneering ones.
  • Fast JL transforms: Ailon-Chazelle Ailon-Liberty.
  • SciKit's random projection implementation.


• Lecture 11 (Feb 18). Dimension Reduction II: JL recap, Compressive Sensing and the Single-Pixel Camera. (handwritten notes)
  • Notes on Compressive sensing, showing that distance preservation for sparse vectors suffices to give good sensing.
    Lemma 4.2 was what we called Theorem 2 in lecture. Theorem 3.2 was the main compressive sensing theorem.
  • Articles from AMS and Wired about compressive sensing. Terry Tao's blog post.
  • Notes on compressive sensing by Roughgarden/Valiant.
  • The Compressive Sensing resource page at Rice.


• Lecture 12 (Feb 20). Dimension Reduction III: Principal Component Analysis and Singular Values. (handwritten notes)
  • Chapter 11 (and slides) from the MMDS book about PCA, SVD, CUR, etc.
  • The data for today's demos and my blog post on this; here's matlab's PCA command.
  • An interactive example (and the accompanying article).
  • Nice summary of PCA/SVD from Stat.SE (and more chatty explanations)
  • Notes, handwritten notes from the 15-850 class, chapter from the Blum-Hopcroft-Kannan book.
  • Optional: Discussions on fast implementations: Trefethen and Bau, Demmel.


• Lecture 13 (Feb 25). Dimension Reduction IV: PCA/SVD (contd.). (same handwritten notes as for lecture 12)


• Lecture 14 (Feb 27). Midterm Exam (no class, exam at 6pm, Rashid)


• Lecture 15 (Mar 3). Optimization I: Flows and Matchings. (handwritten notes)
  • Notes and worksheet (sols) for Max-Flows from our 15-451 course.
  • Part of chapter from the Kleinberg-Tardos book.
  • Animations of some basic max-flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinics)


• Lecture 16 (Mar 5). Optimization II: Max-Flow Min-Cut. (handwritten notes)
  • Notes on modeling (weighted) caching using min-cost flow
  • Notes and worksheet for Max-Flows from our 15-451 course.


• Week of March 9: Spring Break!!


• Lecture 17 (Mar 19). Optimization III: Linear Programming, Introduction and Examples. (handwritten notes)
  • Online lectures: zoom links on Piazza.
  • Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters: Introduction, Examples, LP Basics.
  • Compressive sensing: html and jupyter notebook: basis pursuit (L1 minimization) for sparst signal recovery.
  • CVXOPT and PuLP: Solving linear/convex optimization problems in Python. Free LP solver from COIN-OR. Commercial ones from Gurobi and CPlex.


• Lecture 18 (Mar 24). Optimization IV: Linear Programming, Geometry and Simplex. (handwritten notes, board, updated simplex animation ppt, pdf)
  • Matousek/Gaertner. Chapters: Basics, Simplex.
  • Optional: George Dantzig on the origins of LPs.


• Lecture 19 (Mar 26). Optimization V: Linear Programming Duality, finishing Simplex, discussing Interior Point. (handwritten notes, board, updated simplex animation ppt, pdf)
  • Notes on duality from our 15-451 class, with a couple exercises, and a short "proof" of strong duality.
  • Matousek/Gaertner. Chapters: Simplex, Duality. (The beginnings of both chapters may be useful.)
  • The main classes of algorithms used in commercial solvers for LPs are: Simplex and Interior Point. Other interesting classes are: Ellipsoid and Multiplicative Weights.


• Lecture 20 (Mar 31). NP Hardness and Limits of Efficient Algorithms. (handwritten notes, board)
  • Notes from 15-451, and worksheet.


• Lecture 21 (Apr 2). Combating Intractability (new handwritten notes, notes on new material, board)
  • The Williamson-Shmoys book on Approximation algorithms is an excellent source.
  • Karp's original paper, and a more recent list of hard problems.


• Lecture 22 (Apr 7). Approximations (finish) and Making Decisions Online (begin) (handwritten online algos notes, online algos notes from 15-451, board)
  • Approximations: from last time, handwritten notes and typed 451 notes
  • Online Algorithms: today's notes: handwritten notes, and typed 451 notes


• Lecture 23 (Apr 9). Making Decisions Online (finish) (handwritten online algos notes, online algos notes from 15-451, board)
  • Online Algorithms: new handwritten notes, and typed 451 notes


• Lecture 24 (Apr 14). Online Decision Making III: The Experts Problem and the Multiplicative Weights Framework (handwritten notes, some slides, board)
  • Slides by Avrim Blum.
  • Notes from our 15-859 course.


• Lecture 25 (Apr 16). Online Decision Making IV and Optimization VI: Regularization Strikes Again! (handwritten notes, board)
  • Books by Elad Hazan and Shai Shalev-Shwartz get a lot more into Follow the Regularized Leader.


• Lecture 26 (Apr 21). Optimization VII: Gradient Descent (handwritten notes, board)
  • Notes from 15-451.
  • Potential function proofs of first-order methods by Nikhil Bansal and myself.
  • Books by Elad Hazan and Shai Shalev-Shwartz get a lot more into Follow the Regularized Leader.


• Lecture 27 (Apr 23). Graphs via Matrices: Spectral Graph Theory (handwritten notes, board)
  • A book (in progress) by Spielman, and notes by Trevisan.
  • Some notes by Roughgarden and Valiant


• Lecture 28 (Apr 28). Random Walks, Sampling and Monte Carlo Methods (handwritten notes, board)
  • Avrim Blum's notes on random walks and the connection to electrical networks.
  • The book chapter by Jon Kleinberg and David Easley on random walks and Pagerank.
  • The delightful little Doyle and Snell book on random walks and electrical networks.


• Lecture 29 (Apr 30). Final Exam (no class, details of exam to come soon)