Readings, Notes and Slides

• Introduction
• Compression
• Cryptography
• Linear and Integer Programming
• Nearest Neighbors and Spatial Decompositions
• Parallel Algorithms
• Locality: Memory-Efficient Algorithms
• Computational Biology

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

Locality

Readings

Slides

• Lecture 1-2: Introduction, Sorting List ranking, B-trees, Buffer trees
• Lecture 2.5: Cache-oblivious algorithms, matrix multiplication, searching, distribution sort

Parallel Algorithms

Readings

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. Parallel techniques: contraction.
• Lecture 4. Parallel dynamic programming, Scheduling.

Nearest Neighbors and Spatial Decompositions

Readings

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
  In class we did not get to Bounded Volume Hierarchies.

Linear and Integer Programming

Readings

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.

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 a recent 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

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