15-853: Algorithms in the Real World (Fall 15)
Readings, Notes and Slides
Will be updated as we go along
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 (only covered Burrows Wheeler in class)
- Lecture 4:
Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000
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 (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
Lecture Notes and Pointers
- Lecture 13:
Hashing basics, constructions, Bloom filters, Load-balancing (basic, two-choice), Cuckoo hashing.
- Lecture 14:
Hashing for streaming computation: Data streaming model, heavy hitters,
distinct elements
- Lecture 15:
Hashing for document similarity: min-hashing and locality-sensitive hashing
Lecture Notes
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.
Readings
Slides
- Lecture 1
(ppt):
Introduction,
Sorting
List ranking,
B-trees,
Buffer trees
- Lecture 2
(ppt):
Cache-oblivious algorithms, matrix multiplication, searching,
distribution sort
Readings
Guy Blelloch and Anupam Gupta,
guyb@cs.cmu.edu.