A
versus fully defined class and interface, 139–140
Abstract data type, 31
Abstract method, 29
abstract modifier, 138
Abstraction,
Accessor method, 57
Active method, 208
Acyclic graph, 646, 648, 667, 669, 693–694
Adjacent vertices, 644
Aggregation, 51
Algorithm, 105
minimum spanning tree, 659–663
Alternate implementation(s)
of the BinarySearchTree class, 449–451
of the HashMap class, 626–635, 640
of the LinkedList class, 294–295, 323
A-maze-ing application, 195–208
Application Programming Interface (API), 6
Applications
backtracking through a maze, 195–208
backtracking through a network, 686–689, 695–697
converting from infix to postfix, 338–343
creating a symbol table, 617–625
high-precision arithmetic, 251–257
how compilers implement recursion, 334–337
Approval voting (project), 545–547
Argument, 19
fields in, 248
versus LinkedList class, 150, 282–285
ArrayList objects,
Arrays class
assertEquals, 62
Association, 51
Attribute in Unified Modeling Language, 49
Automatic garbage collection, 93
averageSpace(n), 106
averageTime(«), 106
important assumption for, 106
fixAfterDeletion method (project), 451–454
fixAfterInsertion method (project), 455
B
a-maze-ing application, 195–198
Eight Queens (project), 221–222
Knight's Tour (project), 222–224
through a network, 686–689, 695–697
Balanced binary search tree, 430–435
Base of a logarithm, 707
Base case, 709
Big-Omega notation, 116
Biglnteger class, 251
Binary search, 112–113, 180–185
Binary search tree, 402
chain, 384
decision tree, 468
definition, 377
external path length, 385
full, 381
Huffman tree, 576
two-tree, 381
Binary Tree Theorem, 383
BinarySearchTree class, 403–427
alternative implementation, 449–450
embedded TreeIterator class, 427–430
fields, 411
method specifications, 407–408
TreeIterator embedded class, 427–430
BinarySearchTreeTest class, 410–411
Binding
dynamic, 49
late, 49
Bit-wise operators,
^ (exclusive or), 608
<< (left shift), 382
>> (right shift, 112
>>> (unsigned right shift), 608
Bottom-up testing, 91
Boundary condition, 66
Boxing, 141
Branch, 378
Breadth-first iterator, 651–654, 683
break statement, 73
Bytecode, 92
C
CalendarDate (project), 58
Car wash (application), 351–365
randomizing the arrival times, 362–365
CarWashTest class, 355
UML diagram, 357
with finally block, 81
chain in a binary tree, 384
Circularity in LinkedList class, 298
Circularity in SinglyLinkedList class (project), 322
Arrays, 112–113, 180, 470–475, 477–489
BigInteger, 251
CalendarDate, 58
CarWashTest, 355
contiguous, 133
DecimalToBinaryTest, 163
embedded, 269
in BinarySearchTree class, 412
in HashMap class, 610
in Huffman class, 580
in LinkedList class, 295
in SinglyLinkedList class, 268–269
in TreeMap class, 513
Field, 1
HuffmanTest, 582
HuffmanUserTest, 587
Immutable, 20
implementing an interface, 32–34
instance variables, 59
NetworkTest, 677
Nothing, 19
SalariedEmployee, 46
SinglyLinkedListIterator, 276–279
SpellCheckerTest, 533
TreeSet, 525-530
VeryLongIntTest, 253
VeryLongIntUser, 257
VeryLongIntUserTest, 257
Class variable, 60
close() method in PrintWriter class, 82, 85
Clustering in open-address hashing
Co-domain (of a function), 705
Collision, 606
Collision handling
with open-address hashing, 626–634
Comparable interface, 179
Compiler: implementing recursion, 334–338
Concordance (project), 543–545
Conditional operator (?:), 300
Connectedness, 646–647, 658–659
Constant (independent of n), 111, 117
Constant identifier, 60
inheritance and, 43
Contiguous-collection class, 136, 234–251, 329–332, 552–566
Conversion formulas, 135
Converting from infix notation,
Copy
Correctness, 61
Covariant subtyping, 237
Critical activity, 668
Critical path, 668
Current line (in line editor), 300
D
Data abstraction, 27
Data structure, 31
Dead end, in backtracking, 191
Decimal to binary (application), 162–167
Decoding a Huffman-encoded message (project), 595–597
Default visibility, 93
versus visibility modifiers, 93–94, 100
Depth of an element, 381
Dequeue, 347
Deserialize, 702
Design pattern, 147
divide-and-conquer, 476–477, 484
greedy, 578, 663, 664, 686, 692–693
iterator, 147
Dictionary, 505
Dijkstra's Algorithm, 663–667, 683–686
Directed graph (digraph), 647–648
Directed weighted graph, 649
uniform, 122
Divide-and-conquer algorithms, 476–477, 484
Domain (of a function), 705
Double hashing, 632–635, 638, 640
Dummy entry, 295
Dynamic binding, 49
E
Earliest time for an event, 668
Edge, 643
EditorUserTest class, 313
Efficiency of methods (estimating), 105–119
Eight Queens (project), 221–222
Embedded class, 269
Encapsulation, 48
Encoding, 573
Enhanced for statement, 145–147
Enqueue, 347
Entry class
in BinarySearchTree class, 412
in HashMap class, 610
in Huffman class, 580
in LinkedList class, 295
in SinglyLinkedList class, 268–269
in TreeMap class, 513
reason for static modifier, 296
Entry interface, 610
Equality
untestability of double values for, 66–67
Error
in JUnit, 76
Evaluation of a condition (project), 371–374
Event-driven simulation, 354
Exponential-time method, 119
extends, 38
External path length, 385
External Path Length Theorem, 385–386
F
Failure
in JUnit, 76
Fairness in priority queue, 557, 566
Fast sorts
Feedback, 350
Fibonacci numbers, 167
Fibonacci tree, 437
Field(s), 1
in the ArrayList class, 248
in the BinarySearchTree class, 411
in the Hasher class, 621
in the LinkedList class, 295
in the SinglyLinkedList class, 273
in the SpellCheck class, 533
in the Thesaurus class, 520
in the TreeMap class, 512
in the VeryLongInt class, 254
pre-initialization of, 92
File
final modifier, 60
finally block, 81
Finite sequence, 706
First-in, first-out (FIFO)
in a queue, 347
fixAfterDeletion method
in AVLTree class (project), 455
in TreeMap class (lab), 517
fixAfterInsertion method
in AVLTree class (project), 451–454
in TreeMap class (lab), 515
Full binary tree, 381
Function, 705
and map, 705
G
Garbage, 92
automatic collection of, 92–93
Generating
a minimum spanning tree, 659–663
permutations
lab experiment, 191
pseudorandom values, 122
Graph
acyclic, 646, 648, 667, 669, 693–694
edge, 643
neighbor, 644
path, 644
undirected, 643
vertex, 643
weighted, 649
Graph algorithms
breadth-first traversal, 651–654
depth-first traversal, 654–658
minimum spanning tree, 659–663
Greedy algorithm, 578
Dijkstra's algorithm, 663–667, 683–686
H
Has-a, 47
Hash classes
Hashing, 606
Uniform Hashing Assumption, 609
views (entrySet(), keyset(), values()), 616
Heading
of the ArrayList class, 246
of the BinarySearchTree class, 406
of the HashMap class, 603
of the LinkedList class, 295
of the Network class, 670
Height
of a binary search tree, 434–436
of a binary tree, 339, 447–448 of a red-black tree, 503–504
Hexadecimal notation (exercise), 25
High-precision arithmetic (application), 251–257
HourlyCompany class, 44
HourlyEmployeeTest class, 66–67
Huffman
Huffman encoding, 574
Huffman tree, 574
HuffmanTest class, 582
HuffmanUserTest class, 587
I
Identifier, 617
Imbalance ancestor, 439
Immutable, 20
Immutable class, 20
import directive, 12
Index-related method, 147
Induction and recursion, 719
Infinite recursion, 177
Infix notation, 338
converting to postfix, 338–343
Information hiding, 48
and constructors, 43
multiple inheritance (not allowed), 139
Instance variables, 59
instanceof operator, 96
Integrated Web Browser and Search Engine (project),
LinkedList, 328
Interface
Application Programming Interface, 6
Comparable interface, 179
List interface, 147
ListIterator interface, 285–287
Queue interface, 348
Set interface, 403
SortedMap interface, 508
SortedSet interface, 525
Interning of strings, 8
Intractable problem, 119
Invariant subtyping, 237
Is-a, 47
Iterative method, 161
Iterator, 143
bi-directional, 285
design pattern, 143
J
Java Collections Framework, 133
Java Virtual Machine, 92
java.util, 12
assertEquals, 62
error, 76
no testing of Big-O claims, 131
no testing double values for equality, 66
K
Key part in a map, 504
Knight's Tour (project), 222–224
L
Last-in, first-out (LIFO),
in a stack, 32
Late binding, 49
Latest time (for an event), 668
Leaf, 378
Leap year, 71
LeapYear class, 72
Left child, 379
Left rotation
followed by right rotation, 434–435
Length
of a path in a graph, 645
of a path in a network, 650
Let's Make a Deal (project), 131–132
Line editor (application), 300–315
Linear in n, 117
Linear-logarithmic in n, 117
Link, 267
Linked list, 267
doubly linked list, 268
singly linked list, 268
alternate implementation (project), 323
versus ArrayList class, 282–285, 291
List interface, 147
loadFactor, 611-612
explicit initialization, 10
Logarithmic in n, 117
Longest path through a network, 667–668
Lower bound on sorting, 468–469
M
Map, 504
embedded Entry interface, 610
Mathematical background
functions and sequences, 705–719
mathematical induction, 708–719
Mathematical induction. See Principle of Mathematical
Induction
and recursion, 719
Mathematical model, 350
Mean arrival time, 362
Median, 478
finding in linear-in-n time (exercise), 495–496
of medians, 488
Member of a class, 35
Member-selection operator, 7
in Collections class, 476
Message
in Huffman encoding, 573
in object-oriented language, 7
Method, 1
abstract, 29
accessor, 57
active, 208
exponential-time, 119
final, 61
iterative, 161
mutator, 57
overloading, 5
polynomial-time, 119
signature, 5
static, 61
testing of, 61–67, 69–70, 74–77
virtual, 49
Minimum spanning tree, 659–663
Model, 350
mathematical, 350
physical, 350
Modifier. See Visibility modifier,
abstract, 138
transient, 248
Modulus operator (%), 2
Mutator method, 57
N
Natural logarithm, 708
Neighbor, 644
Nested class, 269
backtracking through, 686–689, 695–697
finding minimum spanning tree, 659–663
finding shortest path, 663–667
NetworkTest class, 677
project network, 667
Traveling Salesperson Problem (project), 694–695
new operator, 4
node, 136
Notation
Big-Omega, 116
infix, 338
postfix, 339
prefix, 343
null keyword, 7
NullPointerException, 78
O
overriding equals method of, 94–96
Object-oriented concepts, 27–49
double hashing, 632–635, 638, 640
Open-Closed Principle, 38
Operator
bitwise exclusive or (^), 608
bitwise left shift (<<), 382
bitwise right shift (>>), 112
unsigned (>>>), 608
conditional (? :), 300
equality (==), 8
instanceof, 96
modulus (%), 2
new, 4,
Overloading of methods, 5
P
Package, 93
Parent, 379
length, 645
Path length
external, 385
Path Rule, 502
Performance requirements, 120
Permutation, generating
lab experiment, 191
Persistent object, 702
Physical model, 350
Polynomial-time method, 119
Postfix notation, 338
converting from infix to, 338–343
Pre-initialization of fields, 92
Precondition, 28
Prefix notation, 343
converting from infix to, 343–346
Primitive type, 2
Principle of Data Abstraction, 27–28
Principle of Mathematical Induction, 708
general form, 711
strong form, 710
Priority queue, 551
heap implementation of, 553–556
in Huffman encoding, 575
in minimum-spanning-tree algorithm, 660
in shortest-path algorithm, 664
versus other visibility modifiers, 93–94, 100
Probing
quadratic, 635
critical activity, 668
critical path, 668
earliest time of an event, 668
latest time of an event, 668
sink, 667
slack time of an activity, 668
source, 667
topological order, 669
topological sorting, 669
fields, 39
methods, 42
testing protected methods, 306
versus other visibility modifiers, 39, 94
Pseudo-random number generator, 122
versus other visibility modifiers, 39, 94
Public-key cryptography, 251
Punched-card sorters, 489
PurePriorityQueue class, 552
PureQueue class, 349
PureStack class, 333
Q
Quadratic in n, 117
Quadratic probing, 635
Queue, 347
dequeue, 347
enqueue, 347
Queue interface, 348
implemented by LinkedList class, 348
implemented by PriorityQueue class, 552
Quotient-offset collision handler, 632–633
R
Random access, 134
Random number, 122
Random-number generator, 122
Randomizing
arrival times in simulation, 362–365
variable seed in Random class, 123
Reachable vertices, 651
decimal to binary (application), 162–167
definition, 209
factorial, 156–159 indirect, 208–209
induction and, 719
infinite, 177
maze searching (application), 195–208
stack frame, 304
stack-based implementation, 334–338
Towers of Hanoi (application), 167–179
versus iteration, 161
Recursive definition, 377
Red Rule, 502
Red-black tree, 502
in TreeMap implementation, 504
Reference variables, 4
testing equality of (==), 8
Right child, 379
Right rotation, 433
followed by left rotation, 435
Robust program, 68
Rotation, 431
properties of, 435
of sort methods (lab), 492
S
SalariedEmployee class (lab), 46
delimiter, 12
InputMismatchException, 71
scanning over a string, 12
scanning over file input, 12
scanning over keyboard input, 12
token, 12
useDelimiter method, 16
whitespace, 12
Scope of an identifier, 11
Search engine. See Integrated Web Browser and Search Engine
Searching
binary search, 180–181, 601–602
seed, 123
Sequence, 706
Sequential searching, 179, 600–601
Set interface, 403
Shortest path through a network, 663–667
Signature of a method, 5
Simulation, 350
event driven, 354
Singly linked list, 268
SinglyLinkedList class, 268–281
embedded SinglyLinkedListIterator class, 276–279
embedded Entry class, 268
expanding (projects), 319–322 field, 273
SinglyLinkedTest class, 271–272
Sink, 667
Slack time (for an activity), 668
SortedMap interface, 508
TreeMap implementation of, 509
Sorting
fast sorts, 470–475, 477–489, 567–573
file sorting (project), 497–499
stable sort, 458
summary, 493
topological sorting, 669
Source, 667
Spanning tree, 659
Specification of methods, 5
Speedo's car wash (application), 351–354
making more realistic, 362–365
Spell Checker (application), 530–531
SpellCheckerTest class, 532–533
SpellCheckerUser class, 534–536
Splitting Rule, 112
Stable sort, 458
Stack, 329
in converting from infix-to-postfix, 334–338
in implementing recursion, 338–341 Stack class, 329–333
Stack frame, 334
Static constant, 60
static modifier, 60
Static variable, 60
Storage structures for collection classes, 136
constructors, 4
testing equality of String objects, 7–8
Stub, 64
Subclass-Substitution Rule, 44
super, 40
Superclass, 37
Symbol table, 617
Synonym, 606
System test, 91
T
Testing
bottom up, 91
unit testing. See JUnit
system tests, 91
Thesaurus (application), 517–518
ThesaurusUserTest class, 521–522
throw statement, 71
Token, 342
Topological order, 669, 693–694
Topological sorting, 669
Towers of Hanoi (application), 167–178
iterative version (project), 219–220
performance requirements, 120
time versus space, 120
transient modifier, 248
Traveling Salesperson Problem (lab), 684
Traversals of a binary tree, 383–392
preOrder (= depth-first), 390–391
Tree
balanced binary search tree, 430
binary search tree, 402
binary tree, 377
complete tree (binary), 382
decision tree (binary), 468
directed tree, 648
expression tree (binary), 389–390
Fibonacci tree (binary), 437
full tree (binary), 381
Huffman tree (binary), 575
red-black tree (binary), 502
spanning tree, 659
subtree, 377
two-tree (binary), 381
undirected tree, 648
approval voting (problem), 545–547
building a concordance (problem), 543–545
building a thesaurus (application), 518–525
Comparable and Comparator interfaces, 510–511
determining word frequencies (problem), 542–543
Entry class, 513
field in Network class, 680–681
fields in, 512
red-black tree, 504
SortedMap interface, 509
views (entrySet(), keyset(), values()), 507–508
spell checker (application), 530–536
with finally block, 81
Two-tree, 381
Type parameter, 141
U
UML, See
Unified Modeling Language Unboxing, 141
acyclic, 646
adjacent, 644
complete, 644
connected, 646
cycle, 646
edge, 643
neighbor, 644
path, 644
vertex, 643
Undirected, weighted tree, 676
Unified Modeling Language (UML), 49–52
Uniform distribution, 112
Uniform Hashing Assumption, 609
Upper bound, 107
V
Value part in a map, 504
reference variable, 4
Vertex, 643
comparing vertices, 680
reachable, 651
Very long integers (application), 251–257
field in, 254
VeryLongIntTest class, 253
VeryLongIntUser class, 257
VeryLongIntUserTest class, 257
Virtual method, 49
default visibility, 93
W
Web browser. See Integrated Web Browser and
Search Engine
Weighted graph, 649
Word frequencies (problem), 542–543
worstSpace(n), 105
worstTime(n), 106
Wrapper class, 135
conversions from/to, 135
3.139.86.18