15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Fall 2015
- Instructor:
Guy Blelloch and
Anupam Gupta
- TA:
Yan Gu
and Colin White
- Time: Monday and Wednesday 1:30 - 2:50 (Starting Sep. 9)
- Place: 4307 Gates Center
- Credit: 12 Units
- Prerequisites: An advanced undergrad course in algorithms
(15-451 or equivalent will suffice).
- Office Hours: Anupam: Tuesday 3:30pm-4:30pm (GHC 7203), Guy: Wednesday 3pm-4pm (GHC 9211), Colin: Thursday 2pm-3pm (GHC 7507),
Yan: Monday 3pm-4pm (GHC 7707)
Announcements:
Course Overview:
This course covers how algorithms and theory are used in "real-world"
applications. The course will cover both the theory behind the
algorithms and case studies of how the theory is applied. It is
organized by topics and the topics change from year to year.
This year we will cover the following topics:
Compression
Information Theory
Huffman/Arithmetic/Gamma Codes
Context Coding/PPM
Lempel Ziv/Gzip/Burrows Wheeler
Graph Compression
Error Correcting Codes
Hamming and Hadamard Codes
Reed-Solomon Codes
Low-Density Parity Check (LDPC) codes
Cryptography
Hashing
Hashing and Bloom Filters
Load Balancing
Hashing for Similarity
The Data Streaming Model
Dimensionality Reduction
Random Projections and Johnson-Lindenstrauss
Singular-Value Decompositions
Compressive Sensing
Parallel Algorithms
Locality and I/O Efficient Algorithms
Linear and Integer programming
Flow problems as Linear programs
Simplex, Elipsoid and Interior point methods
Reductions to integer programs
Basic techniques for solving integer programs
Airline crew scheduling
Requirements and Grading Criteria
Readings (handed out per topic)
Homework Assignments (1 or 2 per topic) (70%)
Take-home final exam (25%)
Class participation (5%)
Assignments
Assignments are due at the beginning of class on the listed day. Late assignments will typically be accepted (give them to either Yan at GHC 7707 or Colin at GHC 7507) for two days at a 20% penalty, and then no longer accepted; talk to us if there are special circumstances.
Assignment 1:
Compression, due Sep 21 (solutions)
Assignment 2:
Coding, due Oct 7 (solutions)
Assignment 3: Cryptography, due Oct 21 (solutions)
Assignment
4: Hashing, due Nov
4 (solutions)
Assignment 5: LSH, due Nov 16
(solutions)
Assignment 6: Parallel Algorithms and Locality, due Dec 2 (solutions)
Guy Blelloch,
guyb@cs.cmu.edu.