Readings, Notes and Slides

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

Nearest Neighbors

Readings

Slides

• Nearest Neighbors Lecture 1
  Callahan Kosaraju "Well Separated Pair Decompositions".

Linear and Integer Programming

Readings

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

Readings

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

Slides

• Lecture 1
• Lecture 2
• Lecture 3

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.

Error Correcting Codes

• Constructing Error-Correcting Codes from Expander Graphs, Dan Spielman
• The complexity of error-correcting codes, Dan Spielman

• Lecture 1
  Intro, Hamming and linear codes
• Lecture 2: number theory review (groups, fields, galois fields), and Reed Solomon codes.
• Lecture 3
  Expander graphs, Low Densisty Parity Check (LDPC) codes, Tornado codes.

String Searching

Slides

• Lecture: suffix trees

Readings (supplementary, but you must understand suffix trees)

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

Compression

Readings

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

• The Large Text Compression Benchmark by Matt Mahoney.
  This is for browsing.

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
• Lecture 4: Lossy Compression: Quantization, Transforms, JPEG, MPEG, Wavelets, MPEG 2000
  

Introduction

Slides

• Introduction