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

Fluid Flow Image

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

    • Announcements:

  • About assignment 7 and final exam:
  • Since this semester goes really late, we will merge assignment 7 with the take-home final exam.
  • You will have 48 hours to finish them without discussing with anyone (we will consider the level of difficulty for assignment 7).
  • You can get the problems no earlier than 3pm on Dec 9 (Wednesday, after class), and hand it back no later than 5pm on Dec 15 (Tuesday).
  • You can pick any 48h that is the most convenient for you.
  • We only provide hard copies of the assignment+exam. Exceptions should be granted by instructors.
  • We require you to type your answer in either LaTex or WinWord. There will be no time for you to dispute the grading, so try to make your answers as clear as possible.

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