Readings, Notes and Slides

Learning, Online Prediction and Games

• A Survey of k-experts based prediction algorithms (guest lecture by Avrim Blum)

Streaming

• A Survey of Streaming Algorithms (guest lecture by Phil Gibbons).

Compression

• Introduction to Data Compression (54 pages).

• Lectures 1 and 2
• Lecture 3

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)

• Intro, Hamming and Linear Codes (Lecture 1)
• Reed-Solomon Codes (Lecture 2)
• Graph-based Codes (Lecture 3)
(Note part of the lecture was given on the board...the part on LDPC codes)

Dimension Reduction

• An introduction to SVD and PCA.
• A paper on applications of PCA to gene expression data.
  The papers above cover the basics of PCA and SVDs.
• Improved Approximation Algorithms for Large Matrices via Random Projections by Tamas Sarlos.
  See this paper (and refs) on how to approximately do SVDs faster.

• Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas
Each of these proofs is a bit different.
• Using J-L for learning applications: robust concept learning and mixtures of Gaussians.
  There are many other application papers: these are the pioneering ones.

• Data Clustering: A survey by Jain, Murty and Flynn, Computing Surveys, 1999

Graph Separators

• 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.
• Spectral Partitioning Works: Planar graphs and finite element meshes, Daniel Spielman and Shang-Hua Teng.
  Section 2 gives a good short overview of spectral partitioning

• Notes on Lipton-Tarjan planar separators from Spring 2002.
  Detailed proofs of all the issues touched upon in class. (Also see the slides below.)
• Notes on planar graphs and separators
  These are from Dexter Kozen's excellent graduate text on algorithms.
  Note that he converts an arbitrary planar graph into a shallow one somewhat differently.

• P. Ungar. A theorem on planar graphs. Journal London Math Society, 26:256--262, 1951.
• R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Applied Mathematics, 36:177-- 189, 1979.

Slides

• Graph Separators (Lectures 1 and 2)
• Nested Dissection (Lecture 3)
  
  Just read the intro portion
• A Proof of the Planar Separator Theorem (Lecture 4)

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
  

Computational Biology

Slides

• Lecture "0" was on Suffix Trees and was done on the board. You should see the readings below for more information.
• Lecture 1 (and part of lecture 2)
• Lecture 1 (lecture 2)

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)

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

Introduction

Slides

• Introduction