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

Fluid Flow Image


Instructors: Guy Blelloch
Time: Monday and Wednesday 10:30 - 11:50 (1st class, Wednesday Sept. 13)
Place: 5409 Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Monday 1:30-2:30pm

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

  • 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

  • Graphs in the Real World
    Shortest Paths (Mapquest)
    Graph Separators
    Flow and Matching

  • String Searching/Matching
    Suffix Arrays and Suffix Trees

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

  • Web Algorithms
    Inverted indexes and searching
    Google page-rank and Hubs and Authorities
    Near duplicate removeal

  • Requirements and Grading Criteria


  • Readings (handed out per topic)
  • Homework Assignments (1 or 2 per topic) (60%)
  • Take-home final exam (20%)
  • Grading Assignments (1 over the semester) (10%)
  • Class participation (10%)

  • Assignments


  • Assign 1: Compression (ps and pdf), Due October 4
    solution
  • Assign 2: Cryptography (ps and pdf), Due October 25
    solution
  • Assign 3: Graph Separators (ps and pdf), Due November 17
  • Assign 4: Computational Biology (ps and pdf), Due December 1
    solution
  • Assign 5: Indexing and Searching (ps and pdf), Due December 8

  • Relevant Books


    See the lists within each of the topic pages


    Guy Blelloch, guyb@cs.cmu.edu.