15853: Algorithms in the Real World (Guy Blelloch, Fall 01)
Readings, Notes and Slides
Note that we will not have slides from all the lectures. Some lectures will
be given on the board, and some slides will be hand done.
Compression
Readings

Introduction to Data Compression I (53 pages, ps.gz or pdf).
Slides
 Compression 1,
(ps,
ps 4up,
ppt
)
 Compression 2,
(ps,
ps 4up,
ppt
)
 Compression 3,
(ps,
ps 4up,
ppt
)
 Compression 4,
(ps,
ps 4up,
ppt
)
Note that this is only a subset of the slides. Many of the "image" slides
were overheads.
Cryptography
Readings
Slides
 Cryptography 1,
(ps,
ps 4up,
ppt
)
 Cryptography 2,
(ps,
ps 4up,
ppt
)
 Cryptography 3,
(ps,
ps 4up,
ppt
)
 Cryptography 4,
(ps,
ps 4up,
ppt
)
Error Correcting Codes
Readings
Slides
Linear and Integer Programming
Readings
These readings will be/have been given out in class.
Gilbert Strang.
Linear Algebra and its Applications. Third Edition.
Chapter 8 (Linear programming and game theory).
This is the most concise and clear introduction to the simplex method I
have read
and it also contains a short description of Karmakar's interiorpoint method.
If you have another source you have already used and feel comfortable with,
feel free to read it instead.
Linear
Programming 2 (Steven Czerwinski). Scribe notes on interiorpoint
methods from a previous version of the course.
Bradley, Hax and Magnanti
Applied Mathematical Programming.
Chapter 9 (Integer Programming).
G. L. Nemhauser.
The age of optimization: solving largescale realworld problems.
This paper has some overlap with the previous paper but concentrates on
applications.
These are some other potentially usefull readings
E. L. Johnson and G. L. Nemhauser.
Recent developments and future directions in mathematical programming.
This is a good overview of optimization techniques including both linear
and integer programming.
Robert Freund and Shinji Mizuno.
Interior Point Methods: Current Status and Future Directions
This is a good overview of interior point methods, and is available online.
Slides
 Linear and Integer Programming 1,
(ps,
ps 4up,
ppt
)
 Linear and Integer Programming 2, (These were overheads and not available electronically)
 Linear and Integer Programming 3,
(ps,
ps 4up,
ppt
)
 Linear and Integer Programming 4,
(ps,
ps 4up,
ppt
)
Computational Biology and Sequence Matching
Scribe Notes
Slides
Indexing and Searching
Readings
Handed out during class, and available outside Keith Ledonne's office (Wean 7116).
Chapters 3 and 4 from:
Ian H. Witten, Alistair Moffat, and Timothy C. Bell.
Managing Gigabytes: Compressing and Indexing Documents and
Images.
Scribe Notes
Back to the Algorithms in the Real World page (V. 2001).
Guy Blelloch,
guyb@cs.cmu.edu.