Index
Symbols
2-3 search tree 424–431
2-nodes and 3-nodes 424
analysis of 429
defined 424
height 429
insertion 425–427
order 424
perfect balance 424
and red-black BST 432
search 425
2-3 tree. See 2-3 search tree
2-colorability problem 546
2-dimensional array 19
2-satisfiability problem 599
2-sum problem 189
3-collinear problem 211
3-way partitioning 298
3-way quicksort 298–301
3-way string quicksort 719–723
8-puzzle problem 358
32-bit architecture 13, 201, 212
A
A* algorithm 350
Abstract data type 64
API 65
client 88–89
design 96–97
implementing an 84–87
multiple implementations 90
Abstract in-place merge 270
Accumulator data type 92–93
Acyclic digraph. See Directed acyclic graph
Acyclic edge-weighted digraph. See Edge-weighted DAG
Adjacency list
directed graph 568–569
edge-weighted digraph 644
edge-weighted graph 609
undirected graph 524–525
Adjacency set 527
Adjacent vertex 519
ADT. See Abstract data type
Algorithm
century of 853
defined 4
deterministic 4
nondeterministic 914
randomized 198
Aliasing
of arrays 19
of objects 69
of substrings 202
All-pairs reachability 590
All-pairs shortest paths 656
Alphabet data type 698–700
Amortized analysis
binary heap 320
defined 198–199
hash table 475
resizing array 199
weighted quick-union with path compression 231
Analysis of algorithms 172–215. See also Propositions; See also Properties
amortized analysis 198–199
big-Oh notation 206–207
cost model 182
divide-and-conquer 272
doubling ratio 192–193
doubling test 176–177
input models 197
log-log plot 176
mathematical models 178
memory usage 200–204
multiple parameters 196
observations 173–175
order-of-growth 179
order-of-growth classifications 186–188
order-of-growth hypothesis 180
problem size 173
randomized algorithm 198
scientific method 172
tilde approximation 178
worst-case guarantee 197
Antisymmetric relation 247
Accumulator 93
Alphabet 698
Bag 121
BinaryStdIn 812
BinaryStdOut 812
Buffer 170
CC 543
Counter 65
Date 79
Degrees 596
Deque 167
Digraph 568
DirectedCycle 576
DirectedDFS 570
DirectedEdge 641
Draw 83
Edge 608
EdgeWeightedDigraph 641
EdgeWeightedGraph 608
FixedCapacityStack 135
FixedCapacityStackOfStrings 133
FlowEdge 890
FlowNetwork 890
GeneralizedQueue 169
Graph 522
GraphProperties 559
IndexMaxPQ 320
IndexMinPQ 320
Interval1D 77
Interval2D 77
java.lang.Double 34
java.lang.Integer 34
java.lang.Math 28
java.lang.String 80
java.util.Arrays 29
KMP 769
List 511
MathSET 509
Matrix 60
MaxPQ 309
MinPQ 309
MST 613
Page 870
Particle 860
Paths 535
Point2D 77
Queue 121
RandomBag 167
RandomQueue 168
Rational 117
SCC 586
Search 528
SET 489
Stack 121
StaticSETofInts 99
StdDraw 43
StdIn 39
StdOut 37
StdRandom 30
StdStats 30
Stopwatch 175
StringSET 754
StringST 730
SuffixArray 879
SymbolDigraph 581
SymbolGraph 548
Topological 578
Transaction 79
TransitiveClosure 592
UF 219
VisualAccumulator 95
Application programming interface. See also APIs
client 28
contract 33
data type definition 65
implementation 28
library of static methods 28
Arbitrage detection 679–681
Arithmetic expression evaluation 128–131
Array 18–21
2-dimensional 19
aliasing 19
as object 72
bounds checking 19
memory usage of 202
of objects 72
ragged 19
Array resizing. See Resizing array
Articulation point 562
Assertion 107
assert statement 107
Assignment statement 14
Associative array 363
Augmenting path 891
AVL tree 452
B
Backtracking 921
Balanced search tree 424–457
2-3 search tree 424–431
AVL tree 452
B-tree 866–874
red-black BST 432–447
Base case 25
Bellman-Ford 671–678
Bellman, R. 683
BFS. See Breadth-first search
Biconnectivity 562
Big-Oh notation 206–207
Big-Omega notation 207
Big-Theta notation 207
Binary data 811–815
Binary dump 813–814
Binary heap 313–322
amortized analysis of 320
analysis of 319
change priority 321
defined 314
deletion 321
heapsort 323–327
insertion 317
remove the maximum 317
remove the minimum 321
representation 313
sink and swim 315–316
Binary logarithm function 185
Binary search 8
bitonic search 210
for a fraction 211
in a sorted array 46–47, 98–99
local minimum 210
symbol table 378–384
Binary search tree 396–423
analysis of 403
anatomy of 396
AVL tree 452
certification 419
defined 396
delete the min/max 408
floor and ceiling 406
height 412
insertion 400–401
minimum and maximum 406
nonrecursive 417
perfectly balanced 403
range query 412
rank and select 415
recursion 415
representation 397
rotation 433–434
search 397–401
symmetric order 396
threading 420
BinaryStdIn library 811–815
BinaryStdOut library 811–815
anatomy of 396
binary heap 313
decision tree 280
external path length 418
heap-ordered 313
height 314
inorder traversal 412
internal path length 412
level-order traversal 420
preorder traversal 834
weighted external path length 832
Binomial coefficient 185
Binomial tree 237
Birthday problem 215
Bitmap 822
Bitonic array 210
Bitonic search 210
Bitonic shortest paths 689
Blacklist filter 491
Boerner’s theorem 357
boolean primitive data type 12
Boolean satisfiability 913, 920
Boruvka, O. 628
Bottleneck shortest paths 690
Bottom-up 2-3-4 tree 451
Bottom-up mergesort 277
Boyer-Moore 770–773
Boyer, R. S. 759
in a digraph 573
in a graph 538–542
break statement 15
Bridge in a graph 562
analysis of 871
insertion 868
perfect balance 868
search 868
Buffer data type 170
Byte (8 bits) 200
byte primitive data type 13
C
Cache 195, 307, 327, 343, 394, 419, 423
Call a method 22
Callback 339. See also Interface
Carter, L. 462
Catenable queue 171
Ceiling function
binary search tree 406
mathematical function 185
ordered array 380
symbol table 367
Cell-probe model 234
Center of a graph 559
Certification
binary heap 330
binary search 392
binary search tree 419
minimum spanning tree 634
NP complexity class 912
red-black BST 452
search problem 912
shortest paths 651
char primitive data type 12, 696
Chebyshev’s inequality 303
Church-Turing thesis 910
Circular linked list 165
Circular queue 169
Circular rotation 114
Classpath 66
Client 28
Closest pair 210
Collections 120
bag 124–125
catenable 171
deque 167
generalized queue 169
priority queue 308–334
pushdown stack 127
queue 126
random bag 167
random queue 168
ring buffer 169
stack 127
steque 167
symbol table 360–513
trie 730–757.
Collision resolution 458
Command-line argument 36
Command-line interface
command-line argument 36
compile a Java program 10
piping 40
redirection 40
run a Java program 10
standard input 39
standard output 37–38
terminal window 36
Comma-separated-value 493
compareTo() method 246–247
Date 247
natural order 337
String 353
symbol table 368–369
Transaction 266
Comparator interface 338–340
compare() method 338–339
priority queue 340
Transaction 339
compare() method. See Comparator interface
compareTo() method. See Comparable interface
Compile a program 10
Complete binary tree 314
Complete graph 681
Compression. See Data compression
Computability 910
Computational complexity
Cook-Levin theorem 918
intractability 910–921
NP-complete 917–918
NP 912
P 914
P = NP question 916
poly-time reduction 916–917
sorting 279–282
Computational geometry 76
Concatenation of strings 34
Concordance 510
Conditional statement 15
Connected components
computing 543–546
defined 519
union-find 217
Connected graph 519
Connectivity
articulation point 562
biconnectivity 562
bridge 562
components 543–546
dynamic 216
edge-connected graph 562
strong connectivity 584–591
undirected graph 530
union-find 216–241
Constant running time 186
continue statement 15
Contract 33
Cook-Levin theorem 918
Cost model 182.
binary search 184
B-tree 866
compares 369
equality tests 369
searching 369
sorting 246
symbol table 369
3-sum 182
union-find 220
Coupon collector problem 215
Covariant arrays 158
CPM. See Critical-path method
C language 104
C++ language 104
Critical path 663
Crossing edge 606
Cubic running time 186
Cuckoo hashing 484
Cut 606. See also Mincut problem
capacity of 892
optimality conditions 634
property for MST 606
st-cut 892
Cycle
Hamiltonian 562
in a digraph 567
in a graph 519
odd length 562
Cycle detection 546–547
Cyclic rotation of a string 784
D
DAG. See Directed acyclic graph
Dangling else 52
Dantzig, G. 909
Data abstraction 64–119
Data compression 810–851
fixed-length code 819–821
Huffman 826–838
lossless 811
lossy 811
LZW algorithm 839–845
prefix-free code 826–827
run-length encoding 822–825
2-bit genomics code 819–821
undecidability 817
uniquely decodable code 826
universal 816
variable-length code 826
Data structure
adjacency lists 525
adjacency matrix 524
binary heap 313
binary search tree 396
binary tree 396
circular linked list 165
defined 4
doubly-linked list 146
linked list 142–146
multiway trie 732
ordered array 312
ordered list 312
parallel arrays 378
parent-link 225
resizing array 136
ternary search trie 746
unordered array 310
unordered list 312
Data type
abstract 64
design of 96–97
encapsulation 96
Date data type 78–79
compareTo() method 247
equals() method 103
implementation 91
toString() method 103
Decision problem 913
Decision tree 280
Declaration statement 14
Dedup 490
Defensive copy 112
Degree of a vertex 519
Degrees of separation 553–554
Denial-of-service attacks 197
Dense graph 520
Deprecated method 113
Depth-first search 530–534
bipartiteness 547
connected components 543
cycle detection 547
directed cycle 574–581
longest path 912
maze exploration 530
path finding 535–537
reachability 570–573
strong components 584–591
topological order 574–581
transitive closure 592
Tremaux exploration 530
2-colorability 547
union-find 546
Depth of a node 226
Design by contract 107
Deterministic finite state automaton 764
Devroye, L. 412
DFA. See Deterministic finite state automaton
Dictionary 361. See also Symbol table
Digraph. See Directed graph
Digraph data type 568–569
Dijkstra, E. 128, 298, 628, 682
Dijkstra’s 2-stack algorithm 128–131
Dijkstra’s algorithm 652–657
bidirectional search 690
negative weights 668
Directed acyclic graph 574–583
depth-first orders 578
edge-weighted 658–667
Hamiltonian path 598
lowest common ancestor 598
shortest ancestral path 598
topological order 575
topological sort 575
Directed cycle 567
Directed cycle detection 576
Directed edge 566
Directed graph 566–603. See also Edge-weighted digraph
acyclic 574–583
all-pairs reachability 590
anatomy of 567
breadth-first search 573
cycle 567
cycle detection 576
defined 566
directed paths 573
edge 566
Euler cycle 598
indegree and outdegree 566
Kosaraju’s algorithm 586–590
path 567
postorder traversal 578
preorder traversal 578
reachable vertex 567
reverse 568
reverse postorder 578
shortest ancestral path 598
shortest directed paths 573
simple 567
strong component 584
strong connectivity 584–591
strongly-connected 584
topological order 575–583
transitive closure 592
Directed path 567
Disjoint set union. See Union find
Divide-and-conquer paradigm
mergesort 270
Division by zero 51
Documentation 28
Double hashing 483
double primitive data type 12
Double probing 483
Doubling array. See Resizing array
Doubling ratio experiment 192
Doubling test 176–177
Doubly-linked list 146
Dump 813
3-way quicksort 301
hash table 488
in a symbol table 363
MSD string sort 715
priority queue 309
quicksort 292
sorting 344
stability 341
Dutch National Flag 298
Dynamic connectivity 216
Dynamic memory allocation 104
Dynamic programming 671
Dynamic resizing array. See Resizing array
E
Eccentricity of a vertex 559
Edge
backward 891
crossing 606
data type 608
eligible 646
forward 891
incident 519
parallel 518
self-loop 518
undirected 518
Edge-connected graph 562
Edge relaxation 646–647
Edge-weighted DAG 658–667
critical path method 663–667
longest paths 661
shortest paths 658–660
adjacency-lists 644
complete 679
data type 641
diameter of 685
shortest paths 638–693
adjacency-lists 609
data type 608
min spanning forest 605
min spanning tree 604–637
Edmonds, J. 901
Ellipsoid algorithm 909
Encapsulation 96
Entropy 300–301
Epsilon-transition 795
Equal keys. See Duplicate keys
equals() method 102–103
symbol table 365
Equivalence class 216
Equivalence relation
equals() method 102
strong connectivity 584
Erdös number 554
Erdös, P. 554
Erdös-Renyi model 239
Error. See also Exception
OutOfMemoryError 107
Event-driven simulation 349, 856–865
Exception. See also Error
Arithmetic 107
ArrayIndexOutOfBounds 107
ClassCast 387
NoSuchElement 139
NullPointer 159
Runtime 107
UnsupportedOperation 139
ConcurrentModification 160
Exhaustive search 912
Exponential inequality 185
Exponential running time 186, 661, 911
Extended Church-Turing thesis 910
Extensible library 101
F
Factor an integer 919
Factorial function 185
Fail-fast design 107
Farthest pair 210
Fibonacci numbers 57
FIFO. See First-in first-out policy
FIFO queue. See Queue data type
File system 493
Filter 60
blacklist 491
dedup 490
Final access modifier 105–106
Fingerprint search 774–778
Finite state automaton. See Deterministic finite state automaton
First-in-first-out policy 126
Fixed-capacity stack 132, 134–135
Fixed-length code 826
Float primitive data type 13
Flood fill 563
Floor function
binary search tree 406
mathematical function 185
ordered array 380
Flow 888. See also Maxflow problem
flow network 888
inflow and outflow 888
residual network 895
st-flow 888
st-flow network 888
value 888
Floyd, R. W. 326
Floyd’s method 327
for loop 16
Ford-Fulkerson 891–893
analysis of 900
maximum-capacity path 901
shortest augmenting path 897
Ford, L. 683
Foreach loop 138
arrays 160
strings 160
Forest
graph 520
spanning 520
Forest-of-trees 225
Formatted output 37
Fortran language 217
Fragile base class problem 112
Frazer, W. 306
Fredman, M. L. 628
G
loitering 137
mark-and-sweep 573
Gaussian elimination 919
and covariant arrays 158
and type erasure 158
parameterized type 122
priority queues 309
stacks and queues 134–135
symbol tables 363
Geometric data types 76–77
Geometric sum 185
Girth of a graph 559
Global variable 113
Gosper, R. W. 759
Graph data type 522–527
Graph processing 514–693. See also Directed graph; See also Edge-weighted digraph; See also Edge-weighted graph; See also Undirected graph; See also Directed acyclic graph
Bellman-Ford 668–681
breadth-first search 538–541
components 543–546
critical-path method 664–666
depth-first search 530–537
Dijkstra’s algorithm 652
Kosaraju’s algorithm 586–590
Kruskal’s algorithm 624–627
longest paths 911–912
max bipartite matching 906
min spanning tree 604–637
Prim’s algorithm 616–623
reachability 570–573
shortest paths 638–693
strong components 584–591
symbol graphs 548
transitive closure 592–593
union-find 216–241
Greatest common divisor 4
Greedy algorithm
Huffman encoding 830
minimum spanning tree 607
Grep 804
H
Halting problem 910
Hamiltonian path 598, 913, 920
Handle 112
Hard-disc model 856
Harmonic sum 185
hashCode() method 101, 102, 461–462
modular 459
perfect 480
Rabin-Karp algorithm 774
universal 463
Hashing. See Hash function; See also Hash table
hash function 459–463
time-space tradeoff 458
Hash table 458–485
array resizing 474–475
clustering 472
collision resolution 458
cuckoo hashing 484
deletion 468
double hashing 483
double probing 483
duplicate keys 488
hashCode() method 461–462
hash function 458
Java library 489
linear probing 469–474
load factor 471
memory usage of 476
primitive types 488
separate chaining 464–468
uniform hashing assumption 463
Head vertex 566
Heap. See Binary heap
multiway 319
Heap order 313
Heapsort 323–327
Height
2-3 search tree 429
binary search tree 412
complete binary tree 314
red-black BST 444
tree 226
Hibbard deletion 422
Hibbard, T. 410
Hoare, C. A. R. 205
Horner’s method 460
h-sorted array 258
Huffman compression 350, 826–838
analysis of 833
optimality of 833
Huffman, D. 827
I
if statement 15
if-else statement 15
Immutability 105–106
defensive copy 112
priority queue keys 320
symbol table keys 365
Implementation inheritance 101
Incident edge 519
Increment sequence 258
Indegree of a vertex 566
a string 877
files 500–501
inverted 498–501
Index priority queue 320–322
Dijkstra’s algorithm 652
Prim’s algorithm 620
Indirect sort 286
Ineligible edge
minimum spanning tree 616
shortest paths 646
compare() 338–339
compareTo() 246–247
equals() 102–103
getClass() 101
hasNext() 138
iterator() 138
next() 138
Inorder tree traversal 412
In-place merge 270
Input and output 82–83
binary data 812–815
from a file 41
piping 40
redirection 40
Input model 197
Input size 173
Insertion sort 250–252
Instance variable 84
int primitive data type 12
Integer linear inequality satisfiability problem 913
Integer linear programming 920
Integer overflow 51
Interface 100
Comparable 246–247
Comparator 338–340
Iterable 138
Iterator 139
Interface inheritance 100
Interior point method 909
Internal path length 412
Internet DNS 493
Internet Movie Database 497
Interpreter 130
Interval graph 564
Intractability 910–921
Inverted index 498–501
Ising model 920
Isomorphic graph 561
Item
contains a key 244
sorting 244
symbol table 387
with multiple keys 339
Item type parameter 134
fail-fast 171
foreach loop 123
J
Jacquet, P. 882
Jarnik’s algorithm 628. See also Prim’s algorithm
Jarnik, V. 628
Java programming
array 18–21
arrays as objects 72
arrays of objects 72
assertion 107
assert statement 107
assignment statement 14
autoboxing 122
autounboxing 122
base class 101
bitwise operators 52
block statement 15
boolean expression 13
break statement 15
bytecode 10
cast 13
classpath 66
comparison operator 13
conditional statement 15
continue statement 15
covariant arrays 158
create an object 67
declaration statement 14
deprecated method 113
derived class 101
Error 107
Exception 107
for loop 16
foreach loop 123
garbage collection 104
generic array creation 158
identifier 11
if statement 15
if-else statement 15
implicit assignment 16
import statement 29
imported system libraries 27
infix expression 13
inheritance 100–101
inherited method 66
initializing declarations 16
inner class 159
instance method signature 86
instance variable 84
invoke instance method 68
iterable collections 123
just-in-time compiler 195
literal 11
loitering 137
loop statement 15
memory management 104
modular programming 26
nested class 159
new() 67
objects 67–74
objects as arguments 71
objects as return values 71
operator 11
operator precedence 13
orphan 137
orphaned object 104
override a method 101
pass by reference 71
primitive data type 11–12
private class 159
private modifier 84
protected modifier 110
ragged array 19
recursion 25
reference 67
reference type 64
return statement 86
short-circuit operator 52
side effects 24
single-statement blocks 16
standard libraries 27
standard system libraries 27
statement 14
static method 22–25
static variable 113
strong typing 14
subclass 101
superclass 101
this reference 87
throw an error/exception 107
two-dimensional array 19
type erasure 158
type parameter 122
unit testing 26
using objects 69
variable 11
visibility modifier 84
while loop 15
wrapper type 122
Java system sort 306
Java virtual machine 51
java.awt
Color 75
Font 75
java.io
File 75
java.lang
ArithmeticException 107
ArrayIndexOutOfBounds 107
Boolean 102
Byte 102
Character 102
ClassCastException 387
Comparable 100
Float 102
Integer 102
Long 102
Math 28
Object 101
OutOfMemoryError 107
RuntimeException 107
Short 102
UnsupportedOperation 139
URL 75
java.util
ArrayList 160
Arrays 29
ConcurrentModification 160
Date 113
HashMap 489
LinkedList 160
NoSuchElementException 139
PriorityQueue 352
Stack 159
TreeMap 489
Job-scheduling problem. See Scheduling
Josephus problem 168
Just-in-time compiler 195
K
Kendall tau distance 286, 345, 356
Kevin Bacon number 553–554
Key 244
Key equality
ordered symbol table 368
symbol table 365
Key-indexed counting 703–705
Key type parameter
priority queue 309
symbol table 361
Keyword in context 879
Khachian, L. G. 909
Kleene’s theorem 794
Knuth-Morris-Pratt 762–769
Knuth shuffle 32
Kosaraju’s algorithm 586–590
Kruskal, J. 628
Kruskal’s algorithm 624–627
L
Last-in-first-out policy 127
Las Vegas algorithm 778
Leading-term approximation. See Tilde notation
Least-significant digit. See LSD string sort
Leipzig Corpora Collection 371
Lempel, A. 839
Level-order traversal
binary heap 313
binary search tree 420
Levin, L. 918
LIFO. See Last-in first-out policy
LIFO stack. See Stack data type
Linear equation satisfiability 913
Linear inequality satisfiability 913
Linear probing 469–474
Linear programming 907–909
ellipsoid algorithm 909
interior point method 909
reductions 907–909
simplex algorithm 909
Linear running time 186
Linearithmic running time 186
Linked allocation 156
Linked list 142–146
building 143
circular 165
defined 142
deletion 145
deletion from beginning 145
garbage collection 145
insertion 145
insertion at beginning 144
insertion at end 145
iterator 154–155
memory usage of 201
Node data type 142
queue 150
reverse a 165
sequential search 374
shuffle a 286
sort a 286
stack 147–149
traversal 146
Literal
null 112–113
primitive type 11
string 80
Load factor 471
Local minimum 210
Logarithm function
binary 185
integer binary 185
natural 185
Logarithmic running time 186
Log-log plot 176
Loitering 137
Longest common prefix 875
Longest prefix match 842
Longest-processing-time first rule 349
Longest repeated substring 875
long primitive data type 13
Loop
for 16
foreach 138
inner 180
while 15
Lossless data compression 811
Lossy data compression 811
Lower bound
priority queue 332
sorting 279–282
3-sum problem 190
union-find 231
Lowest common ancestor 598
Loyd, S. 358
LSD string sort 706–709
LZW algorithm 839–845
compression 840
expansion 841
trie representation 840
M
Manber, U. 884
Mark-and-sweep garbage collection 573
Maslow, A. 904
Maslow’s hammer 904
Matrix data type 60
Maxflow-mincut theorem 894
Maxflow problem 886–902. See also Mincut problem
Ford-Fulkerson 891–893
integrality property 894
maxflow-mincut theorem 892–894
max bipartite matching 906
preflow-push algorithm 902
reductions 905–907
residual network 895–897
Maximum
in array 30
in binary heap 313
in binary search tree 406
in ordered symbol table 367
Maximum st-flow problem. See Maxflow problem
Max bipartite matching 906
Maze 530
McKellar, A. 306
Median-of-3 partitioning 305
Memory management 104
linked allocation 156
loitering 137
orphan 137
Sequential allocation 156
Memory usage 200–204
array 202
hash table 476
linked list 201
nested class 201
primitive types 200
R-way trie 744
stack 213
string 202
substring 202–204
Mergesort 270–288
abstract in-place merge 270
analysis of 272
bottom-up 277
multiway 287
natural 285
optimality 282
stability 341
top-down 272
Merging 270–271
Method
inherited 100–101
static 22–25
Mincut problem 893. See also Maxflow problem
Minimum
in array 30
in binary search tree 406
in ordered symbol table 367
Min spanning forest 605
Min spanning tree 604–637
Boruvka’s algorithm 636
bottleneck shortest paths 690
critical edge 633
crossing edge 606
cut 606
cut optimality conditions 634
cut property 606
defined 604
greedy algorithm 607
Kruskal’s algorithm 624–627
Prim’s algorithm 616–623
reverse-delete algorithm 633
Vyssotsky’s algorithm 633
Minimum st-cut problem. See Mincut problem
Minotaur 530
Mismatched character rule 770
M. L. Fredman 628
Modular hash function 459, 774
Modular programming 26
Monte Carlo algorithm 776
Moore, J. S. 759
Moore’s law 194–195
Morris, J. H. 759
Most-significant-digit sort. See MSD string sort
Move-to-front 169
MSD string sort 710–718
Multidimensional sort 356
Multigraph 518
Multiple-source reachability problem 570, 797
Multiset 509
Multiway mergesort 287
Multiway trie. See R-way trie
Myers, E. 884
N
Natural logarithm function 185
Natural mergesort 285
Natural order 337
Negative cycle 668–670, 677–681
Nested class 159
Network flow. See Maxflow problem Mincut problem
new() 67
Newton’s method 23
NFA. See Nondeterministic finite-state automata
Node data type 159
bag 155
binary search tree 398
Huffman trie 828
linked list 142
queue 151
red-black BST 433
R-way trie 734
stack 149
ternary search trie 747
Nondeterminism 794
Turing machine 914
Nondeterministic finite-state automata 794–799
NP 912
NP-complete 917–918
Null link 396
null literal 112–113
O
Object 67–74. See also Object-oriented programming
memory usage of 201
Object-oriented programming 64–119
arrays of objects 72
creating an object 67
declaring an object 67
encapsulation 96
inheritance 100
instance 73
instantiate an object 67
invoke instance method 68
objects 67–74
objects as arguments 71
objects as return values 71
reference 67
subtyping 100
using objects 69
Odd-length cycle in a graph 562
OOP. See Object-oriented programming
Operations research 349
Optimization problem 913
Ordered symbol table 366–369
floor and ceiling 367
minimum and maximum 367
ordered array 378
range query 368
rank and selection 367
red-black BST 446
Order of growth 179
Order-of-growth classifications 186–188
Order-of-growth hypothesis 180
Order statistic 345
binary search tree 406
ordered symbol table 367
quickselect 345–347
Outdegree of a vertex 566
Output. See Input and output
Overflow 51
Overloading
constructor 84
static method 24
P
P complexity class 914
P = NP question 916
Page data type 870
Parallel arrays
linear probing 471
ordered symbol table 378
sorting 357
Parallel edge 518, 566, 612, 640
Parallel job scheduling 663–667
Parallel precedence-constrained scheduling 663, 904
Parameterized type. See Generics
Parent-link representation
breadth-first search tree 539
depth-first search tree 535
minimum spanning tree 620
shortest-paths tree 640
union-find 225
Parsing
an arithmetic expression 128
a regular expression 800–804
Particle data type 860
Partitioning algorithm 290
2-way 288
3-way (Bentley-McIlroy) 306
3-way (Dijkstra) 298
median-of-5 305
selection 346–347
Partitioning item 290
Pass by reference 71
Path. See Longest paths; See also Shortest paths
augmenting 891
in a digraph 567
in a graph 519
Path compression 231
Pattern matching. See Regular expression
Perfect hash function 480
Performance. See Propositions
Permutation
Kendall-tau distance 356
random 168
ranking 345
sorting 354
Phone book 492
Picture data type 814
Piping 40
Point data type 77
Pointer 111. See also Reference
safe 112
Pointer sort 338
Poisson approximation 466
Poisson distribution 466
Polar angle 356
Polar coordinate 77
Polar sort 356
Poly-time reduction 916
Pop operation 127
Postfix notation 162
Postorder traversal
of a digraph 578
reverse 578
Power law 178
Pratt, V. R. 759
Precedence-constrainted scheduling 574–575
Precedence order
arithmetic expressions 13
regular expressions 789
Prefix-free code 826–827
compression 829
expansion 828
Huffman 833
optimal 833
reading and writing 834–835
trie representation 827
Preorder traversal
of a digraph 578
of a trie 834
Primitive data type 11–12
memory usage of 200
reason for 51
wrapper type 102
Primitive type
versus reference type 110
Prim, R. 628
eager 620–623
lazy 616–619
Priority queue 308–335
binary heap 313–322
change priority 321
delete 321
Dijkstra’s algorithm 652
Fibonacci heap 628
Huffman compression 830
index priority queue 320–321
linked-list 312
multiway heap 319
ordered array 312
Prim’s algorithm 616
reductions 345
remove the minimum 321
soft heap 629
stability 356
unordered array 310
private access modifier 84
Probabilistic algorithm. See Randomized algorithm
Probe 471
Problem size 173
Programs
Accumulator 93
AcyclicLP 661
AcyclicSP 660
Arbitrage 680
Average 39
Bag 155
BellmanFordSP 674
BinaryDump 814
BinarySearch 47
BlackFilter 491
BoyerMoore 772
BreadthFirstPaths 540
BTreeSET 872
Cat 82
CC 544
CollisionSystem 863–864
Count 699
Counter 89
CPM 665
Cycle 547
DeDup 490
DegreesOfSeparation 555
DepthFirstOrder 580
DepthFirstPaths 536
DepthFirstSearch 531
Digraph 569
DijkstraAllPairsSP 656
DijkstraSP 655
DirectedCycle 577
DirectedDFS 571
DirectedEdge 642
DoublingTest 177
Edge 610
EdgeWeightedDigraph 643
EdgeWeightedGraph 611
Evaluate 129
Event 861
Example 245
FileIndex 501
FixedCapacityStack 135
FixedCapacityStackOfStrings 133
Flips 70
FlipsMax 71
FlowEdge 896
FordFulkerson 898
FrequencyCounter 372
Genome 819–820
Graph 526
GREP 804
Heap 324
HexDump 814
Huffman 836
Insertion 251
KMP 768
KosarajuSharirSCC 587
KruskalMST 627
KWIC 881
LazyPrimMST 619
LinearProbingHashST 470
LookupCSV 495
LookupIndex 499
LRS 880
LSD 707
MaxPQ 318
MergeBU 278
MSD 712
Multiway 322
PictureDump 814
PrimMST 622
Queue 151
Quick3string 720
Quick3way 299
RabinKarp 777
RedBlackBST 439
ResizingArrayQueue 140
ResizingArrayStack 141
Reverse 127
RLE 824
Rolls 72
Selection 249
SeparateChainingHashST 465
SequentialSearchST 375
SET 489
Shell 259
SortCompare 256
SparseVector 503
Stack 149
StaticSETofInts 99
Stats 125
Stopwatch 175
SuffixArray 883
SymbolGraph 552
ThreeSum 173
ThreeSumFast 190
TopM 311
Topological 581
Transaction 340
TransitiveClosure 593
TrieST 737–741
TST 747
TwoColor 547
TwoSumFast 189
UF 221
VisualAccumulator 95
WeightedQuickUnionUF 228
WhiteFilter 491
Whitelist 99
Properties 180
3-sum 180
Boyer-Moore algorithm 773
insertion sort 255
quicksort 343
Rabin-Karp algorithm 778
red-black BST 445
selection sort 255
separate-chaining 467
shellsort 262
versus proposition 183
Propositions 182
2-3 search tree 429
3-sum 182
3-way quicksort 301
3-way string quicksort 723
arbitrage 681
B-tree 871
binary heap 319
binary search 383
breadth-first search 541
brute substring search 761
complete binary tree 314
connected components 546
Cook-Levin theorem 918
critical path method 666
cut property 606
flow conservation 893
Ford-Fulkerson 900–901
generic shortest-paths 651
greedy MST algorithm 607
Huffman algorithm 833
index priority queue 321
integer programming 917
key-indexed counting 705
Knuth-Morris-Pratt 769
linear-probing hash table 475
linear programming 908
longest paths in DAG 661
longest repeated substring 885
maxflow-mincut theorem 894
maxflow reductions 906
negative cycles 669
parallel job scheduling with relative deadlines 667
particle collision 865
Prim’s algorithm 616, 618, 623
quick-find algorithm 223
quickselect 347
quicksort 293–295
quick-union algorithm 226
resizing-array stack 199
selection sort 248
sequential search 376
shortest paths in DAG 658
shortest-paths optimality 650
shortest paths reductions 905
sorting reductions 903
suffix array 882
universal compression 816
weighted quick-union 229
protected modifier 110
Protein folding 920
public access modifier 110
Pushdown stack 127. See also Stack data type
Push operation 127
Q
Quadratic running time 186
Quantum computer 911
analysis of 198
API 126
circular linked list 165
linked-list 150–151
resizing-array 140
Quick-find algorithm 222–223
Quickselect 345–347
Quicksort 288–307
2-way partitioning 290
3-way partitioning 298–301
3-way string 719
analysis of 293–295
and binary search trees 403
duplicate keys 292
function-call stack size 304
median-of-5 305
nonrecursive 306
random shuffle 292
Quick-union 224–227
path compression 231
weighted 227–230
R
Rabin-Karp algorithm 774–778
Rabin, M. O. 759
Radius of a graph 559
Radix 700
Radix sorting. See String sorting
Random bag data type 167
Randomized algorithm 198
Las Vegas 778
Monte Carlo 776
quickselect 345–347
Rabin-Karp algorithm 776
3-way string quicksort 722
Random number 30–32
Random queue data type 168
Random string model 716–717
Range query
binary search tree 412
ordered symbol table 368
Rank
ordered symbol table 367
suffix array 879
Reachable vertex 567
Recurrence relation
binary search 383
mergesort 272
quicksort 293
Recursion 25. See also Base case; See also Recursion
binary search tree 401
depth-first search 531
Euclid’s algorithm 4
Fibonacci numbers 57
mergesort 272
quicksort 289
Red-black BST 432–447
and 2-3 search tree 432
analysis of 444–447
color flip 436
color representation 433
defined 432
delete the maximum 454
delete the minimum 453
implementation 439
insertion 437–439
left-leaning 432
perfect black balance 432
rotation 433–434
search 432
Redirection 40
Reduction 903–909
defined 903
polynomial-time 916
linear programming 907–909
maxflow 905–907
priority queue 345
shortest-paths 904–905
Reference 67
Reference type 64
Reflexive relation 102, 216, 247, 584
building an NFA 800–804
closure operation 789
concatenation operation 789
defined 790
epsilon-transition 795
match transition 795
nondeterministic finite-state automaton 794–799
or operation 789
parentheses 789
\s+ 82
shortcuts 791
simulating an NFA 797–799
Rehashing 474
Relation
antisymmetric 247
total order 247
Residual network 895–897
Resizing array 136–137
binary heap 320
hash table 474–475
queue 140
stack 136
Return value 22
Reverese postorder traversal 578
Reverse
a linked list 165–166
an array 21
array iterator 139
with a stack 127
Reverse-delete algorithm 633
Reverse graph 586
Reverse Polish notation. See Postfix notation
Reverse postorder 578
Ring buffer data type 169
RLE. See Run-length encoding
Robson, J. 412
Rooted tree 640
Rotation in a BST 433–434, 452
Run-length encoding 822–825
Running time 172–173
analysis of 176
constant 186
cubic 186
doubling ratio 192
exponential 186
inner loop 180
linear 186
logarithmic 186
measuring 174
order of growth 179
quadratic 186
tilde approximation 178–179
Run-time error. See Error; See also Exception
R-way trie 730–744
Alphabet 741
analysis of 742–743
collecting keys 738
deletion 740
insertion 734
longest prefix 739
memory usage of 744
one-way branching 744–745,
representation 734
search 732–733
wildcard match 739
S
Safe pointer 112
Sample mean 30
Samplesort 306
Sample standard deviation 30
Sample variance 30
critical-path method 664–666
load-balancing problem 349
LPT first 349
parallel precedence-constrained 663–667
precedence constraint 574–575
relative deadlines 666
SPT first 349
Scientific method 172
Search hit 376
Searching 360–513. See also Symbol table
Search miss 376
Search problem 912
Sedgewick, R. 298
Selection 345
binary search tree 406
ordered symbol table 367
quickselect 346–347
suffix array 879
Selection client 249
Selection sort 248–249
Separate-chaining 464–468
Sequential allocation 156
Sequential search 374–377
Set data type 489–491
Shannon entropy 300–301
Shellsort 258–262
Shortest ancestral path 598
Shortest augmenting path 897
Shortest path 638
Shortest paths problem 638–693
all-pairs 656
arbitrage detection 679–681
Bellman-Ford 668–678
bitonic 689
bottleneck 690
certification 651
critical edge 690
Dijkstra’s algorithm 652–657
edge relaxation 646–647
edge-weighted DAG 658–667
generic algorithm 651
ineligible edge 646
in Euclidean graphs 656
monotonic 689
negative cycle 669
Negative cycle detection 670
negative weights 668–681
optimality conditions 650
parent-link 640
reduction 904–905
shortest-paths tree 640
source-sink 656
undirected graph 654
vertex relaxation 648
Shortest-processing-time-first rule 349, 355
short primitive data type 13
Shuffling
a linked list 286
an array 32
quicksort 292
Signature
instance method 86
static method 22
Simple digraph 567
Simple graph 518
Simplex algorithm 909
Single-source problems
connectivity 556
directed paths 573
longest paths in DAG 661
paths 534
reachability 570
shortest directed paths 573
shortest paths in undirected graphs 654, 904
Social network 517
Soft heap 629
Sollin, M. 628
Sorting 242–359. See also String sorting
3-way quicksort 298–301
binary search tree 412
Comparable 246–247
compare-based 279
complexity of 279–282
cost model 246
entropy-optimal 296–301
extra memory 246
heapsort 323–327
indirect 286
in-place 246
insertion sort 250–252
inversion 252
mergesort 270–288
partially-sorted array 252
pointer 338
primitive types 343
quicksort 288–307
reduction 903–904
reductions 344–347
selection sort 248–250
shellsort 258–262
stability 341
suffix array 875–885
system sort 343
Source-sink shortest paths 656
Spanning forest 520
Sparse graph 520
Sparse matrix 510
Sparse vector 502–505
Specification problem 97
SPT. See Shortest paths tree; See also Shortest-processing-time-first rule
st-cut 892
st-flow 888
st-flow network 888
insertion sort 341
key-indexed counting 705
LSD string sort 706
mergesort 341
priority queue 356
Stack data type 127
array implementation 132
fixed-capacity 132–133
generic 134
iteration 138–140
linked-list 147–149
resizing array 136
Standard deviation 30
Standard libraries 30
Draw 82–83
StdDraw 43
StdIn 39
StdOut 37
StdRandom 30
StdStats 30
Stopwatch 174–175
Static method 22–25
argument 22
defining a 22
invoking a 22
overloaded 24
pass by value 24
recursive 25
return statement 24
return value 22
signature 22
Static variable 113
Statistics
chi-square 483
median 345
minimum and maximum 30
order 345
sample standard deviation 30
StdDraw library 43
StdIn library 39
StdOut library 37
StdRandom library 30
StdStats library 30
Stirling’s approximation 185
Stopwatch data type 174–175
API 80
characters 696
charAt() method 696
conversion 102
immutability 696
indexing 696
indexOf() method 779
length 696
length() method 696
literal 34
String processing 80–81, 694–851
data compression 810–851
regular expression 788
sorting 702–729
substring search 758–785
suffix array 875–885
tries 730–757
String search. See Substring search; See also Trie
String sorting 702–729
3-way quicksort 719–723
key-indexed counting 703
LSD string sort 706–709
MSD string sort 710–718
Strong component 584
Strong connectivity 584–591
Strongly connected component. See Strong component
Strongly connected relation 584
Strongly typed language 14
Subclass 101
Subgraph 519
Sublinear running time 716, 779
Substring extraction
memory usage of 202–204
substring() method 696
Substring search 758–785
Boyer-Moore 770–773
brute-force 760–761
indexOf() method 779
Knuth-Morris-Pratt 762–769
Rabin-Karp 774–778
Subtyping 100
Suffix array 875–885
Suffix array data type 879
Suffix-free code 847
Superclass 101
Symbol digraph 581
Symbol graph 548–555
Symbol table 360–513
2-3 search tree 424–431
associative array 363
balanced search tree 424–457
binary search 378–384
binary search tree 396–423
B-tree 866–874
cost model 369
defined 362
duplicate key policy 363
floor and ceiling 367
hash table 458–485
insertion 362
key equality 365
lazy deletion 364
linear-probing 469–474
minimum and maximum 367
null value 364
ordered 366–369
ordered array 378
range query 368
rank and selection 367
red-black BST 432–447
R-way trie 732–745
search 362
separate-chaining 464–468
sequential search 374
string keys 730–757
ternary search trie 746–751
trie 730–757
unordered linked list 374
Symmetric order 396
Symmetric relation 102, 216, 584
Szpankowski, W. 882
T
Tail vertex 566
Tale of Two Cities 371
Tandem repeat 784
Ternary search trie 746–751
alphabet 750
analysis of 749
collecting keys 750
deletion 750
insertion 746
prefix match 750
search 746
wildcard match 750
Theseus 530
this reference 87
Threading 420
Time-driven simulation 856
Timing a program 174–175
Top-down 2-3-4 tree 441
Top-down mergesort 272
Topological sort 574–583
depth-first search 578
queue-based algorithm 599
Total order 247
Transaction data type 78–79
compare() 340
hashCode() 462
Transitive closure 592–593
Transitive relation 102, 216, 247, 584
Transpose a matrix 56
Tree.
2-3 search tree. See 2-3 search tree
binary. See Binary tree
binary search tree. See Binary search tree
balanced search tree. See Balanced search tree
binomial 237
depth of a node 226
height of 226
inorder traversal 412
min spanning tree. See Minimum spanning tree
preorder traversal 834
rooted 640
size 226
spanning tree. See Spanning tree
undirected graph 520
union-find 224–226
Tremaux exploration 530
Triangular sum 185
Trie 730–757. See also R-way trie; See also Ternary search trie
collecting keys 731
Lempel-Ziv-Welch 840
one-way branching 744–745, 751, 755
prefix-free code 827
preorder traversal 834
reading and writing 834–835
wildcard match 731
Tufte plot 456
Tukey ninther 306
Turing, A. 910
Turing machine 910
Church-Turing thesis 910
computability 910
nondeterministic 914
universality 910
Type conversion 13
Type erasure 158
U
acyclic 520
adjacency-lists 524
adjacency-matrix 524
adjacency-sets 527
adjacent vertex 519
articulation point 562
biconnected 562
breadth-first search 538–542
bridge 562
center 559
connected 519
connected component 519
connected to relation 519
cycle 519
cycle detection 546–547
defined 518
degree 519
dense 520
depth-first search 530–533
diameter 559
edge 518
edge-connected 562
edge-weighted. See Edge-weighted graph
Eulerian cycle 562
forest 520
girth 559
Hamiltonian cycle 562
interval graph 564
isomorphism 561
multigraph 518
odd cycle detection 562
parallel edge 518
path 519
radius 559
self-loop 518
simple 518
simple path 519
single-source connectivity 556
single-source paths 534
single-source shortest paths 538
spanning forest 520
spanning tree 520
sparse 520
subgraph 519
tree 520
vertex 518
weighted. See Edge-weighted graph
Unicode 696
Uniform hashing 463
Union-find 216–241
and depth-first search 546
binomial tree 237
Boruvka’s algorithm 636
dynamic connectivity 216
forest-of-trees 225
Kruskal’s algorithm 625
parent-link 225
quick-find 222–223
quick-union 224–227
weighted quick-find 236
weighted quick-union 227–231
weighted quick-union by height 237
weighted quick-union with path compression 237
Uniquely decodable code 826
Unit testing 26
Universal data compression 816
Universal hash function 463
Universality 910
V
Value type parameter
symbol table 361
trie 730
Variable 10
Variable-length code 826
Variance 30
Vector data type 106
Vertex
adjacent 519
connected to relation 519
degree of 519
eccentricity 559
head and tail 566
indegree and outdegree 566
reachable 567
source 528
Vertex cover problem 920
Vertex relaxation 648
Virtual terminal 10
Vyssotsky’s algorithm 633
W
Web search 496
Wegman, M. 463
Weighted digraph. See Edge-weighted digraph
Weighted external path length 832
Weighted graph. See Edge-weighted graph
Weighted quick-union 227–231
Weighted quick-union with path compression 237
Weiner, P. 884
Welch, T. 839
while loop 15
Whitelist filter 8, 48–49, 99, 491
Wildcard character 791
Wildcard match 750
Worst-case guarantee 197
Z
Ziv, J. 839
Zero-based indexing 53
Zipf’s law 393