15-853: Algorithms in the Real World (Guy Blelloch, Fall 07)
Readings, Notes and Slides
- Jim Demmel's notes on graph partitioning (Part 1
- Publications about MeTIS from George Karypis' lab at the University of Minnesota.
The Karypis Kumar paper is the standard reference.
- Lectures on BioInformatics from the Max Planck Institute.
These are some other potentially usefull readings
Some other potentially usefull readings
- 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.
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.
- Lectures 1 and 2:
Introduction, Information Theory,
- 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
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:
The Drive for Perfection: City of San Diego uses RouteSmart to Streamline Curbside Collections.
- GeoRoute: Map-based routing for postal operations