Research Catalog

Title

Algorithms and data structures : with applications to graphics and geometry / Jurg Nievergelt, Klaus Hinrichs.

Author

Nievergelt, Jurg.

Publication

Englewood Cliffs, NJ : Prentice Hall, ©1993.

Items in the Library & Off-site

Holdings

Details

Additional Authors

Hinrichs, Klaus.

Description

xvi, 350 pages : illustrations; 24 cm

Subject

• Computer algorithms
• Data structures (Computer science)
• Computer graphics
• Estructura de datos (Ciencia de la computación)
• Gráficas por computadoras
• Computer algorithms
• Algoritmen
• Datastructuren
• Algorithmus
• Computer
• Computergrafik
• Datenstruktur
• Informatik
• Datenstruktur
• Algorithmus
• Computers

Bibliography (note)

• Includes bibliographical references (pages 338-342) and index.

Processing Action (note)

• committed to retain

Contents

• Pt. 1. Programming environments for motion, graphics, and geometry -- 1. Reducing a Task to Given Primitives: Programming Motion -- 1.1. A robot car, its capabilities, and the task to be performed -- 1.2. Wall-following algorithm described informally -- 1.3. Algorithm specified in a high-level language -- 1.4. Algorithm programmed in the robot's language -- 1.5. The robot's program optimized -- 2. Graphics Primitives and Environments -- 2.1. Turtle graphics: A basic environment -- 2.2. QuickDraw: A graphics toolbox -- 2.3. A graphics frame program -- 2.4. Example of a graphics routine: Polyline input -- 3. Algorithm Animation -- 3.1. Computer-driven visualization: Characteristics and techniques -- 3.2. Example: The convex hull of points in the plane -- 3.3. A gallery of algorithm snapshots -- Pt. II. Programming concepts: Beyond notation -- 4. Algorithms and Programs as Literature: Substance and Form -- 4.1. Programming in the large versus programming in the small -- 4.2. Documentation versus literature: Is it meant to be read? -- 4.3. Pascal and its dialects: Lingua franca of computer science -- 5. Divide-And-Conquer and Recursion -- 5.1. An algorithmic principle -- 5.2. Divide-and-conquer expressed as a diagram: Merge sort -- 5.3. Recursively defined trees -- 5.4. Recursive tree traversal -- 5.5. Recursion versus iteration: The Tower of Hanoi -- 5.6. The flag of Alfanumerica: An algorithmic novel on iteration and recursion -- 6. Syntax -- 6.1. Syntax and semantics
• 6.2. Grammars and their representation: Syntax diagrams and EBNF -- 6.3. Example: Syntax of simple expressions -- 6.4. An overly simple syntax for simple expressions -- 6.5. Parenthesis-free notation for arithmetic expressions -- 7. Syntax Analysis -- 7.1. The role of syntax analysis -- 7.2. Syntax analysis of parenthesis-free expressions by counting -- 7.3. Analysis by recursive descent -- 7.4. Turning syntax diagrams into a parser -- Pt. III. Objects, algorithms, programs -- 8. Truth Values, the Data Type 'SET', and Bit Acrobatics -- 8.1. Bits and boolean functions -- 8.2. Swapping and crossovers: The versatile exclusive-or -- 8.3. The bit sum or "population count" -- 9. Ordered Sets -- 9.1. Sequential search -- 9.2. Binary search -- 9.3. In-place permutation -- 10. Strings -- 10.1. Recognizing a pattern consisting of a single string -- 10.2. Recognizing a set of strings: A finite-state-machine interpreter -- 11. Matrices and Graphs: Transitive Closure -- 11.1. Paths in a graph -- 11.2. Boolean matrix multiplication -- 11.3. Warshall's algorithm -- 11.4. Minimum spanning tree in a graph -- 12. Integers -- 12.1. Operations on integers -- 12.2. The Euclidean algorithm -- 12.3. The prime number sieve of Eratosthenes -- 12.4. Large integers -- 12.5. Modulular number systems: The poor man's large integers -- 12.6. Random numbers -- 13. Reals -- 13.1. Floating point numbers -- 13.2. Some dangers -- 13.3. Homer's method -- 13.4. Bisection
• 13.5. Newton's method for computing the square root -- 14. Straight Lines and Circles -- 14.1. Intersection -- 14.2. Clipping -- 14.3. Drawing digitized lines -- 14.4. The riddle of the braiding straight lines -- 14.5. Digitized circles -- Pt. IV. Complexity of problems and algorithms -- 15. Computability and Complexity -- 15.1. Models of computation: The ultimate RISC -- 15.2. Almost nothing is computable -- 15.3. The halting problem is undecidable -- 15.4. Computable, yet unknown -- 15.5. Multiplication of complex numbers -- 15.6. Complexity of matrix multiplication -- 16. The Mathematics of Algorithm Analysis -- 16.1. Growth rates and orders of magnitude -- 16.2. Asymptotics -- 16.3. Summation formulas -- 16.4. Recurrence relations -- 16.5. Asymptotic performance of divide-and-conquer algorithms -- 16.6. Permutations -- 16.7. Trees -- 17. Sorting and Its Complexity -- 17.1. What is sorting? How difficult is it? -- 17.2. Types of sorting algorithms -- 17.3. Simple sorting algorithms that work in time [actual symbol not reproducible] -- 17.4. A lower bound [actual symbol not reproducible] -- 17.5. Quicksort -- 17.6. Analysis for three cases: best, "typical," and worst -- 17.7. Merging and merge sorts -- 17.8. Is it possible to sort in linear time? -- 17.9. Sorting networks -- Pt. V. Data structures -- 18. What Is a Data Structure? -- 18.1. Data structures old and new -- 18.2. The range of data structures studied -- 18.3. Performance criteria and measures
• 19. Abstract Data Types -- 19.1. Concepts: What and why? -- 19.2. Stack -- 19.3. First-in-first-out queue -- 19.4. Priority queue -- 19.5. Dictionary -- 20. Implicit Data Structures -- 20.1. What is an implicit data structure? -- 20.2. Array storage -- 20.3. Implementation of the fixed-length fifo queue as a circular buffer -- 20.4. Implementation of the fixed-length priority queue as a heap -- 20.5. Heapsort -- 21. List Structures -- 21.1. Lists, memory management, pointer variables -- 21.2. The fifo queue implemented as a one-way list -- 21.3. Tree traversal -- 21.4. Binary search trees -- 21.5. Balanced trees: General definition -- 21.6. Height-balanced trees -- 21.7. Multiway trees -- 22. Address Computation -- 22.1. Concepts and terminology -- 22.2. The special case of small key domains -- 22.3. The special case of perfect hashing: Table contents known a priori -- 22.4. Conventional hash tables: Collision resolution -- 22.5. Choice of hash function: Randomization -- 22.6. Performance analysis -- 22.7. Extendible hashing -- 22.8. A virtual radix tree: Order-preserving extendible hashing -- 23. Metric Data Structures -- 23.1. Organizing the embedding space versus organizing its contents -- 23.2. Radix trees, tries -- 23.3. Quadtrees and octtrees -- 23.4. Spatial data structures: Objectives and constraints -- 23.5. The grid file -- 23.6. Simple geometric objects and their parameter spaces -- 23.7. Region queries of arbitrary shape
• 23.8. Evaluating region queries with a grid file -- 23.9. Interaction between query processing and data access -- Pt. VI. Ineraction between algorithms and data structures: Case studies in geometric computation -- 24. Sample Problems and Algorithms -- 24.1. Geometry and geometric computation -- 24.2. Convex hull: A multitude of algorithms -- 24.3. The uses of convexity: Basic operations on polygons -- 24.4. Visibility in the plane: A simple algorithm whose analysis is not -- 25. Plane-Sweep: A General-Purpose Algorithm for Two-Dimensional Problems Illustrated Using Line Segment Intersection -- 25.1. The line segment intersection test -- 25.2. The skeleton: Turning a space dimension into a time dimension -- 25.3. Data structures -- 25.4. Updating the y-table and detecting an intersection -- 25.5. Sweeping across intersections -- 25.6. Degenerate configurations, numerical errors, robustness -- 26. The Closest Pair Problem -- 26.1. The problem -- 26.2. Plane-sweep applied to the closest pair problem -- 26.3. Implementation -- 26.4. Analysis -- 26.5. Sweeping in three or more dimensions.

ISBN

• 0134894286
• 9780134894287

LCCN

^^^92004687^

OCLC

• 25409154
• SCSB-10060096

Owning Institutions

Harvard Library