Readings, Notes and Slides

• Compression
• Coding and Error Correction
• Cryptography
• Hashing
• Dimension Reduction
• Parallel Algorithms
• Locality: Memory-Efficient Algorithms
• Linear and Integer Programming

Will be updated as we go along

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
  

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 5: Basics: Hamming, Hadamard, etc.
• Lecture 6: Reed-Solomon Codes
• Lecture 7: Expander (LDPC) codes, Tornado codes
• Lecture 8: R-S decoding, Number Theory

Cryptography

Readings

• "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice". A timely article (presented on October 14th) on the weknesses of Diffie-Hellman in practice. This has more to do with the way it is used, than a fundamental flaw in Diffie-Hellman.
• 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). 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 (mostly covered in one lecture since number theory was covered in the previous lecture)
  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
  In class also covered homomorphic encryption from Gentry's CACM paper

Hashing

Lecture Notes and Pointers

• Lecture 13: Hashing basics, constructions, Bloom filters, Load-balancing (basic, two-choice), Cuckoo hashing.
  
  A tutorial by Mikkel Thorup on basic hashing schemes (from this hashing summer school).
  A survey on Network applications of Bloom filters by Broder and Mitzenmacher
  Bloom filters and two-choice hashing feature on Jennifer Rexford's top 10 "practical theory" papers list at SIGCOMM.
  A blog post on choosing good hash functions in practice.
  
  
• Lecture 14: 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.
  
  
• Lecture 15: 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.
  
  

Dimension Reduction and Near-Neighbor Searching

Lecture Notes

• Lecture 16: Dimension Reduction: Random Projections and the Johnson-Lindenstrauss Flattening Lemma.
  
  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.
  Draft of the Foundations of Data Science textbook (in development) by Hopcroft and Kannan; Chapter 2 talks about high-dimensional phenomena.
  
  
• Lecture 17: 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.
  The Hopcroft Kannan chapter on SVDs.
  Notes on SVDs from our Advanced Algorithms class.

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 (ppt): Introduction, Sorting List ranking, B-trees, Buffer trees
• Lecture 2 (ppt): Cache-oblivious algorithms, matrix multiplication, searching, distribution sort

Linear and Integer Programming

Readings

• Lecture 24: Linear Programming basics: Simplex (slides, animation (CMU only))
  
  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.


• Lecture 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 26: Linear Programming: Multiplicative Weights and Interior Point
  Multiplicative Weights:
  Notes on the multiplicative weights algorithm for the experts problem, and using it to solve LPs.
  Avrim Blum's slides are a great read.
  A survey on the Multiplicative Weights method by Arora, Hazan and Kale.
  Interior Point:
  Chapter 7 (Beyond Simplex) (CMU only) of the Matousek Gaertner book.
  
  John Hooker's notes on interior point. (CMU only)
  We roughly followed this; for the explanation behind the system (46), see Matousek Gaertner.



---



• Lecture 27: Integer Programming
  
  slides from lecture.
  Survey article by Bosch and Trick on integer programming.