15-499: Algorithms and Applications
Carnegie Mellon University, Computer Science Department
Spring 2003

Fluid Flow Image


Instructor: Guy Blelloch
    (Office hours Mondays 1:30-2:30pm, Wean 7125)
TA: Shuchi Chawla
    (Office hours Thursdays 1:30-2:30pm, Wean 4104)
Time: Tuesday and Thursday 12:00 - 1:20
Place: BH A53
Credit: 12 Units
Prerequisites: 15-451 or permission from the instructor
  • Readings, Notes and Slides
  • Course Overview and Topic List
  • Course Requirements and Grading Criteria
  • Approximate Schedule
  • Assignments
  • Information on algorithms available on the web
  • Class List

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

    We will cover the following topics:

    Data Compression

    We will start by talking about information theory and why it plays a critical role in data compression. We will then go into many data compression techniques and algorithms including, Huffman codes, arithmetic codes, Lempel-Ziv and gzip, Burrows-Wheeler and bzip, and transform coding and JPEG/MPEG. We will also talk about recent work on compressing structured data such as graphs and triangulated meshes. These techniques are full of interesting theory.

    Cryptography

    We will talk both about algorithms and protocols. Protocols we will cover will include private and public key cryptography, digital signatures, secure hash functions, authentication, and digital cash. Algorithms and applications we will cover will include Rijdael (the new standard for private key cryptography), RSA, ElGamal, Kerberos, and Miller-Rabin.

    Error Correcting Codes

    Error correcting codes are perhaps the most successful application of algorithms and theory to real-world systems. Most of these systems, including DVDs, DSL, Cell Phones, and wireless, are based on early work on cyclic codes, such as the Reed-Solomon codes. We will cover cyclic codes and their applications, and also talk about more recent theoretical work on codes based on expander graphs. Such codes could well become part of the next generation of applications, and also are closely related to other theoretical areas.

    Computational Biology

    Indexing and Searching


    Requirements and Grading Criteria


    Assignments: We will have 6 written assignments during the semester, one for each topic (2 for compression). All students have to write these up individually.

    Project: We will have one group project. The idea of the project is to implement some algorithm and run experiments on it. You will have to give the instructor a one page outline of what you plan to do by April 1, no joke. You will then present your project during the last week of class, and hand in a short writeup (3-5 pages) by Friday May 2. More information to come.

    Midterm and Final: We will have a midterm (March 11) and a 3 hour final.

    Readings: Readings will vary from topic to topic and you should look at the Readings, Notes and Slides page to see what they are.

    Grade partitioning:

  • Assignments -- 40%
  • Midterm -- 10%
  • Project -- 25%
  • Final -- 25%

  • Assignments


  • Assign 1a: Data Compression 1 (ps and pdf), solution (ps and pdf) : Due Jan 28, 2003
  • Assign 1b: Data Compression 2 (ps and pdf), solution (ps and pdf) : Due Feb 11, 2003
    Here is a version with the new table for problem 1: (ps and pdf)
    You can use either version.
  • Assign 2: Cryptography (ps and pdf), solution (ps and pdf) : Due Feb 25, 2003
  • Assign 3: Computatational Biology (ps and pdf) solution (ps and pdf) : Due Mar 20, 2003
  • Assign 4: Indexing and Searching (ps and pdf) solution (ps and pdf) : Due Apr 15, 2003
  • Assign 5: Error Correcting Codes (ps and pdf) solution (ps and pdf) : Due Apr 24, 2003

  • A small sample of companies that sell products that use various algorithms:


    Optimization
    Geometry and Meshing
    Biology
    Cryptography
    CPLEX
    CAPS Logistics
    IBM OSL
    Astrokettle
    APC
    Carmen Systems
    Lindo Systems
    LogicTools
    Fluent
    Geomagic
    Pointwise
    Ansys
    FEGS
    CFDRC
    Marc
    Femsys
    AVL
    Celera
    Curagen
    HGSI
    MLNM
    Hyseq
    Genset
    Incyte
    Variagenics
    Algorithmic Research
    RSA Security
    Entrust
    Cryptomathic
    Netegrity
    InterTrust
    Zero Knowledge
    Mach 5
    Trick's List Owen's List Netsci's list Rivest's List


    Help on giving presentations:


  • How to Present a Paper in Theoretical Computer Science, by Ian Parberry.

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