Nievergelt, “**Algorithms and Data Structures** – With Applications to Graphics and Geometry” (2011)

An Open Textbook by Jurg Nievergelt and Klaus Hinrichs

“An introductory coverage of algorithms and data structures with application to graphics and geometry.”

This textbook, released under a Creative Commons Share Alike (CC BY SA) license, is presented in its original format with the academic content unchanged. It was authored by Jurg Nievergelt (ETH Zurich) and Klaus Hinrichs (Institut für Informatik) and provided by the University of Georgia’s Global Textbook Project.

Photo Credit: Renato Keshet (GFDL) commons.wikimedia.org

**Buy** Print Copy $39.99 (371 pages, paperback, B&W)

Free PDF Download (5.5 Mb)

**Table of Contents**

[bg_faq_start]

### Part I: 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

Algorithm animation

Computer-driven visualization: characteristics and techniques

A gallery of algorithm snapshots

### Part II: 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

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

### Part III: 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

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

Modular number systems: the poor man’s large integers

Random numbers

Reals

Floating-point numbers

Some dangers

Horner’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

### Part IV: 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 T(n)

A lower bound O(n · log n)

Quicksort

Analysis for three cases: best, “typical”, and worst

Is it possible to sort in linear time?

Sorting networks

### Part V: Data structures

What is a data structure?

Data structures old and new

The range of data structures studied

Performance 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

Height-balanced 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

### Part VI: Interaction 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

The problem

Plane-sweep applied to the closest pair problem

Implementation

Analysis

Sweeping in three or more dimensions

[bg_faq_start]