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

Fluid Flow Image

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

  • Clarifications on Final Exam questions
  • Course overview and topic list.
  • Course Requirements and Grading Criteria.
  • Approximate schedule.
  • Readings, Notes and Slides
  • Assignments.
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms
  • Class List

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

    Geometry and Meshing
    CAPS Logistics
    Carmen Systems
    Lindo Systems
    Algorithmic Research
    RSA Security
    Zero Knowledge
    Mach 5
    Trick's List Owen's List Netsci's list Rivest's 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 migh include:
  • Data Compression
  • Error-Correcting Codes
  • Cryptography
  • Linear Programming
  • Integer Programming
  • The N-body Problem
  • Indexing and Search Engines
  • Pattern Matching in Computational Biology
  • Some introductory material.

    Requirements and Grading Criteria

    We will spend 2 to 4 lectures on each topic. Each student will be expected to complete a set of assignments, take the final, and help either grade a homework or take scribe notes for one of the lectures.

    SCRIBE NOTES AND GRADING The scribe notes and granding will work as follows. We will be asking for 2 or 3 volunteers to grade each assignment, and 2 volunteers to take scribe notes for certain lectures (the ones that have not be given in previous years). All students need to volunteer for ONE of these two tasks during the semester.

  • GRADING ASSIGNMENTS: We will give each grader a sampling of the assignments the day they are handed in, and you should look over them to get a sense of the types of answers people are giving. We will get together the next day and discuss the answers and any questions you have. We will also divide up the work at that point. You will then need to grade the assignments and write up a good solution by the following week (the solution write-ups for the problems will be divided among the graders). You will learn a lot by grading an assignment and it will be particularly helpful if you felt you did not fully understand the assignment.

  • SCRIBE NOTES: You will be responsible for writing up what was covered in a lecture. This will involve taking careful notes during the lecture and doing some additional background research on the subject to fill in details that were not covered. The notes must be formatted in LaTeX and should be in written in full sentences (not outline form). These notes should be completed within a week of the lecture and will be handed out to the rest of the class. Scribe notes will probably end up being about 10-15 pages.
  • TAKE HOME FINAL: The 48-hour take home final will be given out over a period of 5 days starting Dec 12 (i.e. you can start any time during the 5 day period, but must finish it within 48 hours of picking up the 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 -- 60%
  • Scribe notes -- 10%
  • Take home Final -- 30%

  • Assignments

  • Assign 1 Compression I (Due Sept 24) - in ps or pdf (solution by Jernej Barbich)
  • Assign 2 Compression II (Due Oct 10) - in ps or pdf (notes): (Best solution, by Annie Luo and Marc Fasnacht).
  • Assign 3 Cryptography (Due Oct 24) - in ps or pdf
  • Assign 4 Error Correction (Due Oct 31) - in ps or pdf
  • Assign 5 Linear and Integer Programming (Due Nov 19) - in ps or pdf (solution)
  • Assign 6 Computational Biology (Due Dec 10) - in ps or pdf

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