15-853: Algorithms in the Real World (Guy Blelloch, Fall 07)
Readings, Notes and Slides
Slides
Readings
- Jim Demmel's notes on graph partitioning (Part 1
Part 2)
- Publications about MeTIS from George Karypis' lab at the University of Minnesota.
The Karypis Kumar paper is the standard reference.
Slides
Readings
- Lectures on BioInformatics from the Max Planck Institute.
Readings:
These are some other potentially usefull readings
Slides
Readings:
Some other potentially usefull readings
Lecture slides:
- Lecture 1
Intro, Hamming and linear codes
- Lecture 2
Reed-Solomon and cyclic codes.
- Lecture 2
Expander graphs, Low Densisty Parity Check (LDPC) codes, Tornado codes.
Readings
Slides (Funky symbols fixed)
- 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
- Lectures 3 and 4.
Slides
Readings
Slides
- Lectures 1 and 2:
Introduction, Information Theory,
Huffman/Arithmetic/Gamma Codes.
- Lecture 2.5:
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: Lempell-Ziv and Burrows-Wheeler
- Lectures 4 and 5:
Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000
Compressing structured data: graph compression
Readings
Other
Slides
Related Readings
In the intro slides I mentioned how algorithms are used to plan trash pickup routes and mail delivery. Here are the two article I briefly displayed:
- RouteSmart:
The Drive for Perfection: City of San Diego uses RouteSmart to Streamline Curbside Collections.
- GeoRoute: Map-based routing for postal operations
Guy Blelloch,
guyb@cs.cmu.edu.