Copyright ©1998-2010 Glenn Fleishman. Send in your comments. Bibliographic information on isbn.nu licensed from Baker & Taylor. Contact them for corrections and licensing, or read more about our data.
Tables of Contents for The Algorithm Design Manual
Chapter/Section Title
Page #
Page Count
Preface
vii
I TECHNIQUES
3
168
1 Introduction to Algorithms
3
24
1.1 Correctness and Efficiency
4
5
1.1.1 Correctness
5
4
1.1.2 Efficiency
9
1
1.2 Expressing Algorithms
9
1
1.3 Keeping Score
10
3
1.3.1 The RAM Model of Computation
10
1
1.3.2 Best, Worst, and Average-Case Complexity
11
2
1.4 The Big Oh Notation
13
2
1.5 Growth Rates
15
1
1.6 Logarithms
16
2
1.7 Modeling the Problem
18
2
1.8 About the War Stories
20
1
1.9 War Story: Psychic Modeling
21
4
1.10 Exercises
25
2
2 Data Structures and Sorting
27
26
2.1 Fundamental Data Types
28
5
2.1.1 Containers
28
1
2.1.2 Dictionaries
29
1
2.1.3 Binary Search Trees
30
1
2.1.4 Priority Queues
31
2
2.2 Specialized Data Structures
33
1
2.3 Sorting
33
1
2.4 Applications of Sorting
34
2
2.5 Approaches to Sorting
36
3
2.5.1 Data Structures
36
1
2.5.2 Incremental Insertion
36
1
2.5.3 Divide and Conquer
37
1
2.5.4 Randomization
37
1
2.5.5 Bucketing Techniques
38
1
2.6 War Story: Stripping Triangulations
39
4
2.7 War Story: Mystery of the Pyramids
43
2
2.8 War Story: String 'em Up
46
4
2.9 Exercises
50
3
3 Breaking Problems Down
53
28
3.1 Dynamic Programming
54
11
3.1.1 Fibonacci numbers
54
2
3.1.2 The Partition Problem
56
4
3.1.3 Approximate String Matching
60
2
3.1.4 Longest Increasing Sequence
62
2
3.1.5 Minimum Weight Triangulation
64
1
3.2 Limitations of Dynamic Programming
65
1
3.3 War Story: Evolution of the Lobster
66
3
3.4 War Story: What's Past Is Prolog
69
3
3.5 War Story: Text Compression for Bar Codes
72
3
3.6 Divide and Conquer
75
2
3.6.1 Fast Exponentiation
75
1
3.6.2 Binary Search
76
1
3.6.3 Square and Other Roots
76
1
3.7 Exercises
77
4
4 Graph Algorithms
81
34
4.1 The Friendship Graph
82
2
4.2 Data Structures for Graphs
84
2
4.3 War Story: Getting the Graph
86
2
4.4 Traversing a Graph
88
4
4.4.1 Breadth-First Search
89
2
4.4.2 Depth-First Search
91
1
4.5 Applications of Graph Traversal
92
3
4.5.1 Connected Components
92
1
4.5.2 Tree and Cycle Detection
93
1
4.5.3 Two-Coloring Graphs
93
1
4.5.4 Topological Sorting
94
1
4.5.5 Articulation Vertices
95
1
4.6 Modeling Graph Problems
95
2
4.7 Minimum Spanning Trees
97
3
4.7.1 Prim's Algorithm
98
1
4.7.2 Kruskal's Algorithm
99
1
4.8 Shortest Paths
100
2
4.8.1 Dijkstra's Algorithm
100
2
4.8.2 All-Pairs Shortest Path
102
1
4.9 War Story: Nothing but Nets
102
3
4.10 War Story: Dialing for Documents
105
5
4.11 Exercises
110
5
5 Combinatorial Search and Heuristic Methods
115
24
5.1 Backtracking
116
3
5.1.1 Constructing All Subsets
117
1
5.1.2 Constructing All Permutations
118
1
5.1.3 Constructing All Paths in a Graph
118
1
5.2 Search Pruning
119
1
5.3 Bandwidth Minimization
120
2
5.4 War Story: Covering Chessboards
122
3
5.5 Heuristic Methods
125
6
5.5.1 Simulated Annealing
125
4
5.5.2 Neural Networks
129
1
5.5.3 Genetic Algorithms
130
1
5.6 War Story: Annealing Arrays
131
3
5.7 Parallel Algorithms
134
1
5.8 War Story: Going Nowhere Fast
135
1
5.9 Exercises
136
3
6 Intractable Problems and Approximations
139
24
6.1 Problems and Reductions
140
1
6.2 Simple Reductions
141
3
6.2.1 Hamiltonian Cycle
142
1
6.2.2 Independent Set and Vertex Cover
142
2
6.2.3 Clique and Independent Set
144
1
6.3 Satisfiability
144
3
6.3.1 The Theory of NP-Completeness
145
1
6.3.2 3-Satisfiability
146
1
6.4 Difficult Reductions
147
4
6.4.1 Integer Programming
147
2
6.4.2 Vertex Cover
149
2
6.5 Other NP-Complete Problems
151
1
6.6 The Art of Proving Hardness
152
2
6.7 War Story: Hard Against the Clock
154
2
6.8 Approximation Algorithms
156
4
6.8.1 Approximating Vertex Cover
157
1
6.8.2 The Euclidean Traveling Salesman
158
2
6.9 Exercises
160
3
7 How to Design Algorithms
163
8
II RESOURCES
171
268
8 A Catalog of Algorithmic Problems
171
256
8.1 Data Structures
174
23
8.1.1 Dictionaries
175
5
8.1.2 Priority Queues
180
3
8.1.3 Suffix Trees and Arrays
183
4
8.1.4 Graph Data Structures
187
4
8.1.5 Set Data Structures
191
3
8.1.6 Kd-Trees
194
3
8.2 Numerical Problems
197
38
8.2.1 Solving Linear Equations
199
3
8.2.2 Bandwidth Reduction
202
2
8.2.3 Matrix Multiplication
204
3
8.2.4 Determinants and Permanents
207
2
8.2.5 Constrained and Unconstrained Optimization
209
4
8.2.6 Linear Programming
213
4
8.2.7 Random Number Generation
217
4
8.2.8 Factoring and Primality Testing
221
3
8.2.9 Arbitrary-Precision Arithmetic
224
4
8.2.10 Knapsack Problem
228
4
8.2.11 Discrete Fourier Transform
232
3
8.3 Combinatorial Problems
235
34
8.3.1 Sorting
236
4
8.3.2 Searching
240
4
8.3.3 Median and Selection
244
2
8.3.4 Generating Permutations
246
4
8.3.5 Generating Subsets
250
3
8.3.6 Generating Partitions
253
4
8.3.7 Generating Graphs
257
4
8.3.8 Calendrical Calculations
261
2
8.3.9 Job Scheduling
263
3
8.3.10 Satisfiability
266
3
8.4 Graph Problems: Polynomial-Time
269
42
8.4.1 Connected Components
270
3
8.4.2 Topological Sorting
273
2
8.4.3 Minimum Spanning Tree
275
4
8.4.4 Shortest Path
279
5
8.4.5 Transitive Closure and Reduction
284
3
8.4.6 Matching
287
4
8.4.7 Eulerian Cycle Chinese Postman
291
3
8.4.8 Edge and Vertex Connectivity
294
3
8.4.9 Network Flow
297
4
8.4.10 Drawing Graphs Nicely
301
4
8.4.11 Drawing Trees
305
3
8.4.12 Planarity Detection and Embedding
308
3
8.5 Graph Problems: Hard Problems
311
34
8.5.1 Clique
312
3
8.5.2 Independent Set
315
2
8.5.3 Vertex Cover
317
2
8.5.4 Traveling Salesman Problem
319
4
8.5.5 Hamiltonian Cycle
323
3
8.5.6 Graph Partition
326
3
8.5.7 Vertex Coloring
329
4
8.5.8 Edge Coloring
333
2
8.5.9 Graph Isomorphism
335
4
8.5.10 Steiner Tree
339
4
8.5.11 Feedback Edge Vertex Set
343
2
8.6 Computational Geometry
345
52
8.6.1 Robust Geometric Primitives
347
4
8.6.2 Convex Hull
351
4
8.6.3 Triangulation
355
3
8.6.4 Voronoi Diagrams
358
3
8.6.5 Nearest Neighbor Search
361
3
8.6.6 Range Search
364
3
8.6.7 Point Location
367
3
8.6.8 Intersection Detection
370
4
8.6.9 Bin Packing
374
3
8.6.10 Medial-Axis Transformation
377
3
8.6.11 Polygon Partitioning
380
3
8.6.12 Simplifying Polygons
383
3
8.6.13 Shape Similarity
386
3
8.6.14 Motion Planning
389
3
8.6.15 Maintaining Line Arrangements
392
3
8.6.16 Minkowski Sum
395
2
8.7 Set and String Problems
397
30
8.7.1 Set Cover
398
3
8.7.2 Set Packing
401
2
8.7.3 String Matching
403
3
8.7.4 Approximate String Matching
406
4
8.7.5 Text Compression
410
4
8.7.6 Cryptography
414
4
8.7.7 Finite State Machine Minimization
418
4
8.7.8 Longest Common Substring
422
3
8.7.9 Shortest Common Superstring
425
2
9 Algorithmic Resources
427
12
9.1 Software Systems
427
6
9.1.1 LEDA
428
1
9.1.2 Netlib
428
1
9.1.3 The Stanford GraphBase
429
1
9.1.4 Combinatorica
430
1
9.1.5 Algorithm Animations with XTango
430
1
9.1.6 Programs from Books
431
2
9.2 Data Sources
433
1
9.3 Textbooks
434
1
9.4 On-Line Resources
435
2
9.4.1 Literature
436
1
9.4.2 People
436
1
9.4.3 Software
437
1
9.5 Professional Consulting Services
437
2
Bibliography
439
24
Index
463