\contentsline {part}{List of Algorithms}{12}
\contentsline {part}{Compression 1 (Ben Zhao)}{14}
\contentsline {section}{\numberline {1}Introduction to Compression}{14}
\contentsline {subsection}{\numberline {1.1}Information Theory}{14}
\contentsline {subsection}{\numberline {1.2}The English Language}{15}
\contentsline {section}{\numberline {2}Basic Compression Algorithms}{17}
\contentsline {subsection}{\numberline {2.1}Prefix Codes}{17}
\contentsline {subsection}{\numberline {2.2}Huffman Codes}{17}
\contentsline {subsection}{\numberline {2.3}Shannon-Fano Coding}{18}
\contentsline {subsection}{\numberline {2.4}Arithmetic Coding}{18}
\contentsline {subsection}{\numberline {2.5}Deriving Probabilities}{19}
\contentsline {section}{\numberline {3}Lempel-Ziv Overview}{19}
\contentsline {subsection}{\numberline {3.1}LZ78 and LZW}{20}
\contentsline {subsection}{\numberline {3.2}LZ77 (Sliding Windows)}{22}
\contentsline {part}{Compression 2 (Gabriel Moy)}{23}
\contentsline {section}{\numberline {1}Lossless Compression: review and expansion}{23}
\contentsline {subsection}{\numberline {1.1}Can we compress all strings?}{23}
\contentsline {subsection}{\numberline {1.2}Huffman Codes Revisited}{23}
\contentsline {subsection}{\numberline {1.3}Arithmetic Coding Revisited}{25}
\contentsline {subsection}{\numberline {1.4}Conditional Entropy and Markov Chains}{27}
\contentsline {subsection}{\numberline {1.5}The JBIG Standard}{28}
\contentsline {subsection}{\numberline {1.6}Tries and use in LZW}{28}
\contentsline {subsection}{\numberline {1.7}Other Lossless Compression Techniques}{28}
\contentsline {section}{\numberline {2}Lossy Compression}{29}
\contentsline {subsection}{\numberline {2.1}Scalar Quantization}{29}
\contentsline {subsection}{\numberline {2.2}Vector Quantization}{30}
\contentsline {subsection}{\numberline {2.3}Transform Coding}{30}
\contentsline {subsection}{\numberline {2.4}Choosing a Transform}{31}
\contentsline {part}{Compression 3 (Ben Liblit)}{33}
\contentsline {section}{\numberline {1}Case Studies}{33}
\contentsline {subsection}{\numberline {1.1}JPEG}{33}
\contentsline {subsubsection}{\numberline {1.1.1}JPEG Introduction}{33}
\contentsline {subsubsection}{\numberline {1.1.2}JPEG Compression Steps}{34}
\contentsline {subsection}{\numberline {1.2}MPEG}{37}
\contentsline {subsubsection}{\numberline {1.2.1}MPEG Introduction}{37}
\contentsline {subsubsection}{\numberline {1.2.2}MPEG Encoding: I-Frames}{39}
\contentsline {subsubsection}{\numberline {1.2.3}MPEG Encoding: P-Frames}{39}
\contentsline {subsubsection}{\numberline {1.2.4}MPEG Encoding: B-Frames}{41}
\contentsline {subsubsection}{\numberline {1.2.5}MPEG Compression Effectiveness}{43}
\contentsline {subsubsection}{\numberline {1.2.6}MPEG in the Real World}{43}
\contentsline {section}{\numberline {2}Other Lossy Transform Codes}{44}
\contentsline {subsection}{\numberline {2.1}Wavelet Compression}{44}
\contentsline {subsubsection}{\numberline {2.1.1}Wavelet Introduction}{44}
\contentsline {subsubsection}{\numberline {2.1.2}Haar Wavelets}{44}
\contentsline {subsubsection}{\numberline {2.1.3}Wavelets in the Real World}{46}
\contentsline {subsection}{\numberline {2.2}Fractal Compression}{47}
\contentsline {subsubsection}{\numberline {2.2.1}Function Fixed Points}{47}
\contentsline {subsubsection}{\numberline {2.2.2}Fractal Compression and Fixed Points}{48}
\contentsline {subsubsection}{\numberline {2.2.3}Fractal Compression in the Real World}{49}
\contentsline {subsection}{\numberline {2.3}Model-Based Compression}{50}
\contentsline {part}{Cryptography 1 (Tzu-Yi Chen)}{51}
\contentsline {section}{\numberline {1}Definitions and Primitives}{51}
\contentsline {subsection}{\numberline {1.1}Definitions}{51}
\contentsline {subsection}{\numberline {1.2}Primitives}{53}
\contentsline {paragraph}{One-way Functions}{53}
\contentsline {paragraph}{One-way Trapdoor Functions}{53}
\contentsline {paragraph}{One-way Hashing Functions}{53}
\contentsline {section}{\numberline {2}Protocols}{53}
\contentsline {subsection}{\numberline {2.1}Digital Signatures}{54}
\contentsline {subsection}{\numberline {2.2}Key Exchange}{55}
\contentsline {subsection}{\numberline {2.3}Authentication}{55}
\contentsline {subsection}{\numberline {2.4}Some Other Protocols}{56}
\contentsline {section}{\numberline {3}Symmetric (private-key) Algorithms}{56}
\contentsline {subsection}{\numberline {3.1}Symmetric Ciphers (Block Ciphers)}{56}
\contentsline {subsection}{\numberline {3.2}DES (Data Encryption Standard)}{57}
\contentsline {part}{Cryptography 2 (David Oppenheimer)}{59}
\contentsline {section}{\numberline {1}Block ciphers}{59}
\contentsline {subsection}{\numberline {1.1}Feistel networks}{59}
\contentsline {subsection}{\numberline {1.2}Security and Block Cipher Design Goals}{61}
\contentsline {subsection}{\numberline {1.3}DES Security}{61}
\contentsline {subsubsection}{\numberline {1.3.1}E-box and P-box}{61}
\contentsline {subsubsection}{\numberline {1.3.2}S-box}{61}
\contentsline {subsubsection}{\numberline {1.3.3}Weaknesses of DES}{62}
\contentsline {subsubsection}{\numberline {1.3.4}DES in the Real World}{63}
\contentsline {subsection}{\numberline {1.4}Differential Cryptanalysis}{64}
\contentsline {subsection}{\numberline {1.5}Linear Cryptanalysis}{64}
\contentsline {subsection}{\numberline {1.6}IDEA}{65}
\contentsline {subsection}{\numberline {1.7}Block Cipher Encryption Speeds}{67}
\contentsline {section}{\numberline {2}Stream ciphers}{67}
\contentsline {subsection}{\numberline {2.1}Stream ciphers vs. Block cipher}{67}
\contentsline {subsection}{\numberline {2.2}RC4}{68}
\contentsline {section}{\numberline {3}Public-Key Algorithms}{69}
\contentsline {subsection}{\numberline {3.1}Merkle-Hellman Knapsack Algorithm}{69}
\contentsline {subsection}{\numberline {3.2}RSA}{70}
\contentsline {part}{Cryptography 3 (Marat Boshernitsan)}{72}
\contentsline {section}{\numberline {1}Some group theory}{72}
\contentsline {subsection}{\numberline {1.1}Groups: Basics}{72}
\contentsline {subsection}{\numberline {1.2}Integers modulo n}{72}
\contentsline {subsection}{\numberline {1.3}Generators (primitive elements)}{73}
\contentsline {subsection}{\numberline {1.4}Discrete logarithms}{74}
\contentsline {section}{\numberline {2}Public Key Algorithms (continued)}{74}
\contentsline {subsection}{\numberline {2.1}RSA algorithm (continued)}{74}
\contentsline {subsection}{\numberline {2.2}Factoring}{75}
\contentsline {subsection}{\numberline {2.3}ElGamal Algorithm}{75}
\contentsline {section}{\numberline {3}Probabilistic Encryption}{75}
\contentsline {subsection}{\numberline {3.1}Generation Random Bits}{76}
\contentsline {subsection}{\numberline {3.2}Blum-Goldwasser}{76}
\contentsline {section}{\numberline {4}Quantum Cryptography}{77}
\contentsline {section}{\numberline {5}Kerberos (A case study)}{77}
\contentsline {subsection}{\numberline {5.1}How Kerberos Works}{78}
\contentsline {subsection}{\numberline {5.2}Tickets and Authenticators}{79}
\contentsline {subsection}{\numberline {5.3}Kerberos messages}{79}
\contentsline {part}{Linear Programming 1 (Richard C. Davis)}{80}
\contentsline {section}{\numberline {1}Introduction}{80}
\contentsline {subsection}{\numberline {1.1}Some Optimization Problems}{80}
\contentsline {subsection}{\numberline {1.2}Applications of Linear Programming}{81}
\contentsline {subsection}{\numberline {1.3}Overview of Algorithms}{82}
\contentsline {subsection}{\numberline {1.4}Linear Programming Formulation}{83}
\contentsline {subsection}{\numberline {1.5}Using Linear Programming for Maximum-Flow}{84}
\contentsline {section}{\numberline {2}Geometric Interpretation}{85}
\contentsline {section}{\numberline {3}Simplex Method}{86}
\contentsline {subsection}{\numberline {3.1}Tableau Method}{88}
\contentsline {subsection}{\numberline {3.2}Finding an Initial Corner Point}{92}
\contentsline {subsection}{\numberline {3.3}Another View of the Tableau}{93}
\contentsline {subsection}{\numberline {3.4}Improvements to Simplex}{93}
\contentsline {part}{Linear Programming 2 (Steven Czerwinski)}{95}
\contentsline {section}{\numberline {1}Duality}{95}
\contentsline {subsection}{\numberline {1.1}Duality: General Case}{95}
\contentsline {subsection}{\numberline {1.2}Example}{96}
\contentsline {subsection}{\numberline {1.3}Duality Theorem}{97}
\contentsline {section}{\numberline {2}Ellipsoid Algorithm}{97}
\contentsline {subsection}{\numberline {2.1}Description of algorithm}{98}
\contentsline {subsection}{\numberline {2.2}Reduction from general case}{99}
\contentsline {section}{\numberline {3}Interior Point Methods}{99}
\contentsline {subsection}{\numberline {3.1}Centering}{100}
\contentsline {subsubsection}{\numberline {3.1.1}Analytical center}{101}
\contentsline {subsubsection}{\numberline {3.1.2}Elliptical Scaling}{101}
\contentsline {subsection}{\numberline {3.2}Optimizing techniques}{102}
\contentsline {subsubsection}{\numberline {3.2.1}Projection}{102}
\contentsline {subsubsection}{\numberline {3.2.2}Newton's Method}{103}
\contentsline {subsection}{\numberline {3.3}Affine scaling method}{104}
\contentsline {subsubsection}{\numberline {3.3.1}Computation at each iteration}{104}
\contentsline {subsubsection}{\numberline {3.3.2}Overall computation}{105}
\contentsline {subsection}{\numberline {3.4}Potential reduction}{106}
\contentsline {subsection}{\numberline {3.5}Central trajectory}{107}
\contentsline {section}{\numberline {4}Algorithm summary}{107}
\contentsline {section}{\numberline {5}General Observation}{108}
\contentsline {part}{Integer Programming 1 (Andrew Begel)}{109}
\contentsline {section}{\numberline {1}Introduction and History}{109}
\contentsline {section}{\numberline {2}Applications}{110}
\contentsline {subsection}{\numberline {2.1}Knapsack Problem}{110}
\contentsline {subsection}{\numberline {2.2}Traveling Salesman Problem}{110}
\contentsline {subsection}{\numberline {2.3}Other Constraints Expressible with Integer Programming}{111}
\contentsline {subsection}{\numberline {2.4}Piecewise Linear Functions}{111}
\contentsline {section}{\numberline {3}Algorithms}{112}
\contentsline {subsection}{\numberline {3.1}Linear Programming Approximations}{112}
\contentsline {subsection}{\numberline {3.2}Search Techniques}{112}
\contentsline {subsubsection}{\numberline {3.2.1}Branch and Bound}{112}
\contentsline {subsection}{\numberline {3.3}Implicit Enumeration (0-1 Programs)}{114}
\contentsline {part}{Integer Programming 2 (Stephen Chenney)}{116}
\contentsline {section}{\numberline {1}Algorithms (continued)}{116}
\contentsline {subsection}{\numberline {1.1}Problem Specific Aspects}{116}
\contentsline {subsection}{\numberline {1.2}Cutting Plane Algorithm}{117}
\contentsline {subsection}{\numberline {1.3}Recent Developments}{118}
\contentsline {section}{\numberline {2}Airline Crew Scheduling (A Case Study)}{118}
\contentsline {subsection}{\numberline {2.1}The Problem}{118}
\contentsline {subsection}{\numberline {2.2}Set Covering and Partitioning}{119}
\contentsline {subsection}{\numberline {2.3}Generating Crew Pairings}{120}
\contentsline {subsection}{\numberline {2.4}TRIP}{122}
\contentsline {subsection}{\numberline {2.5}New System}{123}
\contentsline {subsubsection}{\numberline {2.5.1}Generating a Pool of Pairings}{123}
\contentsline {subsubsection}{\numberline {2.5.2}Solving the LP Approximation}{124}
\contentsline {subsubsection}{\numberline {2.5.3}Using the LP for the IP}{124}
\contentsline {subsubsection}{\numberline {2.5.4}Additional Constraints}{126}
\contentsline {subsubsection}{\numberline {2.5.5}Conclusions}{126}
\contentsline {part}{Triangulation 1 (Aaron Brown)}{128}
\contentsline {section}{\numberline {1}Introduction to Triangulation}{129}
\contentsline {section}{\numberline {2}Basic Geometrical Operations}{129}
\contentsline {subsection}{\numberline {2.1}Degeneracies and Numerical Precision}{129}
\contentsline {subsection}{\numberline {2.2}The Line-side Test}{130}
\contentsline {subsection}{\numberline {2.3}The In-circle Test}{131}
\contentsline {section}{\numberline {3}Convex Hulls}{132}
\contentsline {subsection}{\numberline {3.1}Dual: Convex Polytopes}{132}
\contentsline {subsection}{\numberline {3.2}Algorithms for Finding Convex Hulls}{133}
\contentsline {subsubsection}{\numberline {3.2.1}Giftwrapping}{134}
\contentsline {subsubsection}{\numberline {3.2.2}Graham Scan}{134}
\contentsline {subsubsection}{\numberline {3.2.3}Mergehull}{136}
\contentsline {subsubsection}{\numberline {3.2.4}Quickhull}{137}
\contentsline {section}{\numberline {4}Delaunay Triangulations and Voronoi Diagrams}{139}
\contentsline {subsection}{\numberline {4.1}Voronoi Diagrams}{139}
\contentsline {subsection}{\numberline {4.2}Delaunay Triangulations}{139}
\contentsline {subsection}{\numberline {4.3}Properties of Delaunay Triangulations}{141}
\contentsline {subsection}{\numberline {4.4}Algorithms for Delaunay Triangulation}{141}
\contentsline {subsubsection}{\numberline {4.4.1}Naive Algorithm}{142}
\contentsline {subsubsection}{\numberline {4.4.2}Solution via Reduction to 3D Convex Hull}{142}
\contentsline {subsubsection}{\numberline {4.4.3}Direct Algorithms}{143}
\contentsline {part}{Triangulation 2 (Franklin Cho)}{144}
\contentsline {section}{\numberline {1}Divide-and-Conquer Delaunay Triangulation}{144}
\contentsline {section}{\numberline {2}Incremental Delaunay Triangulation Algorithm}{148}
\contentsline {section}{\numberline {3}Mesh Generation}{149}
\contentsline {subsection}{\numberline {3.1}Ruppert's Algorithm}{150}
\contentsline {part}{Triangulation 3 (Michael Downes)}{154}
\contentsline {section}{\numberline {1}Triangulation in Finite Element Methods (Mark Adams)}{154}
\contentsline {subsection}{\numberline {1.1}FEM Intro}{154}
\contentsline {subsection}{\numberline {1.2}Approximating the Weak Form with Subspaces}{155}
\contentsline {subsection}{\numberline {1.3}Picking Good Subspaces}{156}
\contentsline {subsection}{\numberline {1.4}Linear System Solvers}{156}
\contentsline {subsubsection}{\numberline {1.4.1}Direct Methods ({\pem {}e.g.}, Gauss Elimination)}{156}
\contentsline {subsubsection}{\numberline {1.4.2}Iterative Methods}{157}
\contentsline {subsection}{\numberline {1.5}Multigrid}{159}
\contentsline {subsection}{\numberline {1.6}Unstructured Multigrid Algorithms}{159}
\contentsline {subsection}{\numberline {1.7}Parallel Multigrid Solver for FE}{160}
\contentsline {section}{\numberline {2}Distance Metrics for Voronoi Diagrams and Delaunay Triangulations}{161}
\contentsline {section}{\numberline {3}Surface Modeling Using Triangulation}{162}
\contentsline {subsection}{\numberline {3.1}Terrain Modeling}{162}
\contentsline {subsubsection}{\numberline {3.1.1}Methods for Representing Terrains}{162}
\contentsline {subsubsection}{\numberline {3.1.2}Benefits of Triangulation}{162}
\contentsline {subsubsection}{\numberline {3.1.3}Algorithm}{163}
\contentsline {subsubsection}{\numberline {3.1.4}Finding $\mathop {\prm max}(e(x,y))$}{163}
\contentsline {subsubsection}{\numberline {3.1.5}Running Time}{163}
\contentsline {part}{N-Body Simulations 1 (Tajh Taylor)}{165}
\contentsline {section}{\numberline {1}Delaunay Triangulation - more applications}{165}
\contentsline {section}{\numberline {2}N-Body Introduction}{166}
\contentsline {subsection}{\numberline {2.1}Basic Assumptions}{166}
\contentsline {subsection}{\numberline {2.2}Applications}{167}
\contentsline {subsection}{\numberline {2.3}History of Algorithms}{168}
\contentsline {subsubsection}{\numberline {2.3.1}Particle-Particle (the naive method)}{168}
\contentsline {subsubsection}{\numberline {2.3.2}Mesh Based Methods}{168}
\contentsline {paragraph}{Particle Mesh (PM):}{168}
\contentsline {paragraph}{Particle-Particle Particle-Mesh (P3M):}{168}
\contentsline {paragraph}{Nested-Grid Particle-Mesh (NGPM):}{169}
\contentsline {subsubsection}{\numberline {2.3.3}Tree Based Methods}{169}
\contentsline {paragraph}{Top-down particle-cell:}{169}
\contentsline {paragraph}{Bottom-up particle-cell:}{169}
\contentsline {paragraph}{Cell-cell (Fast multipole method, FMM):}{170}
\contentsline {paragraph}{Tree-code particle-mesh:}{170}
\contentsline {section}{\numberline {3}Mesh-based Algorithms}{170}
\contentsline {section}{\numberline {4}Tree-based Algorithms}{172}
\contentsline {subsection}{\numberline {4.1}Barnes-Hut Algorithm}{172}
\contentsline {paragraph}{Exercise:}{176}
\contentsline {subsection}{\numberline {4.2}Fast Multipole Method}{176}
\contentsline {paragraph}{Particle-Cell Cost}{179}
\contentsline {paragraph}{Cell-Cell Cost}{180}
\contentsline {paragraph}{Definition:}{181}
\contentsline {paragraph}{Definition:}{181}
\contentsline {paragraph}{Definition:}{181}
\contentsline {part}{N-body Simulations 2 (Steve Gribble)}{183}
\contentsline {section}{\numberline {1}Fast Multipole Method (Review)}{183}
\contentsline {subsection}{\numberline {1.1}The Four Ideas}{183}
\contentsline {subsection}{\numberline {1.2}Interaction Lists}{184}
\contentsline {section}{\numberline {2}Callahan and Kosaraju's Algorithm}{185}
\contentsline {subsection}{\numberline {2.1}Well Separated Pair Decompositions}{185}
\contentsline {subsection}{\numberline {2.2}Definitions}{186}
\contentsline {subsection}{\numberline {2.3}Algorithm: Tree Decomposition}{187}
\contentsline {subsection}{\numberline {2.4}Algorithm: Well-Separated Realization}{189}
\contentsline {subsection}{\numberline {2.5}Bounding the size of the realization}{190}
\contentsline {section}{\numberline {3}N-body Summary}{194}
\contentsline {part}{VLSI Physical Design 1 (Rich Vuduc)}{195}
\contentsline {section}{\numberline {1}Some notes regarding the homework assignment}{195}
\contentsline {subsection}{\numberline {1.1}Representing a Delaunay triangulation}{195}
\contentsline {subsubsection}{\numberline {1.1.1}Neighbor graph}{196}
\contentsline {subsubsection}{\numberline {1.1.2}Quad edge}{196}
\contentsline {subsubsection}{\numberline {1.1.3}Triangles}{198}
\contentsline {subsection}{\numberline {1.2}Incremental Delaunay}{198}
\contentsline {subsection}{\numberline {1.3}Ruppert Meshing}{199}
\contentsline {subsection}{\numberline {1.4}Surface Approximation}{199}
\contentsline {section}{\numberline {2}Intro to VLSI Physical Design Automation}{201}
\contentsline {subsection}{\numberline {2.1}Overview}{202}
\contentsline {subsubsection}{\numberline {2.1.1}Physical design}{203}
\contentsline {subsubsection}{\numberline {2.1.2}Design styles}{203}
\contentsline {subsubsection}{\numberline {2.1.3}Transistor level}{205}
\contentsline {subsection}{\numberline {2.2}The role of algorithms}{207}
\contentsline {subsection}{\numberline {2.3}Evolution}{208}
\contentsline {section}{\numberline {3}Summary}{208}
\contentsline {part}{VLSI Physical Design 2 (Mehul Shah)}{210}
\contentsline {section}{\numberline {1}Introduction to VLSI Routing}{210}
\contentsline {section}{\numberline {2}Global Routing Algorithms}{211}
\contentsline {section}{\numberline {3}Two-Terminal Nets: Shortest Paths}{213}
\contentsline {subsection}{\numberline {3.1}Dijkstra's Algorithm}{213}
\contentsline {paragraph}{Exercise:}{215}
\contentsline {subsection}{\numberline {3.2}Maze Routing}{215}
\contentsline {section}{\numberline {4}Multi-Terminal Nets: Steiner Trees}{216}
\contentsline {subsection}{\numberline {4.1}Steiner Trees}{216}
\contentsline {subsection}{\numberline {4.2}Optimal S-RST for separable MSTs}{217}
\contentsline {part}{VLSI 3 \& Pattern Matching 1 (Noah Treuhaft)}{220}
\contentsline {section}{\numberline {1}Integer Programming For Global Routing}{220}
\contentsline {subsection}{\numberline {1.1}Concurrent Layout}{220}
\contentsline {subsection}{\numberline {1.2}Hierarchical Layout}{221}
\contentsline {section}{\numberline {2}Detailed Routing (Channel Routing)}{221}
\contentsline {subsection}{\numberline {2.1}Introduction}{221}
\contentsline {subsection}{\numberline {2.2}Left Edge Algorithm (LEA)}{222}
\contentsline {subsection}{\numberline {2.3}Greedy}{223}
\contentsline {section}{\numberline {3}Sequence Matching And Its Use In Computational Biology}{224}
\contentsline {subsection}{\numberline {3.1}DNA}{224}
\contentsline {subsection}{\numberline {3.2}Proteins}{224}
\contentsline {subsection}{\numberline {3.3}Human Genome Project}{224}
\contentsline {subsection}{\numberline {3.4}Sequence Alignment}{225}
\contentsline {part}{Pattern Matching 2 (Felix Wu)}{226}
\contentsline {section}{\numberline {1}Longest Common Subsequence}{226}
\contentsline {section}{\numberline {2}Global Sequence Alignment}{227}
\contentsline {subsection}{\numberline {2.1}Cost Functions for Protein Matching}{228}
\contentsline {section}{\numberline {3}Sequence Alignment Algorithms}{228}
\contentsline {subsection}{\numberline {3.1}Recursive Algorithm}{228}
\contentsline {subsection}{\numberline {3.2}Memoizing}{229}
\contentsline {subsection}{\numberline {3.3}Dynamic Programming}{229}
\contentsline {subsection}{\numberline {3.4}Space Efficiency}{230}
\contentsline {section}{\numberline {4}Gap Models}{231}
\contentsline {section}{\numberline {5}Local Alignment}{232}
\contentsline {section}{\numberline {6}Multiple Alignment}{233}
\contentsline {section}{\numberline {7}Biological Applications}{233}
\contentsline {part}{Indexing and Searching 1 (Helen J. Wang)}{234}
\contentsline {section}{\numberline {1}Pattern Matching (continued)}{234}
\contentsline {subsection}{\numberline {1.1}Ukkonen's Algorithm}{234}
\contentsline {section}{\numberline {2}Introduction to Indexing and Searching}{236}
\contentsline {section}{\numberline {3}Inverted File Indexing}{239}
\contentsline {subsection}{\numberline {3.1}Inverted File Compression}{239}
\contentsline {subsection}{\numberline {3.2}Representing and Accessing Lexicons}{242}
\contentsline {part}{Indexing and Searching 2 (Ben Horowitz)}{246}
\contentsline {section}{\numberline {1}Evaluating information retrieval effectiveness}{246}
\contentsline {section}{\numberline {2}Signature files}{247}
\contentsline {subsection}{\numberline {2.1}Generating signatures}{247}
\contentsline {subsection}{\numberline {2.2}Searching on Signatures}{248}
\contentsline {subsection}{\numberline {2.3}Query logic on signature files}{249}
\contentsline {subsection}{\numberline {2.4}Choosing signature width}{249}
\contentsline {subsection}{\numberline {2.5}An example: TREC}{250}
\contentsline {section}{\numberline {3}Vector space models}{250}
\contentsline {subsection}{\numberline {3.1}Selecting weights}{251}
\contentsline {subsection}{\numberline {3.2}Similarity measures}{251}
\contentsline {subsection}{\numberline {3.3}A simple example}{252}
\contentsline {subsection}{\numberline {3.4}Implementation of cosine measures using inverted lists}{253}
\contentsline {subsection}{\numberline {3.5}Relevance feedback}{254}
\contentsline {subsection}{\numberline {3.6}Clustering}{254}
\contentsline {section}{\numberline {4}Latent semantic indexing (LSI)}{254}
\contentsline {subsection}{\numberline {4.1}Singular value decomposition (SVD)}{255}
\contentsline {subsubsection}{\numberline {4.1.1}Definition}{255}
\contentsline {subsection}{\numberline {4.2}Using SVD for LSI}{256}
\contentsline {subsection}{\numberline {4.3}An example of LSI}{257}
\contentsline {subsection}{\numberline {4.4}Applications of LSI}{257}
\contentsline {subsection}{\numberline {4.5}Performance of LSI on TREC}{260}
\contentsline {part}{Evolutionary Trees and Web Indexing (Amar Chaudhary)}{262}
\contentsline {section}{\numberline {1}Evolutionary Trees (Andris Ambainis)}{262}
\contentsline {subsection}{\numberline {1.1}Parsimony}{263}
\contentsline {subsection}{\numberline {1.2}Maximum-Likelihood}{264}
\contentsline {subsection}{\numberline {1.3}Distance methods}{266}
\contentsline {section}{\numberline {2}Finding authoritative web pages using link structure (David Wagner)}{267}
\contentsline {subsection}{\numberline {2.1}A naive approach using adjacency}{268}
\contentsline {subsection}{\numberline {2.2}An algorithm for finding communities within topics}{268}
\contentsline {part}{Clustering (Josh MacDonald)}{272}
\contentsline {section}{\numberline {1}Principle Component Analysis}{272}
\contentsline {section}{\numberline {2}Introduction to Clustering}{274}
\contentsline {subsection}{\numberline {2.1}Applications}{274}
\contentsline {subsection}{\numberline {2.2}Similarity and Distance Measures}{275}
\contentsline {section}{\numberline {3}Clustering Algorithms}{275}
\contentsline {subsection}{\numberline {3.1}Bottom-Up Hierarchical Algorithms}{276}
\contentsline {subsection}{\numberline {3.2}Top-Down Hierarchical Algorithms}{277}
\contentsline {subsection}{\numberline {3.3}Optimization Algorithms}{278}
\contentsline {subsection}{\numberline {3.4}Density Search Algorithms}{279}
\contentsline {subsection}{\numberline {3.5}Summary}{279}
\contentsline {part}{Guest lecture Eric Brewer on HotBot (Carleton Miyamoto)}{280}
\contentsline {section}{\numberline {1}Comment on Assignment (Guy)}{280}
\contentsline {section}{\numberline {2}Goals of HotBot}{282}
\contentsline {section}{\numberline {3}Internal Architecture}{282}
\contentsline {subsection}{\numberline {3.1}Semantics}{282}
\contentsline {subsection}{\numberline {3.2}Hardware}{282}
\contentsline {subsection}{\numberline {3.3}Data Base Model}{283}
\contentsline {subsection}{\numberline {3.4}Score}{284}
\contentsline {subsection}{\numberline {3.5}Filters}{284}
\contentsline {section}{\numberline {4}Optimizations}{285}
\contentsline {subsection}{\numberline {4.1}Caching}{285}
\contentsline {subsection}{\numberline {4.2}Compression}{285}
\contentsline {subsection}{\numberline {4.3}Data Base}{285}
\contentsline {subsection}{\numberline {4.4}Parallelism}{285}
\contentsline {subsection}{\numberline {4.5}Misc.}{287}
\contentsline {section}{\numberline {5}Crawling}{287}
\contentsline {section}{\numberline {6}Summary}{288}
\contentsline {part}{Other Material}{289}
\contentsline {section}{\numberline {1}References by Topic}{289}
\contentsline {subsection}{\numberline {1.1}Compression}{289}
\contentsline {subsection}{\numberline {1.2}Cryptography}{289}
\contentsline {subsection}{\numberline {1.3}Linear and Integer Programming}{290}
\contentsline {subsection}{\numberline {1.4}Triangulation}{290}
\contentsline {subsection}{\numberline {1.5}N-body Simulation}{291}
\contentsline {subsection}{\numberline {1.6}VLSI Physical Design}{291}
\contentsline {subsection}{\numberline {1.7}Pattern Matching in Biology}{292}
\contentsline {subsection}{\numberline {1.8}Indexing and Searching}{292}
\contentsline {subsection}{\numberline {1.9}Clustering}{292}
\contentsline {section}{\numberline {2}Assignments}{292}
\contentsline {subsection}{Assignment 1 (Compression)}{293}
\contentsline {subsection}{Assignment 2 (Cryptography)}{295}
\contentsline {subsection}{Assignment 3 (Integer and Linear Programming)}{297}
\contentsline {subsection}{Assignment 4 (Triangulation and N-body)}{299}
\contentsline {subsection}{Assignment 5 (VLSI and Pattern Matching)}{302}