15-750: Algorithms in the Real World, Spring 2022

Lecturers: Anupam Gupta (anupamg@cs), Rashmi Vinayak (rvinayak@cs).

TAs: Justin Whitehouse (jwhiteho@andrew), Francisco Maturana (fmaturan@cs), Yuanhao Wei (yuanhao1@cs).

Office hours:Please refer to the class calendar below.

Piazza: Please use private messages on Piazza instead of emailing the course staff, that way the messages will not get lost.

Location: Margaret Morrison A14, Tue/Thu 10:10-11:30.

Piazza: http://piazza.com/cmu/spring2022/15750/home

Gradescope: https://www.gradescope.com/

Course Details and Policies

• Please read the course policies carefully!!!.
• Here are the course intro slides from lecture #1
• Links to resources to help brush up on your background.
• Here is a tentative schedule for the course.

Homeworks

• Homework 1 (due Thursday, Feb 3) [updated Jan 26 with a small fix in Exercise 3], solutions (CMU only)
• Homework 2 (due Thursday, Feb 17), exercises, solutions (CMU only)
• Homework 3 (due Tuesday, Mar 15), solutions (CMU only), Programming problem solution (CMU only).
• Midterm solutions (CMU only)
• Homework 4 (due Thursday, Mar 31), solutions (CMU only)
• Homework 5 (due Thursday, Apr 14), solutions (CMU only)
• Homework 6 (due Sunday, May 1), solutions (CMU only)

Lectures

• Lecture 1 (Jan 18). Introduction + Strassen's Algorithm (notes, older handwritten notes, board, intro slides)
  • 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 20). Minimum Spanning Trees and Amortized Analysis (notes, older handwritten notes, PPT slides for proof, board)
  • Notes on Kruskal's MST algorithm.
  • Scan of section on Kruskal and MSTs from Kleinberg/Tardos (WebISO access only).
  • Notes on the union-find data structures, both the list-based one we did in lecture, and (optional) the tree-based one we did not get to.
    I find this proof more accessible than Kozen's proof, try it and see what you think.
  • Basic animations of Kruskal/Prim's algorithms
  • Optional: Wayne's slides on the tree-based data structures, and a proof that any (reasonable) union-find data structure takes inverse Ackermann-time.
  • Optional: Kozen's chapters 2, 3 on MST and a generalization called Matroids, and the chapter on Union-find.


• Lecture 3 (Jan 25). Hashing 1 (board).
  • Notes on hashing.


• Lecture 4 (Jan 27). Hashing 2 (board).
  • Notes on hashing (same as above notes on hashing).
  • Detailed description of the proof sketch (on Cuckoo hashing) covered in this lecture can be found here.


• Lecture 5 (Feb 1). Amortization. Shortest Paths (Dijkstra). (amortization notes, handwritten notes, some slides animating Dijkstra)
  • Chapter from Kozen on Dijkstra.
  • Animation of a (max) heap based priority queue data structure.
    Do you see how all operations take $O(\log n)$ time in the worst-case?
  • Optional: Lecture notes from 15-451 on shortest-path algorithms.
  • Optional: Kevin Wayne's original slides on binary and binomial heaps and Fibonacci heaps. Also Kozen's chapter binomial heaps


• Lecture 6 (Feb 3). Dynamic Programming.
  • Lecture notes (and a recitation worksheet) from the 15-451 course, discussing several problems, via memoization and table-filling.
  • Notes for small-space implementations for DP.
  • Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).


• Lecture 7 (Feb 8). Hashing 3: Algorithms for Streaming Data (board).
  • Lecture notes on streaming.


• Lecture 8 (Feb 10). Hashing 4: Load balancing (board).
  • Lecture notes on load-balancing from previous year's 15-750.
  • (Additional reading) Some detailed examples/exercises on Chernoff bounds.


• Lecture 9 (Feb 15). Dimension Reduction 1: Preserving Pairwise Distances (JL Transform) (board).
  • SciKit's random projection implementation.
  • Lecture notes on JL Transform from a previous year.
  • (Optional) Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas.
  • (Optional) Fast JL transforms: Ailon-Chazelle Ailon-Liberty.
  
  
• Lecture 10 (Feb 17). Dimension Reduction 2: Principal Component Analysis and Singular Values (board).
  • Chapter 11 (and slides) from the MMDS book about PCA, SVD, etc.
  • (Optional) Chapter 3 from the Blum-Hopcroft-Kannan book.


• Lecture 11 (Feb 22). Algorithms for Coding 1 (Slides).
  • You might find the scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course useful (although there are some differences in topics covered): Scrie notes 1, Scribe notes 2.
  • (Optional) Chapter 1 from David MacKay's book.


• Lecture 12 (Feb 24). Algorithms for Coding 2 (Slides).
  • You might find the scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course useful (although there are some differences in topics covered): Scrie notes 2, Scribe notes 3.


• Lecture 13 (Mar 3). Algorithms for Coding 3 (Slides).
  • Lecture notes on basic concepts on polynomials and Reed-Solomon codes from Spring 2019 15-451/651.


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


• Lecture 15 (Mar 17). Optimization II: Linear Programming (introduction, applications).
  • Notes about LPs from our 15-451 course.
  • Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters: Introduction, Examples, LP Basics.
  • The online LP solver we used: it's useful to play with, especially if you haven't seen LPs before.
  • Optional: Compressive sensing (from previous years), with html and jupyter notebooks: basis pursuit (L1 minimization) for sparse signal recovery.


• Lecture 16 (Mar 22). Optimization III: Linear Programming (duality, algorithms).
  • Some preliminary notes I've started writing: here.
  • Notes about LP duality from our 15-451 course. Please ignore the first part about Seidel's algorithm.
  • Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters: Introduction, Examples, LP Basics.
  • The simple online LP solver we used.
  • More serious solvers: CVXOPT and PuLP: Solving linear/convex optimization problems in Python. Free LP solver from COIN-OR. Commercial ones from Gurobi and CPlex.


• Lecture 17 (Mar 24). NP Hardness and Limits of Efficient Algorithms. (draft notes, older handwritten notes)
  • Notes from 15-451, and worksheet.


• Lecture 18 (Mar 29). Combating Intractability via Approximations (notes)
  • The Williamson-Shmoys book on Approximation algorithms is an excellent source.
  • Karp's original paper, and a more recent list of hard problems.


• Lecture 19 (Mar 31). Online Decision Making I: Online Algorithms and Competitive Analysis (online algos notes from 15-451)


• Lecture 20 (Apr 5). Online Decision Making II: The Experts Problem and the Multiplicative Weights Framework (handwritten notes)
  • Slides by Avrim Blum.
  • Notes from our 15-859 course.


• Lecture 21 (Apr 12). Compression 1 (Slides).
  • Guy Blelloch's notes on compression. Chapters 1, 2 and 3 are relevant to the lecture material.
  • (Optional) Claude Shannon's 1948 paper.


• Lecture 22 (Apr 14). Compression 2 (Slides).
  • Guy Blelloch's notes on compression. Chapters 4, 6 and 7 are relevant to the lecture material.


• Lecture 23 (Apr 19). Online Decision III and Optimization IV: The Gradient Descent Framework (handwritten notes)
  • Notes from 15-451.
  • Optional: Potential function proofs of first-order methods by Nikhil Bansal and myself.
  • Optional: Books by Elad Hazan and Shai Shalev-Shwartz get a lot more into the material.


• Lecture 24 (Apr 21). Graphs via Matrices: Spectral Graph Theory (handwritten notes from S20)
  • A linear algebra review.
  • Notes on random walks by Avrim Blum.
  • A book (in progress) by Spielman, and notes by Trevisan.


• Lecture 25 (Apr 26). Laplacian Recap, Cheeger's Inequality, and Random Walks (handwritten notes on random walks from S20)
  • We will only test you on the Cheeger and connectivity part, not on the random walks part. See previous lecture's notes.
  • 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 26 (Apr 28). Course Review.

Recitations

• Recitation 1 (Feb 18): Finite fields (Slides).