15-853 Fall 2019: Algorithms in the Real World

Course information

Instructor

Rashmi Vinayak (rvinayak)

TAs

Naama Ben-David (nbendavi) and Francisco Maturana (fmaturan)

Time

Lectures: Tuesday, Thursday 3:00-4:20pm. Recitations and make-up lectures: Friday 3:00-4:20pm.

Location

GHC 5222

Email

All email addresses are @cs.cmu.edu.

Announcements

• 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.

Project

• 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.

Project report

• Please use this outline for your report: [pdf], [tex], [style file].
• Write carefully so that it is understandable. This carries weight.
• Same format even for surveys: you need to distill what you read, compare across papers and bring out the commonalities and differences, etc.

Assignments

• 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 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.

Logistics

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.

Schedule

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>”.

Evaluation

The following are subject to minor changes.

• Homework assignment: 40%
• Final exam: 25%
• Final project: 25%
• Scribing lectures: 5%
• Class participation: 5%