15-853: Algorithms in the Real World (Spring 18)
Readings, Notes and Slides
Will be updated as we go along
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 5:
Graph compression:
Graph representations, reference coding, difference coding, k-bit codes
Graph reordering, shingle-order, recursive bisection
Guy Blelloch
guyb@cs.cmu.edu.