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

Fluid Flow Image

This page is superseded by the general course homepage.

Instructors: Guy Blelloch Gary L Miller
Time: Tuesday and Thursday 10:30 - 11:50 (1st class Sept. 7)
Place: 4615A Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
  • Course overview and topic list.
  • Approximate schedule.
  • Assignments.
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms
  • Class List

    • Course Overview:

    Although all but the simplest algorithms are often derided as being impractical, in reality sophisticated algorithms are used in many applications. The goal of the class is to get an appreciation of where algorithms are used and to understand the various considerations and tradeoffs used in designing algorithms (e.g. time, space, generality, and quality of the solution). I encourage both theory and system's students to take the class. Problems we will consider include:
  • Data Compression
  • Cryptography
  • Linear Programming
  • Integer Programming
  • Triangulation and Meshing
  • The N-body Problem
  • Pattern Matching in Computational Biology
  • Indexing and Search Engines
    • We will spend 2 to 4 lectures on each topic. Each student will be expected to complete a set of homeworks, and take a final. The grade will be partitioned as follows:
  • Assignments -- 70%
  • Take home Final -- 30%

    • The main reading will be the course lecture notes (300 pages, .8Mbytes compressed). These notes are also available separately by topic. We will also hand out some additional readings for each topic.

    Assignments

  • Assign 1 Compression (Due Sept 28)
  • Assign 2 Crypto + Linear/Integer Programming (Due Oct 28)
  • Assign 3 Triangulation + Nbody (Due Nov 18)

    • Relevant Books

    See the lists within each of the topic pages

    Help on giving presentations:

  • How to Present a Paper in Theoretical Computer Science, by Ian Parberry.
    • Guy Blelloch, guyb@cs.cmu.edu.