15-499: Algorithms and Applications (Guy Blelloch, Spring 03)
Readings, Notes and Slides
Note that we might not have slides from all the lectures.
old indicates slides from a previous year.
These will be updated for this year.
Introduction
Vehicle routing, an example of algorithms
used in the "real world".
Slides
Compression
Web page
Readings
-
Introduction to Data Compression (54 pages, ps.gz or pdf).
Slides
- Compression 1 and 2
(ps 4up,
pdf 4up)
Introduction, Information theory, Huffman coding, arithmetic coding,
run-length-coding (fax coding), move-to-front, residual-coding (JPEG LS), PPM
- Compression 3
(ps 4up,
pdf 4up)
Lempel-Ziv (LZ77, LZSS, gzip, LZ78, LZW, gif) and Burrows-Wheeler
- Compression 4
(ps 4up,
pdf 4up)
Lossy compression (quantization, wavelets, JPEG, MPEG, JPEG2000)
- Compression 5
(ps 4up,
pdf 4up)
Compressing graphs
Cryptography
Web page
Readings
Slides
- Cryptography 1
(ps 4up,
pdf 4up)
Introduction, one-way functions, basic protocols
- Cryptography 2
(ps 4up,
pdf 4up)
Number theory: groups, fields, Galois fields
- Cryptography 3 and 4
(ps 4up,
pdf 4up)
Private key cryptosystems (Block Ciphers, Rijdael)
Public key cryptosystems (SSL, RSA, ElGamal, Diffie-Hellman key exchange)
Quantum cryptography
- Cryptography 5
(ps 4up,
pdf 4up)
Kerberos and Digital Cash.
Computational Biology and Sequence Matching
Web page
Slides
- Computational Biology 1
(ps 4up,
pdf 4up)
Introduction, Longest Common Subsequence (LCS), Minimum Edit Distace (MED),
space efficient solutions, Myers/Ukkonen algorithm.
- Computational Biology 2
(ps 4up,
pdf 4up)
Sequence alignment, gap models, local alignment, FASTA, BLAST.
- Computational Biology 3
(ps 4up,
pdf 4up)
Multiple alignment.
- Computational Biology 4
(ps 4up,
pdf 4up)
Sequencing the Human Genome.
- Computational Biology 5
(ps 4up,
pdf 4up)
Sequencing the Human Genome (continued).
- Computational Biology 6
(ps 4up,
pdf 4up)
Suffix Trees.
Indexing and Searching
Web page
Readings
Slides
- Indexing and Searching 1
(ps 4up,
pdf 4up)
Introduction, Inverted Indices
- Indexing and Searching 2
(ps 4up,
pdf 4up)
Vector models
- Indexing and Searching 3 (only available in hardcopy, outside Wean 7116)
Latent semantic indexing
- Indexing and Searching 4
(ps 4up,
pdf 4up)
Link analysis and near duplicate removal
Error Correcting Codes
Web page
Slides
- Error Correcting Codes 1
(ps 4up,
pdf 4up)
Introduction, Hamming Codes, Linear Codes.
- Error Correcting Codes 2
(ps 4up,
pdf 4up)
Reed Solomon Codes, Cyclic Codes.
Back to the Algorithms and Applications page (Spring 2003).
Guy Blelloch,
guyb@cs.cmu.edu.