15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Spring 2014
- Instructor:
Guy Blelloch and
Anupam Gupta
- TA:
Dougal Sutherland
- Time: Tuesday and Thursday 1:30 - 2:50 (Starting Jan. 14)
- Place: 4303 Gates Center
- Credit: 12 Units
- Prerequisites: An advanced undergrad course in algorithms
(15-451 or equivalent will suffice).
- Office Hours: Guy: Monday 2:30-3:30pm (GHC 9211), Anupam: Tuesday 3:00-4:00pm (GHC 7203), Dougal: Friday 3:30-4:30pm (GHC 6505)
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
Hashing
Diminsionality Reduction
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
String Searching/Matching
Suffix Arrays and Suffix Trees
Computational Biology
Approximate String Matching
Various gap and cost models
BLAST/FASTA
HMMs for gene detection
Error Correcting Codes
Requirements and Grading Criteria
Readings (handed out per topic)
Homework Assignments (1 or 2 per topic) (50%)
Take-home final exam (20%)
Project (20%)
Grading Assignments (1 over the semester) (5%)
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 Dougal, GHC 6505) for two days at a 20% penalty, and then no longer accepted; talk to us if there are special circumstances.
Assignment 1:
Compression, due January 28 (solutions)
Assignment 2:
Hashing and Streaming, due February 11 (solutions)
Some probability lecture notes, if you'd like a quick refresher
Assignment 3:
LSH, Streaming, Dimension Reduction, due February 25 (solutions)
Assignment 4:
SVD and Parallel Algorithms, due March 18 (solutions)
Assignment 5:
IO-efficient algorithms and LPs, due April 8 (solutions)
Project:
Assignment; proposal due April 8, due May 1
Guy Blelloch,
guyb@cs.cmu.edu.