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

Fluid Flow Image

Instructors: Guy Blelloch
Time: Tuesday and Thursday 1:30 - 2:50, Note: first class is Thursday January 19
Place: 4303 Gates Center
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Monday 1:00-2:00pm

  • Course announcements.
  • Course overview and topic list.
  • Readings, Notes and Slides.
  • Course Requirements and Grading Criteria.
  • Approximate Schedule.
  • Assignments.

  • Announcements:

  • Assignment 2 is posted, see below.

  • Assignment 1 is posted, see below.

  • 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. The exact subtopics might change

  • Compression
    Information Theory
    Huffman/Arithmetic/Gamma Codes
    Context Coding/PPM
    Lempel Ziv/Gzip/Burrows Wheeler
    Graph Compression

  • String Searching/Matching
    Suffix Arrays and Suffix Trees

  • Computational Biology
    Approximate String Matching
    Various gap and cost models
    HMMs for gene detection

  • Nearest Neighbors

  • Locality

  • Parallelism

  • 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

  • Cryptography
    One-way functions, basic protocols
    Number theory review: groups, fields, Galois fields
    Private key cryptosystems (Block Ciphers, Rijdael)
    Public key cryptosystems (SSL, RSA, ElGamal, Diffie-Hellman key exchange)
    Kerberos and Digital Cash

  • 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) (10%)
  • Class participation (10%)

  • Assignments

  • Assignment 1: Compression, due February 2

  • Assignment 2: Cryptography (mostly), due February 16

  • Assignment 3: Linear and Integer Programming, due March 6

  • Assignment 4: Nearest Neighbors and Parallel Algorithms, due April 5

  • Assignment 5: Project, due May 1

  • Assignment 6 (NOT DUE):
    Computational Biology (problems 1-3) and Locality (problems 3-4)

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