- 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.
- Homework 3 is now available. It is due on Nov 20, 11:59pm.
- No lecture on Tuesday, November 5.
- Make-up lecture on Friday, November 8.
- Share the proposal and related papers in the shared Google Drive by Monday (Nov. 11).
- Project reports due on Dec 3 2:30pm.
- Project presentations are in class on Dec 3 and 5.
- Assignment 1 due on October 4, noon. Solution template: [.pdf] [.tex]. Solutions
- Assignment 2 due on October 25, noon. Solution template: [.pdf] [.tex]. Solutions
- Assignment 3 due on Nov 20, 11:59pm. Solution template: [.pdf] [.tex]. Solutions
For questions about Gradescope, please check the student guide on how to use Gradescope or contact email@example.com 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.
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:
- 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.
- Foundational concepts from information theory: entropy, mutual information, …
- Fundamental limits of compression: lossy vs lossless.
- Compression algorithms: Huffman, Arithmetic, Burrows-Wheeler, …
- Graph compression.
- Balls-and-bins, power-of-2-choices, Cuckoo hashing.
- Bloom filters.
- Concentration bounds.
- Streaming algorithms via hashing.
- Private key cryptosystems
- Public key cryptosystems
- 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.
|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|
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.
- Homework assignment: 40%
- Final exam: 25%
- Final project: 25%
- Scribing lectures: 5%
- Class participation: 5%