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

Fluid Flow Image

Instructor: Guy Blelloch
TA: Laxman Dhulipala and Yihan Sun
Time: Tuesday and Thursday 10:30 - 11:50 (Starting Jan. 16)
Place: 4307 Gates Center
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Guy: Monday 2-3pm (GHC 9211), Laxman: Friday 5-6pm (GHC 9215), Yihan: Wednesday 1-2pm (GHC 7010)
  • Course announcements.
  • Course overview and topic list.
  • Readings, Notes and Slides.
  • Course Requirements and Grading Criteria.
  • Assignments.

    • 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

  • Parallel Algorithms

  • Locality and I/O Efficient Algorithms

  • Indexing and Searching

  • Nearest Neighbors

  • Dimensionality Reduction
    Random Projections and Johnson-Lindenstrauss
    Singular-Value Decompositions
    Compressive Sensing

    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 Laxman at GHC 9215 or Yihan at GHC 7010) for two days at a 20% penalty, and then no longer accepted; One assignment can be turned in up to 3 days late at no penalty. Talk to us if there are special circumstances.

  • Assignment 1: Compression, Part 1 due Jan 26, Part 2 due Feb 2, Solution
    •
  • Assignment 2: Error Correcting Codes, due Feb 20, Solution
    •
  • Assignment 3: Cryptography, due March 6, Solution
    •
  • Assignment 4: Parallel Algorithms, due March 25, Solution
    •
  • Assignment 5: Locality and I/O Efficient Algorithms, due April 10, Solution
    •
  • Assignment 6: Nearest Neighbor and Dimensionality Reduction, due April 24, Solution
    •
  • Course Project: Handout, Proposal due April 3, Project due May 3

    • Guy Blelloch, guyb@cs.cmu.edu.