15-853 Fall 2019: Algorithms in the Real World

Course information

Rashmi Vinayak (rvinayak)
Naama Ben-David (nbendavi) and Francisco Maturana (fmaturan)
Lectures: Tuesday, Thursday 3:00-4:20pm. Recitations and make-up lectures: Friday 3:00-4:20pm.
GHC 5222
All email addresses are @cs.cmu.edu.



Project report


For questions about Gradescope, please check the student guide on how to use Gradescope or contact canvas-help@andrew.cmu.edu for technical support.

Homework collaboration policy

You may discuss homework problems with other students after trying to solve them by yourself. Each student writes their own solutions.

Course topics

This course covers how algorithms and theory are used in “real world” applications. It is organized by topics and the topics change from year to year.

This year, we will cover the following topics:

  1. Error correcting codes:
    • Foundational concepts from coding theory: linear codes, distance, finite fields.
    • Fundamental limits: minimum overhead needed for resilience.
    • Channel coding algorithms: Reed-Solomon (storage), Low-density-parity-check, Fountain/Raptor.
  2. Compression:
    • Foundational concepts from information theory: entropy, mutual information, …
    • Fundamental limits of compression: lossy vs lossless.
    • Compression algorithms: Huffman, Arithmetic, Burrows-Wheeler, …
    • Graph compression.
  3. Hashing:
    • Balls-and-bins, power-of-2-choices, Cuckoo hashing.
    • Bloom filters.
    • Concentration bounds.
    • Streaming algorithms via hashing.
  4. Cryptography:
    • Private key cryptosystems
    • Public key cryptosystems
  5. Optimization and Machine Learning (topics subject to change):
    • Dimensionality reduction: SVD, PCA, Random projections, Johnson-Lindenstrauss

Previous versions of this course.


Instructor office hours
By appointment (send email with subject “15-853…”).
TA office hours (subject to change)
Naama (GHC 6002): Wednesday 2-3pm. Francisco (GHC 9005): Monday 1-2pm.


Date Topic Notes
Tu Sep 3 Course introduction + Lecture on ECC #1 [Slides] [Scribe notes]
Th Sep 5 Error Correcting Codes #2 [Slides] [Scribe notes]
Fr Sep 6 Recitation: Linear Algebra review [Notes]
Tu Sep 10 Error Correcting Codes #3 [Slides] [Scribe notes]
Th Sep 12 Error Correcting Codes #4 [Slides] [Scribe notes]
Fr Sep 13 Recitation: Polynomials [Slides]
Tu Sep 17 Error Correcting Codes #5 [Slides] [Scribe notes]
Th Sep 19 No lecture
Fr Sep 20 Recitation: Probability [Notes]
Tu Sep 24 Error Correcting Codes #6 [Slides] [Scribe notes]
Th Sep 26 Error Correcting Code #7 [Slides] [Scribe notes]
Fr Sep 27 No lecture or recitation
Tu Oct 1 Error Correcting Code #8 and Compression #1 [Slides], [Scribe notes], Compression notes, LT Codes paper, Raptor Codes paper
Th Oct 3 Compression #2 [Slides],[Scribe notes]
Tu Oct 8 Compression #3 [Slides],[Scribe notes]
Th Oct 10 Compression #4 [Slides],[Scribe notes]
Fr Oct 11 No lecture or recitation
Tu Oct 15 Compression #5 [Slides],[Scribe notes]
Th Oct 17 Hashing #1 [Instructor notes],[Scribe notes]
Tu Oct 22 Hashing #2 [Instructor notes],[Scribe notes], Ten "Practical Theory" Papers, Power of Two Choices Survey
Th Oct 24 Hashing #3 [Instructor notes], [Scribe notes]
Tu Oct 29 Guest lecture: Graphs Compression by Laxman Dhulipala
Th Oct 31 Cryptography #1 [Slides], [Scribe notes]
Fr Nov 1 Recitation: Eigenvalues and SVD [Slides]
Tu Nov 5 No lecture Due to PDL retreat. Lecture will be rescheduled.
Th Nov 7 Cryptography #2 [Slides], [Scribe notes]
Fr Nov 8 Hashing #4 [Instructor notes], [Scribe notes]
Tu Nov 12 Hashing #5 [Instructor notes], [Scribe notes]
Th Nov 14 Hashing #6 [Instructor notes], [Scribe notes], Mining of Massive Datasets Book
Tu Nov 19 Dimensionality Reduction [Instructor notes], [Scribe notes]
Th Nov 21 Final review [Slides]
Tu Nov 26 Final exam
Th Nov 28 No lecture Due to Thanksgiving holiday.
Fr Nov 29 No recitation Due to Thanksgiving holiday.
Tu Dec 3 Project presentations Project reports due 2:30pm
Th Dec 5 Project presentations

Scribe notes

Deadline: one week from the day of the lecture.

Scribe sign-up sheet.

Download the template style file and document file (both files are necessary and should be placed in the same directory). Edit the document file with your scribe notes. Compile to pdf and email the pdf output along with your document file (.tex) to both TAs with subject “15-853 Scribe notes lecture <date of lecture MM/DD>”.


The following are subject to minor changes.