Readings, Notes and Slides

• Introduction
• Cryptography
• Error Correcting Codes
• Computational Biology
• String Searching
• Linear and Integer Programming
• Dimension Reduction and Nearest Neighbors
• Satisfiability Solvers

Boolean Satisfiability Solvers

Main Reading

• An Introductory Chapter on SAT Solvers by Gomes et al.

Supplementary Readings

• Survey on state of the art SAT solvers by Kautz and Selman.
• A PhD thesis by Niklas Sorensson that has a good introduction to SAT solvers. See Chapter 1 and possibly parts of 2.
• Lecture notes on proof systems.
• Some satisfiability resources on the web: SAT Live!, SAT Competition, and the SAT software library.

Slides

• Boolean Satisfiability 1 & 2
  

Dimension Reduction and Nearest Neighbors

• 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

Notes

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
  

String Searching

Slides

• Lecture 1: suffix trees
• Lecture 2: suffix trees for compression

Readings

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

Computational Biology

Slides

• Lecture 1
• Lecture 2
• Lecture 3

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

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 3
  Expander graphs, Low Densisty Parity Check (LDPC) codes, Tornado codes.

Cryptography

Readings

• Cryptography A-Z : an online resource courtesy of SSH. (Seems to no longer exist)
• Introduction to Cryptography (30 pages). This is still in rough shape, and here are some bug fixes.
• AES Proposal: Rijndael.
• Useful links on cryptography
• Mathematical Background reading (Groups, Fields, etc). Completely optional.
  • Mathematical background to an upcoming complexity textbook by Arora and Barak. See sections A.3 - A.4. Very concise.
  • Online cryptography textbook by Goldwasser and Bellare. Appendix C (page 255) contains useful mathematical background.
  • Abstract Algebra, 2nd Edition by Dummit & Foote. Classic textbook. Very comprehensive.

Slides

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

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