15-853: Algorithms in the Real World (Guy Blelloch, Fall 08)

### Dimension Reduction and Nearest Neighbors

#### Notes

• Notes from Lecture 1 (Courtesy of Derek Chang)
• Notes on Chernoff bounds (and other large deviation bounds)
• The paper on Well Separated Pair Decompositions described in class. (Callahan and Kosaraju, 1995) (Lecture 2)
• The Wikipeida entry on cover trees and the paper on the topic. (Lecture 3)

• ### Linear and Integer Programming

• 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.
• Bradley, Hax and Magnanti Applied Mathematical Programming. Chapter 9 (Integer Programming).
• G. L. Nemhauser. The age of optimization: solving large-scale real-world problems.
• These are some other potentially useful readings
• 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.
• Scribe notes on Primal-Dual Algorithms that Daniel wrote up once. Concise treatment of LP duality.

### Error Correcting Codes

• Introduction to expander graphs by Michel Nielsen.
• Lecture slides:
• Lecture 1
Intro, Hamming and linear codes
• Lecture 2
Reed-Solomon and cyclic codes.
• Lecture 3
Expander graphs, Low Densisty Parity Check (LDPC) codes, Tornado codes.

### Cryptography

#### Slides

• Lectures 1 and 2
Introduction: terminology, definitions of security, one-way-functions, protocols
Number theory review: groups, fields, discrete logs, Galois Fields
Private-key systems: block-ciphers, Rijndael
• Lectures 3 and 4.