15-853: Algorithms in the Real World (Spring 14)
Readings, Notes and 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 (only covered Burrows Wheeler in class)
- Lecture 4:
Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000
Lecture Notes and Pointers
- Lecture 6 (Jan 30):
Hashing basics, constructions, Bloom filters.
- Lecture 7 (Feb 4):
Hashing for load balancing: concentration bounds, two-choices, cuckoo
hashing.
- Lecture 8 (Feb 6):
Hashing for document similarity: min-hashing and locality-sensitive hashing
- Lecture 9 (Feb 11):
Hashing for streaming computation: Data streaming model, heavy hitters,
distinct elements
Lecture Notes
- Lecture 10 (Feb 13):
Dimension Reduction: Random Projections and the Johnson-Lindenstrauss
Flattening Lemma.
- Lecture 11 (Feb 18):
Dimension Reduction: SVDs, Principal Components Analysis (PCA), CUR
decomposition
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-2:
Introduction,
Sorting
List ranking,
B-trees,
Buffer trees
- Lecture 2.5:
Cache-oblivious algorithms, matrix multiplication, searching,
distribution sort
Readings
- Lecture 18 (Mar 20):
Linear Programming basics: Simplex
- Lecture 19 (Mar 25):
Linear Programming basics: Duality
- Lecture 20 (Mar 27):
Linear Programming: The Multiplicative Weights Method
- Lecture 21 (April 1):
Linear Programming: Ellipsoid and Interior-Point Methods
- Lecture 22 (April 3):
Integer Programming
Readings (supplementary, but you must understand suffix trees)
Slides
Readings
- Lectures on BioInformatics from the Max Planck Institute.
Slides
- Lecture 1: Introduction, Longest
Common Subsequence, Edit Distance
- Lecture 2: Sequence Alignment,
Local Alignment, Database Searching (BLAST / FASTA)
- Lecture 3: Multiple Alignment and
Genome Sequencing
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 28: Basics: Hamming,
Hadamard, etc.
- Lecture 29: An overview of topics
in ECC: Reed-Solomon Codes, List Decoding, LDPC codes, etc.
Guy Blelloch and Anupam Gupta,
guyb@cs.cmu.edu.