15-853: Algorithms in the Real World (Spring 12)
Readings, Notes and 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: Gene detection with
hidden markov models (HMMs), scoring, and decoding
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
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 and 3:
Introduction,
Quad/Oct/Kd/BSP trees,
Nearest Neighbor Search,
Metric spaces,
Ball/Cover trees,
Callahan-Kosaraju,
Bounded Volume Hierarchies
In class we did not get to Bounded Volume Hierarchies.
Readings
These are some other potentially useful readings
Slides
Readings
Slides
- Lectures 1 and 2
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
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
Slides
Guy Blelloch,
guyb@cs.cmu.edu.