15-853: Algorithms in the Real World (Spring 18)
Readings, Notes and Slides
Will be updated as we go along
Slides
Readings
Slides
Readings
Slides
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
Lecture Notes
Slides
- Lecture 1. Cache-aware algorithms,
searching, sorting, list-ranking, buffer-tree.
- Lecture 2.
Cache-oblivious algorithms, matrix transpose, matrix multiplication, searching, sorting.
Readings
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.
Readings
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
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
Readings
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
Guy Blelloch
guyb@cs.cmu.edu.