Readings, Notes and Slides

• Compression
• Coding and Error Correction
• Cryptography
• Parallel Algorithms
• Locality and I/O Efficient Algorithms
• Nearest Neighbors and Spatial Decompositions
• Dimension Reduction
• Clustering

Will be updated as we go along

Introduction

• Course Introduction:

Write-efficient Algorithms

Slides

• Lecture 1 (pdf)
• Lecture 1 (ppsm)

Parallel Search Trees and Range Queries

Readings

Slides

• Lecture 1

Clustering

Readings

Slides

• Lecture 1 and 2

Nearest Neighbors and Spatial Decompositions (Low Dimensions)

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
  

Dimension Reduction and Near-Neighbor Searching (High Dimensions)

Lecture Notes

• Dimension Reduction: Random Projections and the Johnson-Lindenstrauss Flattening Lemma.
  
  Lecture Notes by Anupam Gupta from previous instance of class.
  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.
  
  
• 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.

Locality and I/O Efficient Algorithms

Slides

• Lecture 1. Cache-aware algorithms, searching, sorting, list-ranking, buffer-tree.
• Lecture 2. Cache-oblivious algorithms, matrix transpose, matrix multiplication, searching, sorting.

Readings

Parallel Algorithms

Readings

Slides

• Lecture 1. Introduction, parallelism, nested parallelism, modeling costs with work and span, some examples.
• Lecture 2. Parallel techniques: using collections, divide-and-conquer.
• Lecture 3. Parallel graph connectivity: BFS, random-mate, low-diameter decomposition and work-efficient connectivity.

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:
  Introduction: terminology, definitions of security, one-way-functions, protocols
  Private-key systems: block-ciphers, Rijndael
  
• Lectures 3 and 4:
  Public-key and Key-exchange systems: Diffie-Hellman, ElGamal, RSA, TLS
  Kerberos
  

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 1: Basics: Hamming, Hadamard, etc.
• Lecture 2: Reed-Solomon Codes
• Lecture 3: Expander (LDPC) codes, Tornado codes

Compression

Readings

• Introduction to Data Compression.
  This is a required reading.

• Introduction to Information Theory.
  This is an optional reading. The book can be found here.
  

• 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
• Lecture 4: Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000
  
• Lecture 5: Graph compression:
  Graph representations, reference coding, difference coding, k-bit codes
  Graph reordering, shingle-order, recursive bisection