Readings, Notes and Slides

• Introduction
• Compression
• Suffix Trees
• Cryptography
• Error Correcting Codes
• Linear and Integer Programming
• Computational Biology
• Graph Separators

Graph Separators

Slides

• Graph Separators (Lecture 1)

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.

Computational Biology

Slides

• Lecture 1
• Lecture 2

Readings

• Protein Synthesis Animations (in particular, transcription and translation)

• Lectures on BioInformatics from the Max Planck Institute.
  • General Gap Models
  • Alignment Applet for the dynamic program (using, e.g., the BLOSUM62 score matrix).

Linear and Integer Programming

Slides

• Linear/Integer Programming 1
  Introduction: formulations, integer vs linear programming, max-flow as a linear program
  Simplex method: geometric view
  Duality: Dual formulation and duality theorem
• Linear/Integer Programming 2
  Ellipsoid Method
  Interior Point Methods
  
• Linear/Integer Programming 3
  Introduction to integer programming
  Branch and bound solutions
  
• Linear/Integer Programming 4
  A case study of crew scheduling
  

Error Correcting Codes

• Constructing Error-Correcting Codes from Expander Graphs, Dan Spielman
• The complexity of error-correcting codes, Dan Spielman
• Scribe notes on Tornado Codes (Cha Zhang, 2002)

• 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.

Cryptography

Readings

• Cryptography A-Z : an online resource courtesy of SSH.
• Introduction to Cryptography (30 pages). This is still in rough shape, and here are some bug fixes.
• AES Proposal: Rijndael.

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.

Suffix Trees

Slides

• Lectures 1: suffix trees (Power Point with animations)

Readings

• A gentle introduction to Suffix Trees
• More details on Suffix Tree construction (including applet and code)
• Chapter on suffix trees (Gusfield's book)
• Applications of Suffix Trees (Notes from MIT)
• Building Suffix Trees and Arrays: A Solution to HW1 (Notes from MIT)

Compression

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

• Introduction to Data Compression. This is a required reading.

Other

• The The Archive Comparison Test. A comparison of many lossless compression algorithms over a variety of corpora.

Introduction

Slides

• Introduction

Related Readings

• RouteSmart: The Drive for Perfection: City of San Diego uses RouteSmart to Streamline Curbside Collections.
• GeoRoute: Map-based routing for postal operations