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

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

**Compression**:- Foundational concepts from information theory: entropy, mutual information, …
- Fundamental limits of compression: lossy vs lossless.
- Compression algorithms: Huffman, Arithmetic, Burrows-Wheeler, …
- Graph compression.

**Hashing**:- Balls-and-bins, power-of-2-choices, Cuckoo hashing.
- Bloom filters.
- Concentration bounds.
- Streaming algorithms via hashing.

**Cryptography**:- Private key cryptosystems
- Public key cryptosystems

**Optimization and Machine Learning (topics subject to change)**:- Dimensionality reduction: SVD, PCA, Random projections, Johnson-Lindenstrauss

## 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

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.

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%