\section*{List Of Algorithms}
\addcontentsline{toc}{part}{List of Algorithms}

The following algorithms are covered to some extent in these notes, ranging
from a short overview to a full lecture.

\contentsline{section}{Compression}{}
\contentsline{subsection}{Huffman Coding}{17}
\contentsline{subsection}{Arithmetic Coding}{18}
\contentsline{subsection}{LZ78 and LZW}{20}
\contentsline{subsection}{LZ77 (Sliding Windows)}{22}
\contentsline{subsection}{JPEG Coding}{33}
\contentsline{subsection}{MPEG Coding}{37}
\contentsline{subsection}{Wavelet Compression}{44}

\contentsline{section}{Cryptography}{}
\contentsline{subsection}{DES}{57}
\contentsline{subsection}{RC4}{68}
\contentsline{subsection}{Merkle-Hellman Knapsack Algorithm}{69}
\contentsline{subsection}{RSA}{70}
\contentsline{subsection}{ElGamal}{75}
\contentsline{subsection}{Blum-Goldwasser}{75}

\contentsline{section}{Linear Programming}{}
\contentsline{subsection}{Simplex}{86}
\contentsline{subsection}{Ellipsoid Algorithm: Khachian}{97}
\contentsline{subsection}{Interior Point: Affine Scaling}{104}
\contentsline{subsection}{Interior Point: Potential Reduction}{106}
\contentsline{subsection}{Interior Point: Central Trajectory}{107}

\contentsline{section}{Integer Programming}{}
\contentsline{subsection}{Branch and Bound Enumeration}{112}
\contentsline{subsection}{Implicit Enumeration}{114}
\contentsline{subsection}{Cutting Plane}{117}
\contentsline{subsection}{Crew Scheduling: Anbil, Tanga and Johnson}{118}

\contentsline{section}{Triangulation}{}
\contentsline{subsection}{Convex Hull: Giftwrapping}{134}
\contentsline{subsection}{Convex Hull: Graham Scan}{134}
\contentsline{subsection}{Convex Hull: Mergehull}{136}
\contentsline{subsection}{Convex Hull: Quickhull}{137}
\contentsline{subsection}{Delaunay Triangulation: Blelloch, Miller, and Talmor}{144}
\contentsline{subsection}{Delaunay Triangulation: Incremental}{148}
\contentsline{subsection}{Meshing: Ruppert's Algorithm}{150}
\contentsline{subsection}{Surface Modeling: Garland and Heckbert}{163}

\contentsline{section}{N-body Simulation}{}
\contentsline{subsection}{Particle Mesh (using FFT}{170}
\contentsline{subsection}{Barnes-Hut}{172}
\contentsline{subsection}{Fast Multipole Method: Greengard and Rokhlyn}{176}
\contentsline{subsection}{Callahan and Kosaraju}{185}

\contentsline{section}{VLSI Physical Design}{}
\contentsline{subsection}{Shortest paths: Dijkstra's Algorithm}{213}
\contentsline{subsection}{Shortest paths: Hadlock's Algorithm}{215}
\contentsline{subsection}{Optimal Rectilinear Steiner Trees}{217}
\contentsline{subsection}{Routing with Integer Programming}{220}
\contentsline{subsection}{Detailed Routing: Left Edge Algorithm}{222}
\contentsline{subsection}{Detailed Routing: Greedy Algorithm}{223}

\contentsline{section}{Pattern Matching in Biology}{}
\contentsline{subsection}{Sequence Alignment: Memoizing}{229}
\contentsline{subsection}{Sequence Alignment: Dynamic Programming}{229}
\contentsline{subsection}{Sequence Alignment: Hirschberg}{230}
\contentsline{subsection}{Alignment with Gaps: Waterman-Smith-Beyer}{231}
\contentsline{subsection}{Alignment with Gaps: Gotoh}{231}
\contentsline{subsection}{Local Alignment: Smith-Waterman}{232}
\contentsline{subsection}{Sequence Alignment: Ukkonen}{234}

\contentsline{section}{Indexing and Searching}{}
\contentsline{subsection}{Inverted File Compression}{239}
\contentsline{subsection}{Searching Signature Files}{248}
\contentsline{subsection}{Vector Space Searching}{253}
\contentsline{subsection}{Latent Semantic Indexing (LSI)}{254}
\contentsline{subsection}{Authoritative Pages: Kleinberg}{268}

\contentsline{section}{Clustering}{}
\contentsline{subsection}{Bottom-up Hierarchical Clustering}{276}
\contentsline{subsection}{Splinter Group Clustering}{277}
\contentsline{subsection}{Clustering with Linear Programming}{278}
\contentsline{subsection}{Density Search Clustering}{279}
