15-853: 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

#### Web page

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

### Error Correcting Codes

#### Web page

• Scribe notes from last year.
• Error Detecting and Correcting Codes (scribe notes by Daniel Maynes-Aminzade and Andrew Faulring).
• Reed-Solomon Codes (scribe notes by Anton Likhodedov and Trey Smith).
• Decoding Reed-Solomon Codes (scribe notes by Amitabh Sinha).
• Tornado Codes (scribe notes by Sonesh Surana).

### Linear and Integer Programming

#### Web page

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 interior-point 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 interior-point 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 large-scale real-world 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 )