15-499: Algorithms and Applications
Carnegie Mellon University, Computer Science Department
Spring 2003
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.
We will cover the following topics:
Data Compression
We will start by talking about information theory and why it plays a
critical role in data compression. We will then go into many data
compression techniques and algorithms including, Huffman codes,
arithmetic codes, Lempel-Ziv and gzip, Burrows-Wheeler and bzip, and
transform coding and JPEG/MPEG. We will also talk about recent work
on compressing structured data such as graphs and triangulated meshes.
These techniques are full of interesting theory.
Cryptography
We will talk both about algorithms and protocols. Protocols we will
cover will include private and public key cryptography, digital
signatures, secure hash functions, authentication, and digital cash.
Algorithms and applications we will cover will include Rijdael (the
new standard for private key cryptography), RSA, ElGamal, Kerberos,
and Miller-Rabin.
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.
Computational Biology
Indexing and Searching
Requirements and Grading Criteria
Assignments: We will have 6 written assignments during
the semester, one for each topic (2 for compression). All students
have to write these up individually.
Project:
We will have one group project.
The idea of the project is to implement some algorithm and run
experiments on it.
You will have to give the instructor
a one page outline of what you plan to do by April 1, no joke.
You will then present your project during the last week of class, and
hand in a short writeup (3-5 pages) by Friday May 2.
More information to come.
Midterm and Final:
We will have a midterm (March 11) and a 3 hour 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
A small sample of companies that sell products that use various algorithms:
Help on giving presentations:
Guy Blelloch,
guyb@cs.cmu.edu.