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

Lecturers: Daniel Sleator (sleator@cs), Rashmi Vinayak (rvinayak@cs).

TAs: Runtian Zhai (rzhai@andrew), Yixuan Mei (yixuanm@andrew).

Office hours: Runtian Zhai (M 2-3pm) , Yixuan Mei (Wed 10-11am) (Any changes will be updated in the calendar below and on Piazza).

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: Link

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 27). Introduction, Triangle Counting, Strassen's Algorithm
  • Course introduction slides
  • Chapter 1 of Anupam's 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 29). Minimum Spanning Trees and Amortized Analysis
  • Chapter 2 of Anupam's notes (MST), (older handwritten notes)
  • Chapter 3 of Anupam's notes (amortized analysis)
  • Optional: Basic animations of Kruskal/Prim's algorithms


• Lecture 3 (Sept 2). The analysis of Union-Find
  • Chapter 3 of Anupam's notes (amortized analysis)
  • 451 (Fall 23) Lecture on Union-Find (log log n bound using a potential function)
  • Optional: Log* analysis of Union-Find (451, Spr 19)


• Lecture 4 (Sept 4). Dynamic Programming
  • Notes Sections 4.4 through 4.6 were covered in lecture.
  • 451 notes on DP Section 1 was covered in lecture.
  • Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).


• Lecture 5 (Sept 10). Hashing 1: Hashing with SUHA, analysis of collisions, two-level hashing
  • Chapter 5 of Anupam's notes (which includes topics discussed in this lecture).


• Lecture 6 (Sept 12). Hashing 2: relaxing SUHA, hash function constructions, Load balancing - 1
  • Chapter 5 of Anupam's notes (which includes topics discussed in this lecture).
  • Notes on load-balancing (which includes topics discussed in this lecture).
  
  
• Lecture 7 (Sept 17). Hashing 3: Load balancing - 2
  • Notes on load-balancing.
  • (Additional reading) Some detailed examples/exercises on Chernoff bounds (which includes topics discussed in this lecture).


• Lecture 8 (Sept 19). Bloom Filters, Data Streaming (Sketching)
  • Chapter 5 of Anupam's notes (which includes notes on Bloom Filters).
  • Chapter 7 of Anupam's notes (which includes topics discussed on streaming).


• Lecture 9 (Sept 24). Suffix Trees and Applications
  • 451 notes on suffix trees (see sections 1 and 2)


• Lecture 10 (Sept 26). Constructing Suffix Arrays
  • The O(n log n) surrogate algorithm (451 notes)
  • The O(n) Skew Algorithm.


• Lecture 11 (Oct 1). 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 12 (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 13 (Oct 8). 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 14 (Oct 22). Optimization I: Flows and Matchings
  • Notes from 15-451
  • Part of the flow chapter from the Kleinberg-Tardos book.
  • Animations of some basic max-flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinics)


• Lecture 15 (Oct 24). Optimization II: Min Cost Flows
  • Notes from 15-451


• Lecture 15 (Oct 29). Optimization III: Linear Programs
  • Anupam's notes on Linear Programming
  • Carl Kingsford's Simplex Slides
  • 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 16 (Oct 31). Decision Making Under Uncertainty 1: Prediction with Experts
  • Prediction from experts and the multiplicative weights algorithm from 15-451
  • Notes on Multiplicative weights algorithm from 15-859


• Lecture 17 (Nov 6). Optimization IIII: Convex minimization and Gradient Descent
  • Notes from 15-451. We will cover sections 1, 2, 3, and 5.
  • Online Convex Programming and Generalized Infinitesimal Gradient Ascent by M. Zinkevich


• Lecture 18 (Nov 12). Decision Making Under Uncertainty 2: Competitive Algorithms
  • Notes from 15-451.


• Lecture 19 (Nov 14). Competitive Algorithms 3, Compression 1 (Notes in slides format)
  • Guy Blelloch's notes on compression. Chapters 1, 2 and 3 are relevant to the lecture material.
  • (Optional) Claude Shannon's 1948 paper.