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

Fluid Flow Image

This page is superseded by the general course homepage.

Instructors: Guy Blelloch and Bruce Maggs
Time: Tuesday and Thursday 1:30 - 2:50 (1st class Thursday Sept. 14)
Place: 5409 Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
  • 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

    • 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
  • Internet Algorithms and Protocols
  • Indexing and Search Engines
  • Pattern Matching in Computational Biology
    • Note:This year we will be including more topics to do with the internet, including routing algorithms, error-correcting codes, and web caching.

    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 26)
  • Assign 2 Compression II (Due Oct 12). Notes.
  • Assign 3 Error Correcting Codes (Due Oct 19).
  • Assign 4 Cryptography (Due Nov 7).
  • Assign 5 Internet Protocols (Due Nov 21).
  • Assign 6 Tornado Codes and Indexing/Searching (Due Dec 12).

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