15-853: Algorithms in the Real World (Guy Blelloch and Jeremy Fineman, Fall 10)

### 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
• Lecture 3
Public-key and Key-exchange systems: Diffie-Hellman, ElGamal, RSA, TLS
Kerberos

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

### Parallelism

• Parallel Algorithms by Guy Blelloch and Bruce Maggs. From Computer Science Handbook, Second Edition, Allen B. Tucker (Editor).
• #### Slides

• Lecture 1. Introduction, concurrency vs. parallelism, nested parallelism, modeling costs with work and span, some examples.
• Lecture 2. Parallel techniques: using collections, divide-and-conquer.
• Lecture 3 (revised). Parallel techniques: contraction.
• Lecture 4. Parallel dynamic programming, Scheduling.

### Locality

• The Input/Output Complexity of Sorting and Related Problems by Aggarwal and Vitter (1988).
• Cache-Oblivious Algorithms by Frigo, Leiserson, Prokop, and Ramachandran (1999).
• The Buffer Tree: A Technique for Designing Batched External Data Structures by Arge (2003).

### Spatial Decompositions and Nearest Neighbors

• Cover Trees for Nearest Neighbor by Beygelzimer Kanade and Langford (2006)
• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields by Callahan and Kosaraju (1995).
• Efficient collision detection using bounding volume hierarchies of k-DOPs, J.T. Klosowski, M. Held J. Mitchell, H. Sowizral, K. Zikan. This has some background on BVH in general.
• #### Slides

• Lecture 1, 2 and 3: Introduction, Quad/Oct/Kd/BSP trees, Nearest Neighbor Search, Metric spaces, Ball/Cover trees, Callahan-Kosaraju, Bounded Volume Hierarchies

### Computational Biology

#### Slides

• Lecture 1: Introduction, Longest Common Subsequence, Edit Distance
• Lecture 2: Sequence Alignment, Local Alignment, Database Searching (BLAST / FASTA)
• Lecture 3: Gene detection with hidden markov models (HMMs), scoring, and decoding

### Compression

#### Slides

• Lectures 1 and 2: Introduction, Information Theory, Huffman/Arithmetic/Gamma Codes.
• Lecture 3: 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.5: Lempell-Ziv and Burrows-Wheeler (only covered Burrows Wheeler in class)
• Lecture 4: Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000

### Introduction

#### Slides

Guy Blelloch, guyb@cs.cmu.edu.