15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Fall 2002
- 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:
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:
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.
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
Relevant Books
See the lists within each of the topic pages
Help on giving presentations:
Guy Blelloch,
guyb@cs.cmu.edu.