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

Fluid Flow Image


Instructors: Guy Blelloch and Bruce Maggs
Time: Monday and Wednesday 10:30 - 11:50 (1st class Wednesday Sept. 11)
Place: 4615a Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: Guy on Mondays 3-4pm, or any other time I'm free if you drop by.

  • 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 plan to cover the following topics.

    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.

    Graph Separators

    Most graphs in practice have small separators, i.e. they can be separated into two almost equal sized parts by removing a relatively small number of edges or vertices. Such graphs include the link structure of the web, the internet connectivity graphs, graphs arising from finite-element meshes, map graphs, and many more. Many algorithms can make use of small separators to greatly improve efficiency. This is true both in theory and in practice. We will cover the state-of-the-art in algorithms for finding graph separators, and for making use of graphs with small separators.

    Logistics

    Facility location, path planning, distribution are all of huge importance in industry. Distributors can save 100s of millions of dollars a year by improving the location of facilities, or the scheduling of their fleets of trucks, trains or planes. We will look at case studies of how algorithms are currently used for such problems, and also study recent theory on this class of problems.

    Privacy in Data

    Gathering data that contains private information is becoming much more prevalent in today's world. Even before 9/11 such data was being collected by many private and public entities. We will look at algorithms that can be used to process this data to gather various statistics without revealing private data.

    Algorithms for Indexing and Searching

    Searching large databases, such as the web, has become. There are many interesting algorithmic techniques that can be used to improve the efficiency and quality of such searches. We will look at how standard search engines store and retrieve data, how Google's pagerank works, and at various techniques for clustering data, such as Latent Semantic Indexing.

    Algorithms for Networking and Data Distribution

    Many interesting algorithms are used in networking. These include algorithms for finding fast routes, algorithms for load-balancing users across servers, and algorithms for finding the best servers based on locality.


    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


    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 4 days starting Dec 11 (Dec 11, 12, 13, 14). You can pick it up on any of those 4 days at noon, and return it by noon two days later.

    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: Error Correcting Codes (Due Sept 26, 2002) - in ps
  • Assign 2: Separators (Due Oct 11, 2002) - in ps or pdf.
    Here are the solutions (written up by Nina and Doru Balcan, with help from others).
  • Assign 3: Exercises on Logistics - part 1 (Due Monday Nov 4)
  • Assign 4: Searching and Secrets - ps (Due Wednesday Dec 4)

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