15-750: Algorithms in the Real World, Fall 2023

Lecturer: Rashmi Vinayak (rvinayak@cs).

TAs: Yash Savani (ysavani@cs), Billy Yan (yunzhouy@andrew).

Office hours: Yash Savani (Wed 4:30-5:30pm) Billy Yan (Mon 2:30 - 3:30pm) (Any changes will be updated in the calendar below).

Contacting us: Please use private messages on Piazza instead of emailing the course staff; this helps messages to not get lost.

Lecture location: GHC 4303, Tue/Thu 11:00-12:20.

Piazza: https://piazza.com/cmu/fall2023/15750/home

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

Course Details and Policies

• Please read the course policies carefully!!!
• Links to resources to help brush up on your background.
• The course page will develop more as we proceed through the lectures.

Lectures

• Lecture 1 (Aug 29). Introduction, Triangle Counting, Strassen's Algorithm
  • Course introduction slides
  • Notes
  • Some resources from previous iterations of the course: older 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 (Aug 31). Minimum Spanning Trees (notes, older handwritten notes)
  • 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.
    
  • Basic animations of Kruskal/Prim's algorithms


• Lecture 3 (Sept 5). Amortization + Shortest Paths with Dijkstra
  • Notes on amortization
  • Some resources from previous iterations of the course: handwritten notes, some slides animating Dijkstra
  • Optional: Lecture notes from 15-451 on shortest-path algorithms.


• Lecture 4 (Sept 7). 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 implementation of LCS.
  • Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).
  • For the initial part of the lecture which covered Heaps: Animation of a (max) heap based priority queue data structure.
    


• Lecture 5 (Sept 12). Hashing 1: Hashing with SUHA, analysis of collisions, two-level hashing
  • Notes on hashing


• Lecture 6 (Sept 14). Hashing 2: cuckoo hashing, relaxing SUHA, hash function constructions
  • Notes on hashing (which includes topics discussed in this lecture).
  • A detailed discussion on the proof sketch of Cuckoo hashing covered in the lecture can be found here.


• Lecture 7 (Sept 19). Hashing 3: Load balancing (balls and bins)
  • Notes on load-balancing.
  • (Additional reading) Some detailed examples/exercises on Chernoff bounds.


• Lecture 8 (Sept 21). Two Choices, Bloom filters, Data Streaming Model 1
  • Notes on hashing (which includes Power-of-Two-Choices and Bloom filters).
  • Notes on streaming.


• Lecture 9 (Sept 26). Data Streaming Model 2, Locality Sensitive Hashing and Near-Neighbor Search
  • Notes on streaming (same as the one from the previous lecture).
  • Notes on near-neighbor search and LSH.
  • Chapter on LSH/NN search from the MMDS book (you can skip Section 3.8 onwards).


• Lecture 10 (Sept 28). Dimensionality Reduction: Preserving pairwise distances (JL Transform)
• 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 11 (Oct 3). Principal Component Analysis (PCA)
• Chapter 11 (and slides) from the Mining Massive Datasets book by Leskovec, Rajaraman, and Ullman.
• (Optional) Chapter 3 from the Blum-Hopcroft-Kannan book.


• Lecture 12 (Oct 5). Principal Component Analysis (PCA) - 2, SVD
• Chapter 11 (and slides) from the Mining Massive Datasets book by Leskovec, Rajaraman, and Ullman.
• (Optional) Chapter 3 from the Blum-Hopcroft-Kannan book.


• Lecture 13 (Oct 10). Midterm review


• Lecture 14 (Oct 12). Midterm exam day


• Lecture 15 (Oct 24). 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 16 (Oct 26). Compression 2 (Slides)
  • Guy Blelloch's notes on compression. Chapters 3, 4, and 6 are relevant to the lecture material.


• Lecture 17 (Oct 31). Lossy Compression and Algorithms for Channel Coding (Slides)
  • You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scrie notes 1
  • (Optional) Chapter 1 from David MacKay's book.


• Lecture 18 (Nov 2). Algorithms for Channel Coding: basic concepts, number theory (Slides)
  • You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scrie notes 2
  • (Optional) Chapter 1 from David MacKay's book.


• Lecture 19 (Nov 9). Algorithms for Channel Coding: Algebraic codes (Notes in the form of slides)
  • You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scribe notes 3.


• Lecture 20 (Nov 14). Algorithms for Channel Coding: Graph-based codes (Notes in the form of slides)
  • You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scribe notes 4 and Scribe notes 5.


• Lecture 21 (Nov 16). Optimization I: Flows and Matchings
  • Notes 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 22 (Nov 21). Optimization II: Linear Programs
  • 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.
  • An online LP solver: it's useful to play with, especially if you haven't seen LPs before.
  • 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 23 (Nov 28). Optimization III: Convex minimization and Gradient Descent
  • Notes from our 15-451 (The coverage in this notes is different from what we saw in the lecture. But the contents are mostly relevant.).


• Lecture 24 (Nov 30). Optimization IV: Decision making under uncertainty: Prediction with experts and Online algorithms
  • The coverage in the below notes are different from what we saw in the lecture. But some parts of the contents from each are relevant.
  • Notes on prediction with experts from 15-451
  • Notes on online algorithms from 15-451
  • Notes on Multiplicative weights algorithm from 15-859


• Lecture 25 (Dec 5). Guest lecture by Prof. Nina Balcan on Machine Learning for Algorithm Design
  • Slides
  • Chapter 29. "Data-driven algorithm design" in the "Beyond the Worst-Case Analysis of Algorithms" book, Cambridge University Press, 2020.


• Lecture 26 (Dec 7). Course review.