ABListIterator, iterator class, 352–353

abstract data types defined, 70

abstract keyword, 73

abstract methods

• declaring, 73

• defined, 72

abstraction, 68–78

• data abstraction, 69–70

• data levels, 70–71

• defined, 68

• information hiding, 68–69

• Java interfaces, 72–76

access modifiers

• Java, 5t

• purpose and use of, 5–6

activation record (stack frame), defined, 193

addresses, references as, 34

adjacency lists

• defined, 596

• representation of graphs with, 597

adjacency matrix, 591

• defined, 591

• representing edges in graph with, advantages, 596

adjacent vertices, defined, 588

ADTs. See abstract data types

algorithms

• comparing, 43–54

• inefficient, recursive solution and, 198–200

• recursive, 163–165

aliases, 35–36

amortized analysis, 233

ancestors, 424, 425

anonymous inner class, 353–354

application, 10–12

• (or user) level, of ADT, 70

array-based implementations

• collection ADT, 300–304

• of graphs, 591–596

• for List ADT, 350–355

• map implementations, 508–512

• for Queue ADT, 223–233

• for stack ADT, 90–101

ArrayBlockingQueue, 282

ArrayBoundedQueue class, 223–229

ArrayBoundedStack Class, 91–137

ArrayCollection class, 301–304

ArrayDeque class, 256

ArrayList class, 90, 99, 100, 123, 231, 565

ArrayList iterator method, 512

ArrayListMap.java, code for, 508–511

ArrayListStack class, 99–101

arrays, 28, 28, 38–43

• linked lists vs., 111–113

• of objects, 39

• with references, sorting, 660

• specifying size of, 38

• two-dimensional, 42–43

ArrayUnboundedQueue class, 230–233

asterisk (*), in import declarations, 21

average case complexity, 45

average waiting time application, 257–268

AVL trees, 484-485

B-trees, 483–484

Bag ADT, 331-333

balance operation, for balancing binary search tree, 469

base case, defined, 165

BasicSet1.java, 334

BasicSet2.java, 335

best case complexity, 45

binary operators, 132

binary search, 47, 170–174

• algorithm, 171

• code for, 174

• sorted lists and, 663–664

binary search trees, 429–435

• balancing, 469–471

  • iterative part of algorithm, 469

  • optimal transformation, 471

  • recursive part of algorithm, 469

• classes and interfaces, UML diagram of relationships among, 486

• defined, 432

• implementation level

  • basics, 439–443

  • remaining observers

    • add operation, 455–460

    • contains and get operations, 449–452

    • iteration, 448

    • remove operation, 460–463

• implementing priority queues and, 556

• insertions into, 456

• iterative approach to size method, 446–448

• iterative part of algorithm, 469

• iterative vs. recursive method implementations, 443–448

  • recursion or iteration?, 448

  • recursive approach to size method, 443–448

• performance

  • insertion order, 468

  • text analysis experiment, 466–467

  • tree shape, 468–469

• property, 431–432

• recursive part of algorithm, 470

• removals from, 463

• restructuring, 469

• two, 445

binary tree traversals, 433–434

• inorder traversal, 433

• postorder traversal, 433

• preorder traversal, 433

• visualizing, 434

binary trees, 429–431, 430, 431, 432, 485

• defined, 429

• full, 556

• general, 557

• height of, 431

• nodes for, 440

• as recursive structures, 424

boolean type, 27

bounded time O (1), 53

BoundedQueueInterface, code for, 222

breadth-first searching, airline-route graph and, 602–605

breadth-first traversal

• tree traversals, 426–427

  • algorithm for, 427

BSTInterface interface, 436–437, 440

BSTNode class, 457, 462

• code for, 441–443

bubble sort, 631–635

• analyzing, 633–635

• basic algorithm for, 631

• example of, 632

• snapshot of algorithm, 633

buckets, 523

• collisions and, 523

buffers, queues and, 220

by copy, collection ADT, 319–320, 322

by reference, collection ADT, 319–321, 322

by reference variables, by value variables vs., 35

by value variables, by reference variables vs., 35

byte code, Java, 191

byte type, 27

catch statement, 22, 27

char type, 27

children

• in binary trees, 429

• in trees, 31, 423

Circle class, 34, 73, 78, 84, 309

• code for, 73

circular linked queue, 241

classes, 2–7

• interfaces implemented by, 73

• organizing, 12–22

  • inheritance, 12–19

  • packages, 19–22

• role of, 2

ClassPath directories, 21

clone operation, 143

clustering, 521

collection ADT, 298–336

• array-based implementation, 300–304

• assumptions, 299

• BagInterface class, 331–333

• CollectionInterface class, 299

• comparing objects, 308–315

  • equals method, 308–314

  • interface, 314–315

• defined, 81

• elements, 81–84, 82

• interface, 298–300

• link-based implementation, 325–330

  • comparison, 329–330

  • internal representation, 325

  • operations, 326–329

• naming conventions, 325

• primary classes and interfaces, 337

• protected methods, 302

• Set ADT, 333–336

• sorted array based implementation, 315–324

CollectionInterface, 299, 435

• code for, 300

• method definitions, 331

collisions, 518–519, 518–519, 519

• with buckets, 523

• with chaining, 524

Comparable interface, 308, 314–315

Comparable keys, 507

Comparable objects, 442

Comparator object, 507

compare method, 661

compareTo method, 308, 661, 662

• operation consistency, 315

comparison operator (==), 37

compilation units, multiple, packages with, 20

complete binary tree, 557

complete directed graph, 587

complete graphs, 586

• defined, 588

• types of, 587

complete undirected graph, 587

compression function, 517, 518

concurrency, 283

• Java Library Collection classes and, 282

concurrent programming, 269, 279

ConcurrentLinkedQueue, 282

constant time, 53

constants, capitalization of, 4

CSInfo application, 311–313

Customer class, code for, 260–262

CustomerGenerator class

• code for, 261–262

cycle, defined, 586

Date class, 2, 3–4, 12, 16, 17, 23, 70

• class diagram for, 8

• days-between problem and, 10

DaysBetween program, code for, 11

DecimalFormat class, 472

decision trees, 479–480

depth-first searching, 81, 598–602

• code for, 605

depth-first traversal

• tree traversals, 428–429

  • algorithm for, 429

depth of the recursion, defined, 195

DequeInterface class, 251, 256

dequeue operation, 219

• fixed-front design approach in ArrayBoundedQueue class and, 224

• floating-front design approach in ArrayBoundedQueue class and, 225, 226

• heaps and, 559

• link-based implementations for Queue ADT, 239–241, 240

• for Priority Queue ADT, 553

descendants, in binary trees, defined, 424

Dictionary class, 283

digraph, 584

direct addressing, 33

direct recursion, defined, 166

directed graph (digraph), 587, 588

• defined, 584

disconnected graph, 586

disjoint subtrees, 423

DLLNode class, 253

double ended queue, 251

doubly linked lists, 252–255

• with two references, 388

dynamic binding, 19

dynamic memory management, defined, 37

dynamic programming, 200

dynamic storage allocation, recursion and, 193–195

edges (arcs), 587

• adding to graphs, 594

• in graphs, 584

encapsulation, 69

enlarge method, ArrayUnboundedQueue class and, 230, 231

enqueue operation, 219

• fixed-front design approach in ArrayBoundedQueue class and, 224

• floating-front design approach in ArrayBoundedQueue class and, 225, 226

• link-based implementations for Queue ADT, 238–239, 239

• for Priority Queue ADT, 555

equals method, 298, 308–314

• operation consistency, 315

Exception class, 24

exceptional situations, 22–27

exponential time, O(2^N), 53–54

expression/parse trees, 480–481

factorial method, 166, 193

• iterative solution for, 167

• recursive call in, 195

factory methods, 347

FamousPerson class, 310–311

FIFO. See First in, first out

FigureInterface.java, 73-78

final modifier, purpose of, 4

first in, first out, 29

• as priority queue, 552

• queue operations, breadth-first searching and, 603

fixed-front design approach, for ArrayBoundedQueue class, 224–225

float type, 27

floating-front design approach, for ArrayBoundedQueue class, 225

for-each loops, 347

fractals, 186–190

full binary tree, 556

functional modularization, 10

garbage, 36-37

generic collections, 83–84

getIterator

• method, 435

• snapshot, 437

GlassQueueInterface class, 248–250, 249

• code for, 249

graph ADT, specification of, 589. See also graphs

graphical user interface (GUI), 107

graphs, 31

• adjacency list representation of, 597

• ADT, 583–611

• applications, 597–611

  • breadth-first searching and, 602–605

• complete, 588

• defined, 584

• directed, 584, 587

• edges in, 584

• examples of, 587

• implementations of, 591–597

  • array-based implementation, 591–596

  • linked, 596

• introduction to, 584–588

• operations, 589

• terminology, 588

• undirected, 584, 587, 588

• vertices in, 584

• weighted, 587, 587, 588, 610

growth rates, comparison of, 54t

GUI approach, 109–110, 406

• list-related classes and interfaces, 409

hash-based map, 530–539

• HMap class, using, 538–539

• implementation, 531–538

hash code, 526

hash functions, in map ADT, 524–530

• array size, 524–525

• complexity, 530

• defined, 526

• Java’s support for, 529–530

• minimizing collisions with, 666

• selecting, digitizing, and combining, 526–527

• things to consider, 527–529

hash table, 516

hashCode method, 529

hashing

• in map ADT, 516–524

  • buckets, 523

  • chaining, 524

  • collisions, 518–519

  • defined, 516

  • entry removal, 520–521

  • hash table, 516

  • linear probing, 519–520

  • quadratice probing, 521–523

• in search, 665

HashMap class, 283

HashSet class, 283

HashTable class, 283

header node, 381

Heap class, 608, 653

heap sort, general approach of, 652

heap values, in array representation, 562

HeapPriQ class

• code for, 565–567

heaps, 556–576

• building, 652–655

  • algorithm for, 653

  • changing contents of array, 654

  • process for, 654

• defined, 556

• dequeueing elements from, 559

• enqueueing elements to, 560

• implementation of, 562–576

  • dequeue method, 569–574

  • enqueue method, 567–569

• maximum, 557

• other representations of priority queues vs., 575–576

• testing, 574–575

hierarchical relationships, trees and modeling of, 423

high-probability ordering, 663–664

HMap code, 531–536

hybrid data structures, 541

immutable objects, 13

implementation dependent structures, 28–29

• arrays, 28

• linked lists, 29

implementation independent structures, 29–31

• graphs, 31

• queues, 29–30

• sorted lists, 30

• stacks, 29

• trees, 31

import statements, forms of, 21

indexed lists, 346

IndexedListInterface, code for, 348–349

IndexOutOfBoundsException, 346

indirect addressing, 33

indirect recursion

• defined, 166

• remove operation and, 466

infix notation, 132

information hiding, 68–69

inheritance, 5, 12–19

• extended class diagram for, 15

• of interfaces, 249

inheritance based polymorphism, 18–19

inheritance tree, 15, 16–17

Inner class, iterator class, 353

inorder traversal, 434, 452

• defined, 433

• generating, 433

• uses for, 437

• visualizing, 434

input size, 46

insertionSort, 374, 635–638, 638

• algorithm of, 637

• analyzing, 638

• code for, 638

• example of, 636

• order of magnitude for, 666t

integrated testing, 96–98

interactive test driver, Queue ADT, 234–237

• algorithm for implementation, 234

• sample output, 236

interface keyword, 72

interfaces

• benefits of, with ADT specifications, 75–76

• class implementation of, 73

• example of, 73

• in java, 72–76

• versatility and power of, 75

interference, threads and, 274–275

ITDArrayBoundedQueue, 235

Iterable interface, 347, 435

iteration

• Binary Search Tree ADT, 448

• defined, 346

iterative approach, to size method, 446–448

iterative solution, for factorial, 167

iterator

• interface, 408

• object, 435, 590

• snapshot, 437

iterator() method, 347, 512

• code for, 359

• defined, 347

Java programming model, description of, 191

Java threads, 271–274

Java Virtual Machine, executing, 10

Java’s Scanner, 307

Java’s support for

• hash functions, in map ADT, 529–530

• map variations, 542

join command, 273, 274

key attribute, 298

Kids class, code for, 191–192

large integers

• internal representation, 387–388

• LargeInt object, 386

• with linked list, 387

LargeInt class, 393

• adding element to beginning, 391

• addition rules, 402

• helper methods, 396–398, 400

• subtraction, 403

leaf

• in binary trees, defined, 425

• removing, 461

leaf nodes, removing, 461

level-order traversal, 426

LIFO. See Last in, first out

Lilian Day Numbers, 3, 6–7, 10

lilian method, 10

linear linked lists, traversals, 426

linear probing

• hashing, in map ADT, 519–520, 519, 520

• vs. quadratic probing, 523

linear time, O(N), 53

link-based implementations

• collection ADT, 325–330

• of graphs, 596

• for list ADT

  • index-related operations, 356

  • iteration, 358

• for Queue ADT, 237–244

  • dequeue operation, 239–241, 240

  • enqueue operation, 238–239, 239

• for stack ADT, 121–132

linked list, 28, 29, 111–121

• arrays vs., 111–113

• in dynamic and static storage, 383

• LLNode class, 113–115

• operations on, 115–121

  • insertion, 119–121

  • remaining operations, 121

  • traversal, 116–119

• recursive nature of, 175

• transforming, 178–182

• traversing, 175–178

• variations, 382

  • Java library lists, 380–381

LinkedBlockingQueue, 282

LinkedCollection class, 334

LinkedGlassQueue class, 250

• code for, 250

• queue variations, 248

LinkedList class, 381

LinkedQueue class, 237

LinkedStack class, 122, 131, 197

list ADT, 345–408

• applications, 366–373

• array-based implementations for, 350–355

• assumptions about, 348

• defined, 346

• informal specification for, 348

• iterable, 352

• in Java Collections Framework, 346

• link-based, 355–360

List interface, 348–350

list-related classes and interfaces, 409

LLNode class, 113–115, 115, 122, 125, 129

• code for, 115

logarithmic time, O (log₂N), 53

logical (or abstract) level, of ADT, 70–71

long type, 27

Map ADT, 499–543

• hash-based map, 530–539

• hash functions, 524–530

• hashing, 516–524

• implementations, 506–512

• legal mapping variations, 502

• rules for, 501

• variations, 539–542

map implementations, 506–512

• array-based implementation, 508–512

• binary search tree, 508

• sorted array, 507

• sorted linked list, 508

• unsorted array, 506–507

• unsorted linked list, 507

map variations, 539–542

• hybrid structure, 540–542

• Java support for, 542

MapEntry class

• code for, 504

MapInterface, 501–506

• code for, 502–503

maximum heap, 557

• shortest-path algorithm and, 608

merge sort, 639–646

• algorithm for, 639

• analysis of algorithm with N = 16, 645

• merging for sorted halves, 640, 642

mergeSort algorithm, analysis of, with N = 16, 644, 645

multi-tasking, defined, 268

N log N time, 53

naming constructs, 123

natural order of class, 314

nodes, 440

• as ancestors of other nodes, 443

• in binary trees, 429–430, 440

• in graphs, 31, 584

• iterative method to counting of, on linked lists, 446

• level of, 425

• in linked lists, 112, 113

• with only one child, removing, 461, 461

• removing, methods for, 460–462, 462

• of trees, 423

• with two children, removing, 461, 462

• without subtrees, determining, 445

nonprimitive variables, primitive variables vs., 37, 309

null reference, 9, 34

null value, 113

NullPointerException, 128

Object class, 16, 17–19, 82, 83, 92

objects, 8–10

• aliases and, 35–36

• array of, 39

• changing to strings, 16

• comparing, 37

• sorting, 660

observers, defined, 4

O(N log₂N) sorts, 638–657

• heap sort, 652–657

• merge sort, 639–646

• quick sort, 646–651

order property, 557

order of growth, 49–50

• exponential time, 53–54

• linear time, 53

• logarithmic time, 53

• N log N time, 53

• quadratic time, 53

@Override notation, 309–310

package access, 5

packages, 5

• with multiple compilation units, 20

• subdirectories and, 21

• syntax for, 19–20

• textbook program files, 21–22

Palindrome class

• code for, 245–246

• creating, 244

palindromes

• application, 244–247

• defined, 244

• program, architecture for, 247

Parallelogram class, 75

parameters, 37–38

parents, in trees, 31, 424

paths, between vertices, 586

pixels, defined, 186

pointers, references as, 34

polymorphism

• defined, 18

• inheritance based, 18–19

• interface-based, 76–78

pop operation, 79, 80, 85, 127, 128

postconditions, defined, 72

postfix expressions

• error processing, 136–137

• evaluating, 132–141

  • algorithm, 134–136

• evaluation algorithm, 134

• GUI approach, 141

postorder traversal, 434, 452

• code for, 455

• defined, 433

• generating, 433

• uses for, 433

• visualizing, 434

preconditions, defined, 71

preorder traversal, 434, 452

• balancing binary search tree and, 471

• code for, 455

• defined, 433

• generating, 433

• uses for, 433, 435

• visualizing, 434

primitive types, 27

• reference types vs., 34–35

primitive variables, 33

• vs. nonprimitive, 309

• vs. nonprimitive variables, 37

priority queues, 551-556

heaps used for implementing, 657

PriQueueInterface, 565

• code for, 553–554

private access modifier, 5, 5t

professional testing, 98–99

programming

• concurrent, 279

• dynamic, 200

protected access modifier, 5, 5t, 6

public access modifier, 5, 5t

push operation, 79, 80, 85, 124–127, 127

quadratic time, O(N²), 53

quadratice probing, 521–523

• hashing, in map ADT, 521–523

• vs. linear probing, 523

queue ADT, 29–30, 29, 217–283, 218–220. See also priority queues

• array-based implementation of, 223–233

• average waiting time application, 257–268

• circularly linked, 241

• comparing implementations, 242–244

• description, 218–219

• interactive test driver, 234–237

• interface for, 220–223

• link-based implementations, 237–244

• operations on, 219

• palindromes application, 244–247

• synchronized, 277–282

• variations, 247–257

QueueInterface

• code for, 221

• in Java Library Collection Framework, 255

• UML diagram of, 247

QueueOverflowException class, 221

QueueUnderflowException, 221, 241

quick sort algorithm, 647–651

R-trees, 481

Random class, 260

RDN. See Relative Day Number

recPrintList method

• the base-case question, 176

• the general-case question, 176

• the smaller-caller question, 176

recRemove method, 460, 464

• recursive definition and code for, 464–465

recRev-PrintList method

• stacking and, 196

Rectangle class, 74, 78

recursion, 161–201

array processing, 170-174

• debugging recursive methods, 170

• deciding whether to use recursive solution, 197–201

• depth of, 195

• direct, 166

• how it works, 191–195

  • dynamic storage allocation, 193–195

  • static storage allocation, 191–193

• indirect, 166

• recursive algorithms, 163–169

• recursive definitions, 162–163

• recursive linked-list processing, 174–182

• stacking and, 196–197

• tail call elimination and, 195–196

• three questions approach, 167–170

• Towers of Hanoi, 182–186

• writing recursive methods, 169

reference types, primitive types vs., 34–35

reference variables, 33

references, 34–37

• manipulating, exercising care in, 120

• sorting and, 660

• sorting arrays with, 660

rehashing, 525

reheapDown algorithm, 571

reheapDown method, 657

• building a heap and, 652–653, 653

reheapDown operation

• in action, 571

• specification for, 559

reheapUp algorithm, 569

reheapUp method, code for, 569

reheapUp operation, 560

• in action, 568

Relative Day Number, 7

remove operation, 460–463, implementing Binary Search Tree ADT and

• implementing, four methods for, 460–462, 462

reserved words, in Java, 2

reusable software, 146

root

• defined, 423

• in trees, 31

root node

• in binary trees, 432

• reheapDown method and, 652, 653

run-time binding, 19

run-time (system) stack, defined, 194

Runnable interface, 271

RunTimeException class, 346

SafeDate class, 24, 25

Scanner class, 10

searching, 662–665

• high-probability ordering, 663

• sequential, 663

selection sort

• algorithm, 50–53, 51

• algorithm for, 627

• analyzing, 630–631

• example of, 627

• snapshot of algorithm, 628

• test harness code, 628–629

selectionSort method, 628, 630, 631, 638

• code for, 629

• order of magnitude for, 666t

self-organizing (or self-adjusting) lists, 664

self-referential class, defined, 113

sequential searches, 44, 663

set ADT, collection ADT, 333–336

shape property, 557

short type, 27

shortBubble, 638

• order of magnitude for, 666t

shortestPaths algorithm, 606-609

siblings, in trees, 424

simple sorts, 625–638

• bubble sort, 631–635

• insertion sort, 635–638

• straight selection sort, 625–638

Simulation class, 263

• code for, 264–267

single-source shortest-paths problem, 605–611

Smaller-Caller Question

• binary search, 173

• recursive algorithms verified with, 168

• Towers of Hanoi and, 185

software, reusable, 146

sorted array based implementation

• for collection ADT, 315–324

• for list ADT

  • LBList, 373

  • Like ABList, 373

  • SortedABList, 373

• for map ADT, 507

• priority queues and, 554–555

sorted linked list

• implementing priority queues and, 556

• map implementations, 508

sorted lists, 30, 348, 373

SortedArrayCollection class, 317–318

Sorting, 622–625

• algorithms, comparison of, 666t

• arrays with references, 660

• efficiency of, 622, 658–660

  • eliminating calls to methods, 659

  • programmer time, 659–660

  • space considerations, 660

  • when N is small, 658–659

• with heap, 655–657

• objects, 660

space considerations, 660

stable, 661–662

• test harness, 623–625

• testing and, 658

Square class, 75

Stack class, 282

stack implementations, comparing, 131–132

stack interface, 84–90

• example for, 89–90

• exceptional situations, 85–88

stack operations

• definitions of, 93–96

• efficiency of, 131

stack variations, 142–145

stacking, recursive calls and, 196–197

stack(s), 29, 29, 78–81, 78

• defined, 79

• as last in, first out structures, 218

• link-based, 121–132

• operations on, 79

• usage of, 79–81

static storage allocation, recursion and, 191–193

storing information by reference, dangers of, 607

Selection sort, 625–638

String class, 18, 19, 82, 124, 307

StringPairApp.java, code for, 513–514

subclasses, 5

• inheritance and, 12

subdirectories, packages and, 21

subtrees, 423

• nodes without, determining, 446

• right and left, 431

superclasses, 5

• inheritance and, 12

SyncArrayBoundedQueue class, 282

• code for, 279–281

SyncCounter class, code for, 276

synchronization, 275–277, 283

synchronized keyword, 276, 279

synchronized queues, 277–282

Synchronous-Queue, 282

system stack, defined, 194

T-square fractals, 187–190

• drawing stages, 187

• variations Samples, 188

tail call elimination

• recursive calls and, 195–196

tail recursion

• defined, 196

• heap sort algorithm and, 655

test harness

• code for Sorts.java, 623–625

• defined, 623

• sorting and, 658

testing

• ADTs, 96–99

• heaps, 574–575

thread object, instantiating, 272

threads

• interference and, 274–275

• Java, 271–274

Three-Question approach

• binary search, 173–174

• recursive algorithms verified with, 167–170

• recursive methods verified with, 170

time efficiency, measuring algorithm’s, 44–45

toString method, 16, 17, 18, 19, 98

• heap test and, 574–575

• invoking, 9

Towers of Hanoi, 182–186

• algorithm, 182–184, 183

• method, 184–185

• program, 184–186

trailer node, 381

transformers, defined, 4–5

traveling salesman problem, exponential time and, 53–54

traversals

• binary tree, 433–435

• in linked lists, 116–119

traversing, linked list, 175–178

tree shape, insertion order and, 468–469, 468

tree traversals, 426–429

• breadth-first traversal, 426–427

• depth-first traversal, 428–429

tree variations

• application-specific variations, 479–482

• balanced search trees, 482–485

trees, 31, 31, 423–428, 431. See also binary search trees

• See also binary trees

• defined, 423

• hierarchical relationships modeled with, 423

• purpose of, 423

• terminology, 425

• unsorted array and, 653

tries/prefix trees, 481–482

try-catch statement, 86

two-dimensional arrays, 39, 42–43

• variables, declaring, 43

UML. See Unified Modeling Language

unchecked exceptions, 27

undirected graphs, 584, 586, 587

Unified Modeling Language, class notation approach, 8

unreachable vertices, determining, 610–611

unsupported operations, for list ADT

• add or set, 375

• sorted array-based list implementation, for list ADT, 373–380

UnsupportedOperationException, 348, 375, 437

UseSafeDate class, 25

• code for, 26–27

util package, 10

Vector class, 143, 282

vertex (vertices), 588

• adjacency lists and, 596

• adjacent, 586

• finding index of, 595

• in graphs, 31, 584

  • representing, 594

• unreachable, 610–611

vocabulary density, application, 305–308

• algorithm for, 305

• code for, 305–307

• results of, 324t

weighted graphs, defined, 587, 587

WeightedGraphInterface.java, code for, 590–591

WeightedGraph.java, code for, 593–594

well-formed expression algorithm, 103

Word Frequency Generator program, 472, 473

WordFreq class, 472–473

• code for, 472–473

WordFreq object, 473–474, 501

worst case complexity, 45–46