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