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

Fluid Flow Image

Instructors: Guy Blelloch
Time: Tuesday and Thursday 10:30 - 11:50, Note: first class is September 8
Place: 4102 Gates Center
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Tuesday 1:00-2: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:

  • We will have a guest lecturer, Jeremy Fineman, on Tuesday December 1. He will talk about models for analyzing algorithms to take account of the memory hierarchy.

  • Solutions to Assignment 5 are posted.

  • Assignment 6 is posted. It is due Dec 3 (last day of classes).

  • On assignment 5 problem 2 please note: (1) there cannot be any sharing of characters between the two strings S1 and S2, (2) by "spaces" I mean characters that appear in T but not in S1 or S2, and (3) it is OK if S1 is completely before S2 or S2 is completely before S1.

  • There will be no class or office hours on Tuesday November 10. I updated the approximate schedule.
    I will hold office hours on Wednesday (Nov 11) at 1:30pm.

  • Assignment 5 is posted. It is due November 12.

  • I sent everyone their midsemester grades based on the first three assignments and the midterm. I calculated them by dropping half of your lowest assignment grade. For the final grade I will drop your lowest assignment grade.

  • Assignment 4 is posted.

  • Midterm:
    For problem 2 you can assume k=3.
    Byte based means every character can have one of 256 possible values.

    For problem 4a, the codeword length is the number of bytes.

  • Solutions to assigment 3 posted.

  • On assignment 3 problem 1 the FindClosest function should not have an argument e. Just ignore it....it was a typo.

  • The takehome midterm will be handed out on October 20 at the end of class and will be due 24 hour later. If this is going to be a problem for you, please tell me ASAP. It will include topics through Error Correcting Codes, and perhaps some simple questions on cryptography (we will be part of the way through the topic). Note that this will be after official midsemester grades are reported. Therefore the official grades won't be very meaningful. Therefore I'll write your overall midsemester grade on the exam when I return it.

  • The takehome final will have a flexible time period. You will be able to pick it up any day between Monday Dec 7 and Friday Dec 11 (inclusive) and hand it back 24 hours later.

  • Assignment 3 has been posted. It is due October 15.

  • Solutions to assignment 1 have been posted.
    Also the Approximate Schedule for the rest of the lectures has been posted (click on bullet item above).

  • Assignment 2 has been posted. It is due Thursday October 1.

  • Assignment 1 has been posted. It is due Thursday September 17. (Sorry, the version I posted earlier on Saturday was in the wrong place. The link should now work, 9PM Saturday the 12th.)

    • 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

  • Error Correcting Codes
    Hamming Codes, Linear Codes
    Reed Solomon Codes, Cyclic Codes (uses in CDs, DVDs, DSL, ...)
    Expander graphs and Tornado codes

  • 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

  • Computational Biology
    Approximate String Matching
    Various gap and cost models
    BLAST/FAST
    Sequencing the Human Genome

  • String Searching/Matching
    Suffix Arrays and Suffix Trees

  • 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

  • Nearest Neighbors

    •

    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 17
    (solutions 1)
  • Assignment 2: Compression 2, due October 1
  • Assignment 3: String Searching and ECC, due October 15
    (solutions 3)
  • Assignment 4: Cryptography, due Nov 3.
    (solutions 4)
  • Assignment 5: Computational Biology, due Nov 12.
    (solutions 5)
  • Assignment 6: Linear and Integer Programming, due Dec 3.

    • Relevant Books

    See the lists within each of the topic pages

    Guy Blelloch, guyb@cs.cmu.edu.