| |
| |
| Preface | |
| |
| |
| Programming environments for motion, graphics, and geometry | |
| |
| |
| Reducing a Task to Given Primitives: Programming Motion | |
| |
| |
| A robot car, its capabilities, and the task to be performed | |
| |
| |
| Wall-following algorithm described informally | |
| |
| |
| Algorithm specified in a high-level language | |
| |
| |
| Algorithm programmed in the robot's language | |
| |
| |
| The robot's program optimized | |
| |
| |
| Graphics Primitives and Environments | |
| |
| |
| Turtle graphics: A basic environment | |
| |
| |
| QuickDraw: A graphics toolbox | |
| |
| |
| A graphics frame program | |
| |
| |
| Example of a graphics routine: Polyline input | |
| |
| |
| Algorithm Animation | |
| |
| |
| Computer-driven visualization: Characteristics and techniques | |
| |
| |
| Example: The convex hull of points in the plane | |
| |
| |
| A gallery of algorithm snapshots | |
| |
| |
| Programming concepts: Beyond notation | |
| |
| |
| Algorithms and Programs as Literature: Substance and Form | |
| |
| |
| Programming in the large versus programming in the small | |
| |
| |
| Documentation versus literature: Is it meant to be read? | |
| |
| |
| Pascal and its dialects: Lingua franca of computer science | |
| |
| |
| Divide-And-Conquer and Recursion | |
| |
| |
| An algorithmic principle | |
| |
| |
| Divide-and-conquer expressed as a diagram: Merge sort | |
| |
| |
| Recursively defined trees | |
| |
| |
| Recursive tree traversal | |
| |
| |
| Recursion versus iteration: The Tower of Hanoi | |
| |
| |
| The flag of Alfanumerica: An algorithmic novel on iteration and recursion | |
| |
| |
| Syntax | |
| |
| |
| Syntax and semantics | |
| |
| |
| Grammars and their representation: Syntax diagrams and EBNF | |
| |
| |
| Example: Syntax of simple expressions | |
| |
| |
| An overly simple syntax for simple expressions | |
| |
| |
| Parenthesis-free notation for arithmetic expressions | |
| |
| |
| Syntax Analysis | |
| |
| |
| The role of syntax analysis | |
| |
| |
| Syntax analysis of parenthesis-free expressions by counting | |
| |
| |
| Analysis by recursive descent | |
| |
| |
| Turning syntax diagrams into a parser | |
| |
| |
| Objects, algorithms, programs | |
| |
| |
| Truth Values, the Data Type 'SET', and Bit Acrobatics | |
| |
| |
| Bits and boolean functions | |
| |
| |
| Swapping and crossovers: The versatile exclusive-or | |
| |
| |
| The bit sum or "population count" | |
| |
| |
| Ordered Sets | |
| |
| |
| Sequential search | |
| |
| |
| Binary search | |
| |
| |
| In-place permutation | |
| |
| |
| Strings | |
| |
| |
| Recognizing a pattern consisting of a single string | |
| |
| |
| Recognizing a set of strings: A finite-state-machine interpreter | |
| |
| |
| Matrices and Graphs: Transitive Closure | |
| |
| |
| Paths in a graph | |
| |
| |
| Boolean matrix multiplication | |
| |
| |
| Warshall's algorithm | |
| |
| |
| Minimum spanning tree in a graph | |
| |
| |
| Integers | |
| |
| |
| Operations on integers | |
| |
| |
| The Euclidean algorithm | |
| |
| |
| The prime number sieve of Eratosthenes | |
| |
| |
| Large integers | |
| |
| |
| Modulular number systems: The poor man's large integers | |
| |
| |
| Random numbers | |
| |
| |
| Reals | |
| |
| |
| Floating point numbers | |
| |
| |
| Some dangers | |
| |
| |
| Homer's method | |
| |
| |
| Bisection | |
| |
| |
| Newton's method for computing the square root | |
| |
| |
| Straight Lines and Circles | |
| |
| |
| Intersection | |
| |
| |
| Clipping | |
| |
| |
| Drawing digitized lines | |
| |
| |
| The riddle of the braiding straight lines | |
| |
| |
| Digitized circles | |
| |
| |
| Complexity of problems and algorithms | |
| |
| |
| Computability and Complexity | |
| |
| |
| Models of computation: The ultimate RISC | |
| |
| |
| Almost nothing is computable | |
| |
| |
| The halting problem is undecidable | |
| |
| |
| Computable, yet unknown | |
| |
| |
| Multiplication of complex numbers | |
| |
| |
| Complexity of matrix multiplication | |
| |
| |
| The Mathematics of Algorithm Analysis | |
| |
| |
| Growth rates and orders of magnitude | |
| |
| |
| Asymptotics | |
| |
| |
| Summation formulas | |
| |
| |
| Recurrence relations | |
| |
| |
| Asymptotic performance of divide-and-conquer algorithms | |
| |
| |
| Permutations | |
| |
| |
| Trees | |
| |
| |
| Sorting and Its Complexity | |
| |
| |
| What is sorting? How difficult is it? | |
| |
| |
| Types of sorting algorithms | |
| |
| |
| Simple sorting algorithms that work in time [actual symbol not reproducible] | |
| |
| |
| A lower bound [actual symbol not reproducible] | |
| |
| |
| Quicksort | |
| |
| |
| Analysis for three cases: best, "typical," and worst | |
| |
| |
| Merging and merge sorts | |
| |
| |
| Is it possible to sort in linear time? | |
| |
| |
| Sorting networks | |
| |
| |
| Data structures | |
| |
| |
| What Is a Data Structure? | |
| |
| |
| Data structures old and new | |
| |
| |
| The range of data structures studied | |
| |
| |
| Perfomance criteria and measures | |
| |
| |
| Abstract Data Types | |
| |
| |
| Concepts: What and why? | |
| |
| |
| Stack | |
| |
| |
| First-in-first-out queue | |
| |
| |
| Priority queue | |
| |
| |
| Dictionary | |
| |
| |
| Implicit Data Structures | |
| |
| |
| What is an implicit data structure? | |
| |
| |
| Array storage | |
| |
| |
| Implementation of the fixed-length fifo queue as a circular buffer | |
| |
| |
| Implementation of the fixed-length priority queue as a heap | |
| |
| |
| Heapsort | |
| |
| |
| List Structures | |
| |
| |
| Lists, memory management, pointer variables | |
| |
| |
| The fifo queue implemented as a one-way list | |
| |
| |
| Tree traversal | |
| |
| |
| Binary search trees | |
| |
| |
| Balanced trees: General definition | |
| |
| |
| Height-balanced trees | |
| |
| |
| Multiway trees | |
| |
| |
| Address Computation | |
| |
| |
| Concepts and terminology | |
| |
| |
| The special case of small key domains | |
| |
| |
| The special case of perfect hashing: Table contents known a priori | |
| |
| |
| Conventional hash tables: Collision resolution | |
| |
| |
| Choice of hash function: Randomization | |
| |
| |
| Performance analysis | |
| |
| |
| Extendible hashing | |
| |
| |
| A virtual radix tree: Order-preserving extendible hashing | |
| |
| |
| Metric Data Structures | |
| |
| |
| Organizing the embedding space versus organizing its contents | |
| |
| |
| Radix trees, tries | |
| |
| |
| Quadtrees and octtrees | |
| |
| |
| Spatial data structures: Objectives and constraints | |
| |
| |
| The grid file | |
| |
| |
| Simple geometric objects and their parameter spaces | |
| |
| |
| Region queries of arbitrary shape | |
| |
| |
| Evaluating region queries with a grid file | |
| |
| |
| Interaction between query processing and data access | |
| |
| |
| Ineraction between algorithms and data structures: Case studies in geometric computation | |
| |
| |
| Sample Problems and Algorithms | |
| |
| |
| Geometry and geometric computation | |
| |
| |
| Convex hull: A multitude of algorithms | |
| |
| |
| The uses of convexity: Basic operations on polygons | |
| |
| |
| Visibility in the plane: A simple algorithm whose analysis is not | |
| |
| |
| Plane-Sweep: A General-Purpose Algorithm for Two-Dimensional Problems Illustrated Using Line Segment Intersection | |
| |
| |
| The line segment intersection test | |
| |
| |
| The skeleton: Turning a space dimension into a time dimension | |
| |
| |
| Data structures | |
| |
| |
| Updating the y-table and detecting an intersection | |
| |
| |
| Sweeping across intersections | |
| |
| |
| Degenerate configurations, numerical errors, robustness | |
| |
| |
| The Closest Pair Problem | |
| |
| |
| The problem | |
| |
| |
| Plane-sweep applied to the closest pair problem | |
| |
| |
| Implementation | |
| |
| |
| Analysis | |
| |
| |
| Sweeping in three or more dimensions | |
| |
| |
| References | |
| |
| |
| Index | |