15-853: Algorithms in the Real World (Spring 12)
Readings, Notes and Slides
- Lectures on BioInformatics from the Max Planck Institute.
- 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
- Lecture 1-2:
- Lecture 2.5:
Cache-oblivious algorithms, matrix multiplication, searching,
- 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.
- Lecture 1, 2 and 3:
Nearest Neighbor Search,
Bounded Volume Hierarchies
In class we did not get to Bounded Volume Hierarchies.
These are some other potentially useful readings
- 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
- Lectures 1 and 2:
Introduction, Information Theory,
- 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