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

Fluid Flow Image

Instructors: Guy Blelloch and Jeremy Fineman
Time: Tuesday and Thursday 10:30 - 11:50, Note: first class is September 7
Place: 4303 Gates Center
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: (Guy) Monday 1:00-2:00pm, (Jeremy) Thursday 2:00-3:00pm
  • Course announcements.
  • Course overview and topic list.
  • Readings, Notes and Slides.
  • Course Requirements and Grading Criteria.
  • Approximate Schedule.
  • Assignments.
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms

    • Announcements:

  • Assignment 5 has been posted.

  • A revised version of the slides from Lecture 3 on parallel algorithms have been posted. The original version had several confusing typos.

  • The project description is now posted under assignments. It is due Nov 18.

  • The due date of assignment 4 has been delayed until Thursday (Oct 28).

  • Supplementary slides on cache-oblivious matrix multiplication have been posted (on the Notes and Slides page) to help clarify the issues.

  • Assignment 4 has been posted and is due on Tuesday (Oct 26).

  • Jeremy's office hours have moved to 2-3 on Thursdays. (Formerly at 3-4)

  • The slides on Spacial decompositions have been updated to include the third lecture.

  • Assignment 3 has been posted and is due on Tuesday (Oct 12).

  • Assignment 2 solutions have been posted. The assignment was handed back in class. Jeremy has any that were not picked up.

  • There was a bug in the PPM example in the compression reading, in particular for the case when characters are excluded. This has been fixed in the copy you can now download from the "Readings, Notes and Slides" page.

  • Assignment 2 has been posted and is due on Tuesday (Sept 28).

  • Assignment 1 solutions have been posted. The assignment was handed back in class. Guy has any that were not picked up.

  • Assignment 1 has been posted.

    • 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
    BLAST/FASTA
    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 Midterm (10%)
  • Take-home final exam (20%)
  • Grading Assignments (1 over the semester) (10%)
  • Class participation (10%)

    • Assignments

  • Assignment 1: Compression 1, due September 16

  • Assignment 2: Compression 2, due September 28

  • Assignment 3: Computational Biology, due October 12

  • Assignment 4: Nearest Neighbors and Locality, due October 28

  • Project: Nearest Neighbors and Locality, due Novermber 18

  • Assignment 5: Parallel Algorithms, Linear/Integer Programming, Cryptography, due December 2
    •

    Relevant Books

    See the lists within each of the topic pages

    Guy Blelloch, guyb@cs.cmu.edu.