15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Spring 2014

Fluid Flow Image

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)
  • Course announcements.
  • Course overview and topic list.
  • Readings, Notes and Slides.
  • Course Requirements and Grading Criteria.
  • Approximate Schedule.
  • Assignments.

    • Announcements:

  • The project has been posted
  • Assignment 5 been posted (and solutions)
  • Corrected April 1: problem 2(a) and (b) were incorrect
    •
  • Assignment 4 has been posted (and solutions)
  • Assignment 3 has been posted (and solutions)
  • For 2(iii), feel free to show $2e^{-m/256}$ instead of $2e^{-m/128}$.
  • For 3(ii), k is $O(\log D + \log (1/\eta))/\epsilon^2$, not $O(\log D + \log \eta)/\epsilon^2$.
    •
  • Assignment 2 has been posted (and solutions)
  • Assignment 1 has been posted (and solutions)

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