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.