Index

actual parameter

PreorderInorder, and Postorder , PreorderInorder, and Postorder

acyclic

directed graph: Directed Acyclic Graphs

adapter

address

adjacency lists

adjacency matrix

adjacent

ADT

seeabstract data type

algorithmic abstraction

Algorithmic Abstraction

ancestor

UnionIntersection, and Difference

proper: More Terminology

and

annealing

annealing schedule

About Arithmetic Series Summation

arc

directed: Terminology
undirected: Undirected Graphs

ArgumentError

extract Method

arithmetic series

arithmetic series summation

An example-Geometric Series Summation, About Arithmetic Series Summation

arity

Foundational Data Structures

array

ASCII

Character String Keys

association

Searchable Containers

asymptotic behavior

Asymptotic Notation

attribute

class: InstancesInstance Attributes and
instance: InstancesInstance Attributes and

attribute accessor

attribute reader

attribute writer

attributes

AVL balance condition

AVL rotation

AVL tree

B-Tree

Bachmann, P.

An Asymptotic Upper Bound-Big

backtracking algorithms

Backtracking Algorithms

bag

Projects, Multisets

balance condition

AVL Search Trees, B-Trees

AVL: AVL Search Trees

base class

Class Hierarchy, Derivation and Inheritance

big oh

An Asymptotic Upper Bound-Big

tightness: Tight Big Oh Bounds, More Notation-Theta and Little
tightness: Tight Big Oh Bounds, More Notation-Theta and Little
transitive property: Properties of Big Oh

Bignum

The Basic Axioms, Example-Fibonacci Numbers

binary digit

Binomial Queues

binary heap

binary operator

Locating Items in an , Example-Binary Search

binary search

binary search tree

Binary Search Trees, Binary Search Trees

binary tree

Binary Trees, Binary Trees

complete: Complete Trees

binding

binomial

binomial coefficient

bit

Binomial Queues

Boolean

and: UnionIntersection, and Difference
or: UnionIntersection, and Difference

bound

Constructing Spanning Trees

branch-and-bound

Branch-and-Bound Solvers

breadth-first spanning tree

breadth-first traversal

Applications, Applications, Breadth-First Traversal, Example-Balancing Scales, Breadth-First Traversal

brute-force algorithms

Brute-Force and Greedy Algorithms

bubble sort

Bubble Sort

bucket sort

Example-Bucket Sort

buckets

Example-Bucket Sort

C++ programming language

carry

Merging Binomial Queues

ceiling function

About Harmonic Numbers

central limit theorem

Singly-Linked Lists, Doubly-Linked and Circular Lists

chained scatter table

Chained Scatter Table

child

Applications, Terminology

circular list

class

Classes

abstract: Algorithmic Abstraction

class attribute

InstancesInstance Attributes and

clock frequency

A Simplified Model of

clock period

A Simplified Model of

coalesce

Chained Scatter Table

cocktail shaker sort

coefficient

binomial: Binomial Trees

collapsing find

Collapsing Find

column-major order

The Fragmentation Problem

commensurate

elements: Sorted Lists, Basics
elements: Sorted Lists, Basics
functions: More Big Oh Fallacies , More Big Oh Fallacies
functions: More Big Oh Fallacies , More Big Oh Fallacies

compact

compaction

Mark-and-Compact Garbage Collection

complement

Complete Trees, Sorting with a Heap

complete N-ary tree

Complete N-ary Trees

complete binary tree

complex numbers

Example-Complex Numbers

component

connected: Connectedness of an Undirected

compound statement

Rules For Big Oh

concrete class

Class Hierarchy, Class Hierarchy

conjunction

Connectedness of an Undirected , Exercises

connected

undirected graph: Connectedness of an Undirected

connected component

conquer

seedivide

constant

ContainerEmpty

first and last Methods

copy

clone Method

shallow: clone Method

critical activity

critical path

critical path analysis

cubic

cycle

negative cost: Single-Source Shortest Path
simple: More Terminology

dangling pointer

dangling reference

The Fragmentation Problem

data ordering property

M-Way Search Trees

database

Associations

decision tree

A Lower Bound on

defragment

degree

in: Terminology
out: Terminology

dense graph

Sparse vs. Dense Graphs

depth

Constructing Spanning Trees

depth-first spanning tree

depth-first traversal

Example-Balancing Scales, Depth-First Traversal

deque

StacksQueues, and Deques, Deques

derivation

Class Hierarchy, Derivation and Inheritance

derivative

Derivation and Inheritance

derived class

descendant

SetsMultisets, and Partitions, Basics, UnionIntersection, and Difference

proper: More Terminology

difference

symmetric: Exercises

differentiation

digit

binary: Binomial Queues

digraph

seedirected graph

Dijkstra's algorithm

Dijkstra's Algorithm

directed acyclic graph

Directed Acyclic Graphs

directed arc

Discrete Event Simulation

directed graph

Directed Graphs

discrete event simulation

disjunction

distribution sorting

Distribution Sorting

distribution sorts

Top-Down Algorithms: Divide-and-Conquer

divide and conquer

division method of hashing

Division Method

double hashing

Double Hashing

double rotation

Doubly-Linked and Circular Lists

double-ended queue

Deques

doubly-linked list

dual

dynamic binding

Bottom-Up Algorithms: Dynamic
Programming

dynamic programming

earliest event time

edge

Applications, Terminology

emanate: Terminology
incident: Terminology

element

emanate

enumerator

Projects

equivalence classes

Applications, Kruskal's Algorithm

equivalence of trees

Comparing Trees

equivalence relation

Euler's constant

About Harmonic Numbers, Solving The Recurrence-Telescoping, Average Running Time

Euler, Leonhard

Eulerian walk

evaluation stack

Postfix Notation

event-node graph

exception

first and last Methods, extract Method

exception handler

Exceptions

exceptions

Exceptions

exchange sorting

Exchange Sorting

exchange sorts

Character String Keys, Character String Keys

exclusive or

exponent

Floating-Point Keys

exponential

exponential cooling

Exponentially Distributed Random Variables

exponential distribution

expression tree

Expression Trees

extend

Example-Graphical Objects

external node

Analyzing Recursive Methods

external path length

Unsuccessful Search

factorial

feasible solution

Brute-Force Algorithm

Fibonacci hashing method

Fibonacci Hashing

Fibonacci number

Fibonacci Hashing, AVL Search Trees

Fibonacci numbers

Example-Fibonacci Numbers, Example-Computing Fibonacci Numbers

closed-form expression: Example-Fibonacci Numbers
generalized: Example-Generalized Fibonacci Numbers

FIFO

Queues

fifo-in, first-out

Queues

find

collapsing: Collapsing Find

Fixnum

The Basic Axioms, Example-Fibonacci Numbers

floor function

About Harmonic Numbers

Floyd's algorithm

Floyd's Algorithm

forest

Binomial Queues, Binomial Queues, Implementing a Partition using

formal parameter

Foundational Data Structures

foundational data structure

fully connected graph

garbage

garbage collection

mark-and-compact: Mark-and-Compact Garbage Collection
mark-and-sweep: Mark-and-Sweep Garbage Collection
reference counting: Reference Counting Garbage Collection
stop-and-copy: Stop-and-Copy Garbage Collection

Gauss, Karl Friedrich

Example-Generalized Fibonacci Numbers

generalized Fibonacci numbers

generator

IteratorsGenerators, and the

geometric series

About Geometric Series Summation

geometric series summation

An example-Geometric Series Summation, Example-Geometric Series Summation Again, About Geometric Series Summation, Example-Geometric Series Summation Yet

golden ratio

Fibonacci Hashing

graph

connectedness: Connectedness of an Undirected
dense: Sparse vs. Dense Graphs
directed: Directed Graphs
directed acyclic: Directed Acyclic Graphs
labeled: Labeled Graphs
sparse: Sparse vs. Dense Graphs
traversal: Graph Traversals
undirected: Undirected Graphs

graph theory

Graphs and Graph Algorithms

handle

Handles

harmonic number

Average Running Times, About Harmonic Numbers, Average Case Analysis, Solving The Recurrence-Telescoping, Average Running Time

harmonic series

About Harmonic Numbers

hash function

Keys and Hash Functions, Keys and Hash Functions

hash table

Hash Tables

hashing

division method: Division Method
Fibonacci method: Fibonacci Hashing
middle-square method: Middle Square Method
multiplication method: Multiplication Method

head

Singly-Linked Lists

heap

Basics, Garbage Collection and the

heapify

heapsort

Depth-FirstBranch-and-Bound Solver

height

of a node in a tree: More Terminology
of a tree: More Terminology

heuristic

hierarchy

Trees

Horner's rule

Another example-Horner's Rule, Example-Geometric Series Summation Again, Character String Keys

in-degree

Terminology, Topological Sort

in-place sorting

Insertion Sorting, Selection Sorting

incident

increment

infix

Derivation and Inheritance

infix notation

Infix Notation

inheritance

multiple: Derivation and Inheritance

inorder traversal

Inorder Traversal, Traversing a Search Tree

M-way tree: Traversing a Search Tree

insertion sorting

Insertion Sorting

straight: Straight Insertion Sort

insertion sorts

InstancesInstance Attributes and

instance

instance attribute

InstancesInstance Attributes and

internal node

SetsMultisets, and Partitions, Basics, UnionIntersection, and Difference

internal path length

Unsuccessful Search

complete binary tree: Complete Trees

internal path length of a tree

Successful Search

Internet domain name

Character String Keys

intersection

interval

search: Locating Items in an

inverse modulo W

Multiplication Method

inversion

Average Running Time

isomorphic

Alternate Representations for Trees

isomorphic trees

Example-Fibonacci Numbers

iterative algorithm

iterator

Iterators

iterator protocol

Iterators

Java programming language

Associations, Keys and Hash Functions

key

keyed data

Using Associations

knapsack problem

Example-0/1 Knapsack Problem

Kruskal's algorithm

Kruskal's Algorithm

L'Hôpital's rule

About Logarithms, About Logarithms

labeled graph

Labeled Graphs

lambda

seeload factor

last-in, first-out

Stacks

latest event time

leaf

leaf node

least-significant-digit-first radix sorting

Binary Trees, M-Way Search Trees

left subtree

leftist tree

Leftist Trees

level

level-order

Complete N-ary Trees

level-order traversal

Array Subscript Calculations

lexicographic order

lexicographic ordering

lexicographically precede

Abstract Data Types, Abstract Data Types, Objects and Types

lifetime

LIFO

Stacks

limit

Properties of Big Oh

linear

linear congruential random number generator

Yet Another example-Finding the

linear probing

Linear Probing

linear search

linked list

Foundational Data Structures

list

Ordered Lists and Sorted

little oh

More Notation-Theta and Little

live

Mark-and-Sweep Garbage Collection

LL rotation

Single Rotations

in a B-tree: Removing Items from a

load factor

Average Case Analysis

log squared

logarithm

loop

More Notation-Theta and Little

loose asymptotic bound

LR rotation

ukasiewicz, Jan

Mark-and-Compact Garbage Collection

M-way search tree

M-Way Search Trees

mantissa

Floating-Point Keys

many-to-one mapping

Keys and Hash Functions

mark-and-compact garbage collection

mark-and-sweep garbage collection

Mark-and-Sweep Garbage Collection

matrix

Matrices

adjacency: Adjacency Matrices
sparse: Adjacency Matrices

max-heap

median

Selecting the Pivot

median-of-three pivot selection

Selecting the Pivot

memory leak

merge sort

Example-Merge Sorting

merge sorting

Merge Sorting

merge sorts

mergeable priority queue

The Minimal Standard Random

merging nodes in a B-tree

Removing Items from a

Mersenne primes

method

static: Static Methods

middle-square hashing method

Middle Square Method

min heap

minimal subgraph

minimum spanning tree

mix-in

mixed linear congruential random number generator

modulus

Derivation and Inheritance

Monte Carlo methods

Monte Carlo Methods

multi-dimensional array

Multi-Dimensional Arrays

multiple inheritance

multiplication hashing method

Multiplication Method

multiplicative linear congruential random number generator

Abstract Data Types, Abstract Data Types, Abstract Data Types, Variables

multiset

Multisets

N-ary tree

N-ary tree: N-ary Trees

N-queens problem

N-queens problem: Exercises

name

Nary tree

textbf

negative cost cycle

Single-Source Shortest Path

nested class

Implementation, Nested Classes

Newton, Isaac.

Example-Fibonacci Numbers

node

Applications, Basics, N-ary Trees, Binary Trees, Terminology

non-recursive algorithm

normalize

null path length

Leftist Trees, Leftist Trees

object

Objects and Types

object-oriented programming

object-oriented programming language

objective function

Brute-Force Algorithm

odd-even transposition sort

An Asymptotic Lower Bound-Omega

omega

open addressing

Scatter Table using Open

operator overloading

Operator Overloading

operator precedence

optimal binary search tree

UnionIntersection, and Difference

or

ordered list

Ordered Lists and Sorted

ordered tree

N-ary Trees, Binary Trees

ordinal number

Positions of Items in

oriented tree

out-degree

Class Hierarchy, Derivation and Inheritance, Derivation and Inheritance

overloading operators

Operator Overloading

override

parameter passing

parent

Applications, Terminology

parentheses

partial order

Partitions, Kruskal's Algorithm

partition

Pascal's triangle

Example-Computing Binomial Coefficients

Pascal, Blaise

Example-Computing Binomial Coefficients

pass-by-reference

path

Searching a Binary Tree, AVL Search Trees

access: Inserting Items into an

path length

external: Unsuccessful Search
internal: Unsuccessful Search
weighted: Shortest-Path Algorithms

perfect binary tree

period

pivot

Quicksort

Polish notation

Class Hierarchy, Polymorphism

polymorphism

polynomial

About Polynomials, About Polynomials Again

postcondition

Inserting Items in a

postorder traversal

Postorder Traversal

power set

Array and Bit-Vector Sets

precede lexicographically

Instance Attributes, More Terminology

precondition

Inserting Items in a

predecessor

prefix notation

Prefix Notation

preorder traversal

Preorder Traversal

prepend

prepend Method

Prim's algorithm

Prim's Algorithm

primary clustering

Linear Probing

prime

relatively: Multiplication Method

priority queue

mergeable: Basics

probability density function

Exponentially Distributed Random Variables

probe sequence

Scatter Table using Open

proper subset

proper superset

pruning a solution space

Branch-and-Bound Solvers

pseudorandom

quadratic

quadratic probing

Quadratic Probing

queue

StacksQueues, and Deques

quicksort

Quicksort

radix sorting

raise

Exceptions

random number generator

linear congruential: Generating Random Numbers
mixed linear congruential: Generating Random Numbers
multiplicative linear congruential: Generating Random Numbers

random numbers

random variable

Random Variables

rank

Union by Height or

reader

attribute: Attribute Accessors

record

Analyzing Recursive Methods

recurrence relation

recursive algorithm

Analyzing Recursive Methods, Example-Fibonacci Numbers

reference count

Reference Counting Garbage Collection

reference counting garbage collection

Reference Counting Garbage Collection

reflexive

Solving Recurrence Relations-Repeated Substitution

relation

equivalence: Applications

relatively prime

Multiplication Method

repeated substitution

Reverse-Polish notation

right subtree

Binary Trees

RL rotation

Basics, Mark-and-Sweep Garbage Collection

root

rotation

AVL: Balancing AVL Trees
double: Double Rotations
LL: Single Rotations, Removing Items from a
LL: Single Rotations, Removing Items from a
LR: Double Rotations
RL: Double Rotations
RR: Single Rotations, Removing Items from a
RR: Single Rotations, Removing Items from a
single: Double Rotations

row-major order

Array Subscript Calculations

RPN

seeReverse-Polish notation

RR rotation

Single Rotations

in a B-tree: Removing Items from a

Ruby programming language

Abstract Data Types, Abstract Data Types

scales

Example-Balancing Scales

scatter tables

Scatter Tables

scope

search interval

Locating Items in an

search tree

M-way: M-Way Search Trees
binary: Binary Search Trees

seed

selection sorting

Selection Sorting

selection sorts

Singly-Linked Lists, Adjacency Matrices

sentinel

separate chaining

Separate Chaining

set

shallow copy

sibling

sign

significant

simple cycle

simulated annealing

Discrete Event Simulation

simulation time

single rotation

Doubly-Linked and Circular Lists

single-ended queue

Queues

singleton

Exercises, Implementation

singly-linked list

size

slack time

Abstract Backtracking Solvers

slide

Handles

solution space

Example-Balancing Scales

solver

sort

topological: Topological Sort

sorted list

Ordered Lists and Sorted , Sorted Lists, Basics

sorter

Sorting and Sorters

sorting

in place: Selection Sorting
in-place: Insertion Sorting

sorting algorithm

bucket sort: Example-Bucket Sort

sorting by distribution

Distribution Sorting

sorting by exchanging

Exchange Sorting

sorting by insertion

Insertion Sorting

sorting by merging

Merge Sorting

sorting by selection

Selection Sorting

source

spanning tree

Discrete Event Simulation

breadth-first: Constructing Spanning Trees
depth-first: Constructing Spanning Trees
minimum: Minimum-Cost Spanning Trees

sparse graph

Sparse vs. Dense Graphs

sparse matrix

specializes

stable sorts

stack

stack frame

state

static binding

Stop-and-Copy Garbage Collection

static method

Static Methods

Stirling numbers

Partitions, Partitions

stop-and-copy garbage collection

straight insertion sorting

Straight Insertion Sort

straight selection sorting

Straight Selection Sorting

strongly connected

Connectedness of a Directed

subgraph

minimal: Minimum-Cost Spanning Trees

subset

proper: Comparing Sets

subtraction

subtree

Instance Attributes, More Terminology

successor

superclass

Example-Graphical Objects

superset

HashingHash Tables, and , Applications

proper: Comparing Sets

symbol table

symmetric

symmetric difference

Singly-Linked Lists, Singly-Linked Lists

tail

telescoping

Solving The Recurrence-Telescoping, Running Time of Divide-and-Conquer

temperature

tertiary tree

More Notation-Theta and Little

theta

tight asymptotic bound

Tight Big Oh Bounds

time

simulation: Discrete Event Simulation

topological sort

Topological Sort

total order

Tree Traversals, Example-Balancing Scales, Graph Traversals

binary trees: Comparing Trees

transitive

Sorted Lists, Applications, Basics

traversal

breadth-first: Breadth-First Traversal, Breadth-First Traversal
breadth-first: Breadth-First Traversal, Breadth-First Traversal
depth-first: Depth-First Traversal
inorder: Inorder Traversal, Traversing a Search Tree
inorder: Inorder Traversal, Traversing a Search Tree
postorder: Postorder Traversal
preorder: Preorder Traversal

tree

N-ary: N-ary Trees
binary: Binary Trees
equivalence: Comparing Trees
expression: Expression Trees
height: More Terminology
internal path length: Successful Search
leftist: Leftist Trees
ordered: N-ary Trees, Binary Trees
ordered: N-ary Trees, Binary Trees
oriented: N-ary Trees
search: seesearch tree
tertiary: N-ary Trees
traversal: Tree Traversals

tree traversal

Abstract Data Types, Objects and Types

type

undirected arc

Undirected Graphs

undirected graph

Undirected Graphs

uniform distribution

Spreading Keys Evenly

uniform hashing model

Average Case Analysis

union

SetsMultisets, and Partitions, Basics, UnionIntersection, and Difference

union by rank

Union by Height or

union by size

Union by Size

universal set

SetsMultisets, and Partitions, Kruskal's Algorithm

unsorted list

Abstract Data Types, Associations, Objects and Types

value

Venn diagram

Alternate Representations for Trees, SetsMultisets, and Partitions

vertex

visibility