Algorithms and Data Structures: With Applications to Graphics and Geometry

Cover......Page 1
Title Page......Page 2
Copyright Page......Page 3
Dedication......Page 4
Contents\0......Page 6
PREFACE\0......Page 14
Part I Programming environments for motion, graphics, and geometry\0......Page 18
1.1 A robot car, its capabilities, and the task to be  performed\0......Page 20
1.2 Wall-following algorithm described informally\0......Page 22
1.4 Algorithm programmed in the robot\'s language\0......Page 23
1.5 The robot\'s program optimized\0......Page 24
2.1 Turtle graphics: A basic environment\0......Page 26
2.2 QuickDraw: A graphics toolbox\0......Page 29
2.3 A graphics frame program\0......Page 32
2.4 Example of a graphics routine: Polyline input\0......Page 35
3.1 Computer-driven visualization: Characteristics and techniques\0......Page 37
3.2 Example: The convex hull of points in the plane\0......Page 39
3.3 A gallery of algorithm snapshots\0......Page 41
Part II Programming concepts: Beyond notation\0......Page 48
4.1 Programming in the large versus programming in the small\0......Page 49
4.2 Documentation versus literature: Is it meant to be read?\0......Page 50
4.3 Pascal and its dialects: Lingua franca of computer science\0......Page 56
5.1 An algorithmic principle\0......Page 61
5.2 Divide-and-conquer expressed as a diagram: Merge sort\0......Page 62
5.3 Recursively defined trees\0......Page 63
5.4 Recursive tree traversal\0......Page 65
5.5 Recursion versus iteration: The Tower of Hanoi\0......Page 66
5.6 The flag of Alfanumerica: An algorithmic novel on iteration and recursion\0......Page 69
6.1 Syntax and semantics\0......Page 71
6.2 Grammars and their representation: Syntax diagrams and EBNF\0......Page 72
6.3 Example: Syntax of simple expressions\0......Page 74
6.4 An overly simple syntax for simple expressions\0......Page 76
6.5 Parenthesis-free notation for arithmetic expressions\0......Page 77
7.1 The role of syntax analysis\0......Page 80
7.2 Syntax analysis of parenthesis-free expressions by counting\0......Page 81
7.4 Turning syntax diagrams into a parser\0......Page 83
Part III Objects, algorithms, programs\0......Page 86
8.1 Bits and boolean functions\0......Page 88
8.2 Swapping and crossovers: The versatile exclusive-or\0......Page 89
8.3 The bit sum or \"population count\"\0......Page 90
9 ORDERED SETS\0......Page 98
9.1 Sequential search\0......Page 99
9.2 Binary search\0......Page 100
9.3 In-place permutation\0......Page 103
10.1 Recognizing a pattern consisting of a single string\0......Page 110
10.2 Recognizing a set of strings: A finite-state-machine interpreter\0......Page 111
11.1 Paths in a graph\0......Page 116
11.2 Boolean matrix multiplication\0......Page 117
11.3 Warshall\'s algorithm\0......Page 119
11.4 Minimum spanning tree in a graph\0......Page 121
12.1 Operations on integers\0......Page 124
12.2 The Euclidean algorithm\0......Page 127
12.3 The prime number sieve of Eratosthenes\0......Page 128
12.4 Large integers\0......Page 129
12.5 Modular number systems: The poor man\'s large integers\0......Page 130
12.6 Random numbers\0......Page 133
13.1 Floating point numbers\0......Page 136
13.2 Some dangers\0......Page 138
13.3 Homer\'s method\0......Page 140
13.4 Bisection\0......Page 141
13.5 Newton\'s method for computing the square root\0......Page 142
14.1 Intersection\0......Page 146
14.2 Clipping\0......Page 149
14.3 Drawing digitized lines\0......Page 151
14.4 The riddle of the braiding straight lines\0......Page 154
14.5 Digitized circles\0......Page 159
Part IV Complexity of problems and algorithms\0......Page 164
15.1 Models of computation: The ultimate RISC\0......Page 165
15.2 Almost nothing is computable\0......Page 169
15.3 The halting problem is undecidable\0......Page 170
15.4 Computable, yet unknown\0......Page 171
15.5 Multiplication of complex numbers\0......Page 173
15.6 Complexity of matrix multiplication\0......Page 174
16.1 Growth rates and orders of magnitude\0......Page 178
16.2 Asymptotics\0......Page 180
16.3 Summation formulas\0......Page 181
16.4 Recurrence relations\0......Page 183
16.5 Asymptotic performance of divide-and-conquer algorithms\0......Page 186
16.6 Permutations\0......Page 187
16.7 Trees\0......Page 188
17.1 What is sorting? How difficult is it?\0......Page 191
17.2 Types of sorting algorithms\0......Page 194
17.3 Simple sorting algorithms that work in time 0(n2)\0......Page 197
17.4 A lower bound Sl(n  log n)\0......Page 198
17.5 Quicksort\0......Page 200
17.6 Analysis for three cases: best, \"typical,\" and worst\0......Page 203
17.7 Merging and merge sorts\0......Page 205
17.8 Is it possible to sort in linear time?\0......Page 208
17.9 Sorting networks\0......Page 209
Part V Data structures\0......Page 214
18.1 Data structures old and new\0......Page 216
18.2 The range of data structures studied\0......Page 218
18.3 Performance criteria and measures\0......Page 219
19.1 Concepts: What and why?\0......Page 221
19.2 Stack\0......Page 223
19.3 First-in-first-out queue\0......Page 227
19.4 Priority queue\0......Page 229
19.5 Dictionary\0......Page 230
20.1 What is an implicit data structure?\0......Page 235
20.2 Array storage\0......Page 236
20.3 Implementation of the fixed-length fifo queue as a circular buffer\0......Page 241
20.4 Implementation of the fixed-length priority queue as a heap\0......Page 244
20.5 Heapsort\0......Page 249
21.1 Lists, memory management, pointer variables\0......Page 251
21.2 The fifo queue implemented as a one-way list\0......Page 254
21.3 Tree traversal\0......Page 255
21.4 Binary search trees\0......Page 265
21.5 Balanced trees: General definition\0......Page 269
21.6 Height-balanced trees\0......Page 271
21.7 Multiway trees\0......Page 277
22.1 Concepts and terminology\0......Page 284
22.3 The special case of perfect hashing: Table contents known a priori\0......Page 286
22.4 Conventional hash tables: Collision resolution\0......Page 288
22.5 Choice of hash function: Randomization\0......Page 293
22.6 Performance analysis\0......Page 295
22.7 Extendible hashing\0......Page 296
22.8 A virtual radix tree: Order-preserving extendible hashing\0......Page 298
23.1 Organizing the embedding space versus organizing its contents\0......Page 301
23.2 Radix trees, tries\0......Page 302
23.3 Quadtrees and octtrees\0......Page 303
23.4 Spatial data structures: Objectives and constraints\0......Page 305
23.5 The grid file\0......Page 307
23.6 Simple geometric objects and their parameter spaces\0......Page 311
23.7 Region queries of arbitrary shape\0......Page 313
23.9 Interaction between query processing and data access\0......Page 315
Part VI Interaction between algorithms and data structures: Case studies in geometric computation\0......Page 320
24.1 Geometry and geometric computation\0......Page 322
24.2 Convex hull: A multitude of algorithms\0......Page 324
24.3 The uses of convexity: Basic operations on polygons\0......Page 328
24.4 Visibility in the plane: A simple algorithm whose analysis is not\0......Page 331
25.1 The line segment intersection test\0......Page 338
25.2 The skeleton: Turning a space dimension into a time dimension\0......Page 340
25.3 Data structures\0......Page 341
25.5 Sweeping across intersections\0......Page 342
25.6 Degenerate configurations, numerical errors, robustness\0......Page 343
26.1 The problem\0......Page 346
26.2 Plane-sweep applied to the closest pair problem\0......Page 347
26.3 Implementation\0......Page 349
26.4 Analysis\0......Page 351
26.5 Sweeping in three or more dimensions\0......Page 352
REFERENCES\0......Page 355
INDEX\0......Page 360