Preface
\contentsline Introduction
\contentsline Structure of the chapters
\contentsline Naming of variables
\contentsline Probabilities
\contentsline Asymptotic notation
\contentsline About the programming languages
\contentsline On the code for the algorithms
\contentsline Complexity measures and real timings
\contentsline Basic Concepts
\contentsline {section}{\numberline {2.1}Data structure description}{9}
\contentsline {subsection}{\numberline {2.1.1}Grammar for data objects}{9}
\contentsline {subsection}{\numberline {2.1.2}Constraints for data objects}{12}
\contentsline {subsubsection}{\numberline {2.1.2.1}Sequential order}{13}
\contentsline {subsubsection}{\numberline {2.1.2.2}Uniqueness}{13}
\contentsline {subsubsection}{\numberline {2.1.2.3}Hierarchical order}{13}
\contentsline {subsubsection}{\numberline {2.1.2.4}Hierarchical balance}{13}
\contentsline {subsubsection}{\numberline {2.1.2.5}Optimality}{14}
\contentsline {section}{\numberline {2.2}Algorithm descriptions}{14}
\contentsline {subsection}{\numberline {2.2.1}Basic (or atomic) operations}{15}
\contentsline {subsection}{\numberline {2.2.2}Building procedures}{17}
\contentsline {subsubsection}{\numberline {2.2.2.1}Composition}{17}
\contentsline {subsubsection}{\numberline {2.2.2.2}Alternation}{21}
\contentsline {subsubsection}{\numberline {2.2.2.3}Conformation}{22}
\contentsline {subsubsection}{\numberline {2.2.2.4}Self-organization}{23}
\contentsline {subsection}{\numberline {2.2.3}Interchangeability}{23}
\contentsline Searching Algorithms
\contentsline {section}{\numberline {3.1}Sequential search}{25}
\contentsline {subsection}{\numberline {3.1.1}Basic sequential search}{25}
\contentsline {subsection}{\numberline {3.1.2}Self-organizing sequential search: move-to-front method}{28}
\contentsline {subsection}{\numberline {3.1.3}Self-organizing\penalty \@M \ sequential\penalty \@M \ search: transpose method}{31}
\contentsline {subsection}{\numberline {3.1.4}Optimal sequential search}{34}
\contentsline {subsection}{\numberline {3.1.5}Jump search}{35}
\contentsline {section}{\numberline {3.2}Sorted array search}{36}
\contentsline {subsection}{\numberline {3.2.1}Binary search}{37}
\contentsline {subsection}{\numberline {3.2.2}Interpolation search}{39}
\contentsline {subsection}{\numberline {3.2.3}Interpolation--sequential search}{42}
\contentsline {section}{\numberline {3.3}Hashing}{43}
\contentsline {subsection}{\numberline {3.3.1}Practical hashing functions}{47}
\contentsline {subsection}{\numberline {3.3.2}Uniform probing hashing}{48}
\contentsline {subsection}{\numberline {3.3.3}Random probing hashing}{50}
\contentsline {subsection}{\numberline {3.3.4}Linear probing hashing}{51}
\contentsline {subsection}{\numberline {3.3.5}Double hashing}{55}
\contentsline {subsection}{\numberline {3.3.6}Quadratic hashing}{57}
\contentsline {subsection}{\numberline {3.3.7}Ordered and split-sequence hashing}{59}
\contentsline {subsection}{\numberline {3.3.8}Reorganization schemes}{62}
\contentsline {subsubsection}{\numberline {3.3.8.1}Brent's algorithm}{62}
\contentsline {subsubsection}{\numberline {3.3.8.2}Binary tree hashing}{64}
\contentsline {subsubsection}{\numberline {3.3.8.3}Last-come-first-served hashing}{67}
\contentsline {subsubsection}{\numberline {3.3.8.4}Robin Hood hashing}{69}
\contentsline {subsubsection}{\numberline {3.3.8.5}Self-adjusting hashing}{70}
\contentsline {subsection}{\numberline {3.3.9}Optimal hashing}{70}
\contentsline {subsection}{\numberline {3.3.10}Direct chaining hashing}{71}
\contentsline {subsection}{\numberline {3.3.11}Separate chaining hashing}{74}
\contentsline {subsection}{\numberline {3.3.12}Coalesced hashing}{77}
\contentsline {subsection}{\numberline {3.3.13}Extendible hashing}{80}
\contentsline {subsection}{\numberline {3.3.14}Linear hashing}{82}
\contentsline {subsection}{\numberline {3.3.15}External hashing using minimal internal storage}{85}
\contentsline {subsection}{\numberline {3.3.16}Perfect hashing}{87}
\contentsline {subsection}{\numberline {3.3.17}Summary}{90}
\contentsline {section}{\numberline {3.4}Recursive structures search}{91}
\contentsline {subsection}{\numberline {3.4.1}Binary tree search}{91}
\contentsline {subsubsection}{\numberline {3.4.1.1}Randomly generated binary trees}{94}
\contentsline {subsubsection}{\numberline {3.4.1.2}Random binary trees}{96}
\contentsline {subsubsection}{\numberline {3.4.1.3}Height-balanced trees}{97}
\contentsline {subsubsection}{\numberline {3.4.1.4}Weight-balanced trees}{100}
\contentsline {subsubsection}{\numberline {3.4.1.5}Balancing by internal path reduction}{102}
\contentsline {subsubsection}{\numberline {3.4.1.6}Heuristic organization schemes on binary trees}{105}
\contentsline {subsubsection}{\numberline {3.4.1.7}Optimal binary tree search}{109}
\contentsline {subsubsection}{\numberline {3.4.1.8}Rotations in binary trees}{112}
\contentsline {subsubsection}{\numberline {3.4.1.9}Deletions in binary trees}{114}
\contentsline {subsubsection}{\numberline {3.4.1.10}$m$-ary search trees}{116}
\contentsline {subsection}{\numberline {3.4.2}B-trees}{117}
\contentsline {subsubsection}{\numberline {3.4.2.1}2--3 trees}{124}
\contentsline {subsubsection}{\numberline {3.4.2.2}Symmetric binary B-trees}{126}
\contentsline {subsubsection}{\numberline {3.4.2.3}1--2 trees}{128}
\contentsline {subsubsection}{\numberline {3.4.2.4}2-3-4 trees}{129}
\contentsline {subsubsection}{\numberline {3.4.2.5}B-tree variations}{130}
\contentsline {subsection}{\numberline {3.4.3}Index and indexed sequential files}{130}
\contentsline {subsubsection}{\numberline {3.4.3.1}Index sequential access method}{132}
\contentsline {subsection}{\numberline {3.4.4}Digital trees}{133}
\contentsline {subsubsection}{\numberline {3.4.4.1}Hybrid tries}{137}
\contentsline {subsubsection}{\numberline {3.4.4.2}Tries for word-dictionaries}{138}
\contentsline {subsubsection}{\numberline {3.4.4.3}Digital search trees}{138}
\contentsline {subsubsection}{\numberline {3.4.4.4}Compressed tries}{140}
\contentsline {subsubsection}{\numberline {3.4.4.5}Patricia trees}{140}
\contentsline {section}{\numberline {3.5}Multidimensional search}{143}
\contentsline {subsection}{\numberline {3.5.1}Quad trees}{144}
\contentsline {subsubsection}{\numberline {3.5.1.1}Quad tries}{146}
\contentsline {subsection}{\numberline {3.5.2}K-dimensional trees}{149}
\contentsline {chapter}{\numberline {4}Sorting Algorithms}{153}
\contentsline {section}{\numberline {4.1}Techniques for sorting arrays}{153}
\contentsline {subsection}{\numberline {4.1.1}Bubble sort}{154}
\contentsline {subsection}{\numberline {4.1.2}Linear insertion sort}{156}
\contentsline {subsection}{\numberline {4.1.3}Quicksort}{158}
\contentsline {subsection}{\numberline {4.1.4}Shellsort}{161}
\contentsline {subsection}{\numberline {4.1.5}Heapsort}{164}
\contentsline {subsection}{\numberline {4.1.6}Interpolation sort}{166}
\contentsline {subsection}{\numberline {4.1.7}Linear probing sort}{168}
\contentsline {subsection}{\numberline {4.1.8}Summary}{170}
\contentsline {section}{\numberline {4.2}Sorting other data structures}{171}
\contentsline {subsection}{\numberline {4.2.1}Merge sort}{173}
\contentsline {subsection}{\numberline {4.2.2}Quicksort for lists}{174}
\contentsline {subsection}{\numberline {4.2.3}Bucket sort}{176}
\contentsline {subsection}{\numberline {4.2.4}Radix sort}{179}
\contentsline {subsection}{\numberline {4.2.5}Hybrid methods of sorting}{180}
\contentsline {subsubsection}{\numberline {4.2.5.1}Recursion termination}{181}
\contentsline {subsubsection}{\numberline {4.2.5.2}Distributive partitioning}{181}
\contentsline {subsubsection}{\numberline {4.2.5.3}Non-recursive bucket sort}{182}
\contentsline {subsection}{\numberline {4.2.6}Treesort}{182}
\contentsline {section}{\numberline {4.3}Merging}{183}
\contentsline {subsection}{\numberline {4.3.1}List merging}{184}
\contentsline {subsection}{\numberline {4.3.2}Array merging}{185}
\contentsline {subsection}{\numberline {4.3.3}Minimal-comparison merging}{186}
\contentsline {section}{\numberline {4.4}External sorting}{187}
\contentsline {subsection}{\numberline {4.4.1}Selection phase techniques}{189}
\contentsline {subsubsection}{\numberline {4.4.1.1}Replacement selection}{189}
\contentsline {subsubsection}{\numberline {4.4.1.2}Natural selection}{190}
\contentsline {subsubsection}{\numberline {4.4.1.3}Alternating selection}{191}
\contentsline {subsubsection}{\numberline {4.4.1.4}Merging phase}{192}
\contentsline {subsection}{\numberline {4.4.2}Balanced merge sort}{193}
\contentsline {subsection}{\numberline {4.4.3}Cascade merge sort}{195}
\contentsline {subsection}{\numberline {4.4.4}Polyphase merge sort}{196}
\contentsline {subsection}{\numberline {4.4.5}Oscillating merge sort}{200}
\contentsline {subsection}{\numberline {4.4.6}External Quicksort}{201}
\contentsline {chapter}{\numberline {5}Selection Algorithms}{205}
\contentsline {section}{\numberline {5.1}Priority queues}{205}
\contentsline {subsection}{\numberline {5.1.1}Sorted/unsorted lists}{206}
\contentsline {subsection}{\numberline {5.1.2}P-trees}{209}
\contentsline {subsection}{\numberline {5.1.3}Heaps}{211}
\contentsline {subsection}{\numberline {5.1.4}Van Emde-Boas priority queues}{216}
\contentsline {subsection}{\numberline {5.1.5}Pagodas}{218}
\contentsline {subsection}{\numberline {5.1.6}Binary trees used as priority queues}{221}
\contentsline {subsubsection}{\numberline {5.1.6.1}Leftist trees}{221}
\contentsline {subsubsection}{\numberline {5.1.6.2}Binary priority queues}{223}
\contentsline {subsubsection}{\numberline {5.1.6.3}Binary search trees as priority queues}{225}
\contentsline {subsection}{\numberline {5.1.7}Binomial queues}{226}
\contentsline {subsection}{\numberline {5.1.8}Summary}{227}
\contentsline {section}{\numberline {5.2}Selection of $k$th element}{228}
\contentsline {subsection}{\numberline {5.2.1}Selection by sorting}{230}
\contentsline {subsection}{\numberline {5.2.2}Selection by tail recursion}{230}
\contentsline {subsection}{\numberline {5.2.3}Selection of the mode}{232}
\contentsline {chapter}{\numberline {6}Arithmetic Algorithms}{235}
\contentsline {section}{\numberline {6.1}Basic operations, multiplication/division}{235}
\contentsline {section}{\numberline {6.2}Other arithmetic functions}{240}
\contentsline {subsection}{\numberline {6.2.1}Binary powering}{240}
\contentsline {subsection}{\numberline {6.2.2}Arithmetic-geometric mean}{242}
\contentsline {subsection}{\numberline {6.2.3}Transcendental functions}{243}
\contentsline {section}{\numberline {6.3}Matrix multiplication}{245}
\contentsline {subsection}{\numberline {6.3.1}Strassen's matrix multiplication}{246}
\contentsline {subsection}{\numberline {6.3.2}Further asymptotic improvements}{247}
\contentsline {section}{\numberline {6.4}Polynomial evaluation}{248}
\contentsline {chapter}{\numberline {7}Text Algorithms}{251}
\contentsline {section}{\numberline {7.1}Text searching without preprocessing}{251}
\contentsline {subsection}{\numberline {7.1.1}Brute force text searching}{253}
\contentsline {subsection}{\numberline {7.1.2}Knuth--Morris--Pratt text searching}{254}
\contentsline {subsection}{\numberline {7.1.3}Boyer--Moore text searching}{256}
\contentsline {subsection}{\numberline {7.1.4}Searching sets of strings}{259}
\contentsline {subsection}{\numberline {7.1.5}Karp--Rabin text searching}{260}
\contentsline {subsection}{\numberline {7.1.6}Searching text with automata}{262}
\contentsline {subsection}{\numberline {7.1.7}Shift-or text searching}{266}
\contentsline {subsection}{\numberline {7.1.8}String similarity searching}{267}
\contentsline {subsection}{\numberline {7.1.9}Summary of direct text searching}{270}
\contentsline {section}{\numberline {7.2}Searching preprocessed text}{270}
\contentsline {subsection}{\numberline {7.2.1}Inverted files}{271}
\contentsline {subsection}{\numberline {7.2.2}Trees used for text searching}{273}
\contentsline {paragraph}{Prefix searching}{273}
\contentsline {paragraph}{Range searching}{274}
\contentsline {paragraph}{Longest repetition searching}{274}
\contentsline {paragraph}{`Most significant' or `most frequent' searching}{275}
\contentsline {subsection}{\numberline {7.2.3}Searching text with automata}{275}
\contentsline {subsection}{\numberline {7.2.4}Suffix arrays and \PAT arrays}{277}
\contentsline {subsection}{\numberline {7.2.5}DAWG}{279}
\contentsline {subsection}{\numberline {7.2.6}Hashing methods for text searching}{280}
\contentsline {subsection}{\numberline {7.2.7}P-strings}{281}
\contentsline {section}{\numberline {7.3}Other text searching problems}{283}
\contentsline {subsection}{\numberline {7.3.1}Searching longest common subsequences}{283}
\contentsline {subsection}{\numberline {7.3.2}Two-dimensional searching}{284}
\contentsline {paragraph}{Linear time algorithms}{285}
\contentsline {paragraph}{Fast algorithm on average}{286}
\contentsline {paragraph}{Algorithm with preprocessing of the text}{286}
\contentsline {chapter}{\numberline {\uppercase {i}}Distributions Derived from Empirical Observation}{289}
\contentsline {section}{\numberline {\uppercase {i}.1}Zipf's law}{289}
\contentsline {subsection}{\numberline {\uppercase {i}.1.1}First generalization of a Zipfian distribution}{290}
\contentsline {subsection}{\numberline {\uppercase {i}.1.2}Second generalization of a Zipfian distribution}{290}
\contentsline {section}{\numberline {\uppercase {i}.2}Bradford's law}{291}
\contentsline {section}{\numberline {\uppercase {i}.3}Lotka's law}{293}
\contentsline {section}{\numberline {\uppercase {i}.4}80\%--20\% rule}{293}
\contentsline {chapter}{\numberline {\uppercase {ii}}Asymptotic Expansions}{297}
\contentsline {section}{\numberline {\uppercase {ii}.1}Asymptotic expansions of sums}{298}
\contentsline {section}{\numberline {\uppercase {ii}.2}Gamma-type expansions}{300}
\contentsline {section}{\numberline {\uppercase {ii}.3}Exponential-type expansions}{301}
\contentsline {section}{\numberline {\uppercase {ii}.4}Asymptotic expansions of sums and definite integrals containing ${\prm e}^{-x^{2}}$ }{302}
\contentsline {section}{\numberline {\uppercase {ii}.5}Doubly exponential forms}{303}
\contentsline {section}{\numberline {\uppercase {ii}.6}Roots of polynomials}{304}
\contentsline {section}{\numberline {\uppercase {ii}.7}Sums containing descending factorials}{305}
\contentsline {section}{\numberline {\uppercase {ii}.8}Summation formulas}{307}
\contentsline {chapter}{\numberline {\uppercase {iii}}References}{309}
\contentsline {section}{\numberline {\uppercase {iii}.1}Textbooks}{309}
\contentsline {section}{\numberline {\uppercase {iii}.2}Papers}{311}
\contentsline {chapter}{\numberline {\uppercase {iv}}Algorithms coded in Pascal and C}{375}
\contentsline {section}{\numberline {\uppercase {iv}.1}Searching algorithms}{375}
\contentsline {section}{\numberline {\uppercase {iv}.2}Sorting algorithms}{387}
\contentsline {section}{\numberline {\uppercase {iv}.3}Selection algorithms}{399}
\contentsline {section}{\numberline {\uppercase {iv}.4}Text algorithms}{408}
\contentsline {chapter}{Index}{415}