The Algorithm Design Manual - Steven S. Skiena

Descriere

n{*DRAFT*}Introduction to Algorithm DesignAlgorithm Analysis nData Structures nSorting and Searching nDivide and Conquer nRandomized Algorithms and Hashing nGraph Traversal nWeighted Graph Algorithms nCombinatorial Search and Heuristic Methods nDynamic Programming nNP-Completeness nDealing with Hard Problems nHow to Design Algorithms14 A Catalog of Algorithmic Problems 43715 Data Structures 43915.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44015.2 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44515.3 Sux Trees and Arrays . . . . . . . . . . . . . . . . . . . . . . . 44815.4 Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 45215.5 Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 45615.6 Kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46016 Numerical Problems 46516.1 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . . . 46716.2 Bandwidth Reduction . . . . . . . . . . . . . . . . . . . . . . . . 47016.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 47216.4 Determinants and Permanents . . . . . . . . . . . . . . . . . . . 47516.5 Constrained/Unconstrained Optimization . . . . . . . . . . . . . 47816.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 48216.7 Random Number Generation . . . . . . . . . . . . . . . . . . . . 48616.8 Factoring and Primality Testing . . . . . . . . . . . . . . . . . . . 49016.9 Arbitrary-Precision Arithmetic . . . . . . . . . . . . . . . . . . . 49316.10Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 49716.11Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . 50117 Combinatorial Problems 50517.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50617.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51017.3 Median and Selection . . . . . . . . . . . . . . . . . . . . . . . . . 51417.4 Generating Permutations . . . . . . . . . . . . . . . . . . . . . . 51717.5 Generating Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 52117.6 Generating Partitions . . . . . . . . . . . . . . . . . . . . . . . . 52417.7 Generating Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 52817.8 Calendrical Calculations . . . . . . . . . . . . . . . . . . . . . . . 53217.9 Job Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53417.10