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

Readings, Notes and Slides

Introduction
Compression
String Searching
Computational Biology
Spatial Decompositions and Nearest Neighbors
Locality: Memory-Efficient Algorithms
Parallelism: Processor-Efficient Algorithms
Linear and Integer Programming
Cryptography

Cryptography

Readings

Introduction to cryptography. An introduction from the PGP folks. This is not a technichal document, but gives some good overview and introduction to the terminology.
Introduction to Cryptography: Course Notes (30 pages). This is still in rough shape, and here are some bug fixes.
AES Proposal: Rijndael.
Cryptography Links.
Mathematical Background reading (Groups, Fields, etc). Completely optional.
- Mathematical background to an upcoming complexity textbook by Arora and Barak. See sections A.3 - A.4. Very concise.
- Online cryptography textbook by Goldwasser and Bellare. Appendix C (page 255) contains useful mathematical background.
- Abstract Algebra, 2nd Edition by Dummit & Foote. Classic textbook. Very comprehensive.

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

Readings

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.

Slides

Linear/Integer Programming 1 Introduction & formulations, geometric view, simplex method, duality.
Linear/Integer Programming 2 Ellipsoid method, interior point methods.
Linear/Integer Programming 3 Introduction to integer programming, branch and bound solutions.

Parallelism

Readings

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

Readings

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

Slides

Lecture 1-2: Introduction, Sorting List ranking, B-trees, Buffer trees
Lecture 2.5: Cache-oblivious algorithms, matrix multiplication, searching, distribution sort
Clarification on cache-oblivious matrix multiply I wasn't as clear as I would have liked on the matrix-multiply algorithm. Here are some slides that should provide some clarification.

Spatial Decompositions and Nearest Neighbors

Readings

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

Readings

Lectures on BioInformatics from the Max Planck Institute.
- General Gap Models
- Alignment Applet for the dynamic program (using, e.g., the BLOSUM62 score matrix).

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

String Searching

Slides

Lecture: suffix trees

Readings (supplementary, but you must understand suffix trees)

A gentle introduction to Suffix Trees
More details on Suffix Tree construction (including applet and code)
Chapter on suffix trees (Gusfield's book) (Available from CMU IP address only)
Applications of Suffix Trees (Notes from MIT)
Building Suffix Trees and Arrays (Notes from MIT)

Compression

Readings

Introduction to Data Compression.
This is a required reading.
The Large Text Compression Benchmark by Matt Mahoney.
This is for browsing.

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

Introduction

Guy Blelloch, guyb@cs.cmu.edu.