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

### Nearest Neighbors

• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields by Callahan and Kosaraju (1995).
• Cover Trees for Nearest Neighbor by Beygelzimer Kanade and Langford (2006)

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

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

### Error Correcting Codes

• Introduction to expander graphs by Michel Nielsen.
• Lecture slides:

### Compression

#### Slides

• Lectures 1 and 2: Introduction, Information Theory, Huffman/Arithmetic/Gamma Codes.
• Lecture 2.5: Applications of Probability Coding:
Transform coding: run-length (ITU Fax), move to front, residual coding (JPEG LS)
Context coding: fixed context (JBIG), partial matching (PPM)
• Lecture 3: Lempell-Ziv and Burrows-Wheeler
• Lecture 4: Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000

### Introduction

#### Slides

Guy Blelloch, guyb@cs.cmu.edu.