Readings, Notes and Slides

• Compression
• Hashing
• Dimension Reduction
• Parallel Algorithms
• Locality: Memory-Efficient Algorithms
• Linear and Integer Programming
• String Searching
• Computational Biology
• Coding and Error Correction

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
  

Hashing

Lecture Notes and Pointers

• Lecture 6 (Jan 30): Hashing basics, constructions, Bloom filters.
  
  A survey on Network applications of Bloom filters by Broder and Mitzenmacher
  Bloom filters feature on Jennifer Rexford's top 10 "practical theory" papers list at SIGCOMM.
  
  
• Lecture 7 (Feb 4): Hashing for load balancing: concentration bounds, two-choices, cuckoo hashing.
  
  Two-choices also appear on the Rexford top 10 "practical theory" papers list.
  An application (and extension): Optimistic cuckoo hashing by our own Bin Fan, Dave Andersen, Michael Kaminsky. They also created the Cuckoo Filter!
  
  
• Lecture 8 (Feb 6): Hashing for document similarity: min-hashing and locality-sensitive hashing
  
  (Required) Chapter on minhash and LSH from the Leskovec, Rajaraman, Ullman MMDS book (You can skip Section 3.8 onwards).
  CACM article (author copy) on LSH by Andoni and Indyk (and the technical perspective by Chazelle, which should be read first)
  (Advanced) Indyk's construction of approximate min-hashing using k-universal hash families.
  
  
• Lecture 9 (Feb 11): Hashing for streaming computation: Data streaming model, heavy hitters, distinct elements
  
  The beginning of this chapter (sections 4.1-4.4) from the MMDS book give a good introduction to some of the issues.
  This monograph by S. Muthukrishnan contains a lot of information and pointers.

Dimension Reduction and Near-Neighbor Searching

Lecture Notes

• Lecture 10 (Feb 13): Dimension Reduction: Random Projections and the Johnson-Lindenstrauss Flattening Lemma.
  
  Section 4.5 of this MMDS chapter talks about the AMS Tug-of-War estimator for $F_2$.
  Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Each of these proofs is a bit different.
  Jelani Nelson's notes with different proofs, and many pointers.
  Using J-L for learning applications: robust concept learning and mixtures of Gaussians. There are many other application papers: these are the pioneering ones.
  The Ailon-Chazelle paper on the Fast JL transform.
  
  
• Lecture 11 (Feb 18): Dimension Reduction: SVDs, Principal Components Analysis (PCA), CUR decomposition
  
  Chapter 11 of MMDS gives an introduction into SVD, PCA, CUR, and the like.
  The data for today's demos were from here.

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.

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

Linear and Integer Programming

Readings

• Lecture 18 (Mar 20): Linear Programming basics: Simplex
  
  Chapter 5 (Simplex) (CMU only) of Understanding and Using Linear Programming by Jiri Matousek and Bernd Gaertner.
  The entire book is highly recommended! It is an excellent intro to the basics, simplex, duality, and even ellipsoid and interior-point.
  Lecture notes (postscript file) by Michel Goemans. A nice coverage of linear programming from basic definitions through interior-point methods.
  slides from lecture. (Describes the tableau representation of simplex, which we did not do explicitly.)
  The animation for simplex we did in Lecture 19.


• Lecture 19 (Mar 25): Linear Programming basics: Duality
  
  Chapter 6 (Duality) (CMU only) of the Matousek Gaertner book.
  
  Dantzig's article about simplex, duality, and the origins of LPs.


• Lecture 20 (Mar 27): Linear Programming: The Multiplicative Weights Method
  
  Notes on the multiplicative weights algorithm for the experts problem, and using it to solve LPs.
  Avrim's slides we used in lecture.
  A survey on the Multiplicative Weights method by Arora, Hazan and Kale.


• Lecture 21 (April 1): Linear Programming: Ellipsoid and Interior-Point Methods
  
  Chapter 7 (Beyond Simplex) (CMU only) of the Matousek Gaertner book.
  
  slides from lecture. (We did not follow the treatment of interior point methods from it, only ellipsoid.)
  John Hooker's notes on interior point. (CMU only)
  We roughly followed this; for the explanation behind the system (46), see Matousek Gaertner.


• Lecture 22 (April 3): Integer Programming
  
  slides from lecture.
  Survey article by Bosch and Trick on integer programming.

String Searching

Readings (supplementary, but you must understand suffix trees)

• An introduction to 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)

Slides

• Lecture: suffix trees

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: Multiple Alignment and Genome Sequencing

Coding and Error Correction

Readings (supplementary)

• A book being written by Guruswami, Rudra, and Sudan, talks about many aspects of Coding Theory (from a CS viewpoint).
• A survey by Dan Speilman on the "Complexity of Error Correcting Codes".
• A crash course in coding theory, by Madhu Sudan.
• An Introduction to LDPC codes by Amin Shokrollahi.
• Some lecture notes from older versions of the course.

Slides

• Lecture 28: Basics: Hamming, Hadamard, etc.
• Lecture 29: An overview of topics in ECC: Reed-Solomon Codes, List Decoding, LDPC codes, etc.