Readings, Notes and Slides

Indexing and Searching

Readings

Slides

• Indexing and Searching I (pdf 4up,ppt)
  Introduction. Inverted File Indexes. Compression, Lexicon Access, Union/Intersection.
• Indexing and Searching II & III (pdf 4up,ppt)
  Link Analysis

Computational Biology and Sequence Matching

Web page

Slides

• Computational Biology I (pdf 4up)
  Knuth-Morris-Pratt. Suffix Trees.
• Computational Biology II (pdf 4up)
  Introduction to strings in biology, Longest Common Subsequence (LCS), Minimum Edit Distace (MED), space efficient solutions, Myers/Ukkonen algorithm.
• Computational Biology III (pdf 4up,ppt)
  Sequence alignment, gap models, local alignment, FASTA, BLAST.
• Computational Biology IV (pdf 4up,ppt)
  Genome Sequencing. Multiple alignment.
• Computational Biology V (pdf 4up,ppt)
  Genome Sequencing.

Separators

Readings

Slides

• Graph Separators 1 and 2 ( pdf )

Cryptography

Web page

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

• Cryptography 1 and 2 ( pdf )
  Introduction: one-way functions, basic protocols
  Number theory: groups, fields, Galois fields
  Private key cryptosystems: Block Ciphers, Rijdael
• Cryptography 3 and 4 ( pdf )
  Public key cryptosystems: Diffie-Hellman, Merkle-Hellman, RSA, ElGamal
  Applications: Kerberos, electronic cash

Compression

Readings

• Introduction to Data Compression (54 pages, ps.gz or pdf).
• Simple Linear Work Suffix Array Construction.
  Juha Karkkainen and Peter Sanders. (pdf).
  This can be used to do the BW sort in linear time.

Slides

• Lectures 1 and 2 (pdf)
• Lecture 2.5 (pdf)
• Lecture 3 (pdf)
• Lecture 4.5 and 5 (lecture 4.0 had no slides, it was on sorting by suffixes) (pdf)

Introduction

Slides

• Introduction (ps, pdf )