Index

A

A-format instructions, 911

Absolute value function, 199

Abstract methods, 446

Abstraction

circuits, 1037–1039

color, 341–343

data, 382

displays, 346

function-call, 590–591

libraries, 230, 429

object-oriented programming, 329

printing as, 76

recursion, 289

vs. representation, 69

standard audio, 155

standard drawing, 144

standard I/O, 129, 139–143

Access modifiers, 384

Accessing references, 339

Account information

dictionary lookup, 628–629

indexing, 634

Accuracy

n-body simulation, 488

random web surfer, 185

Adaptive plots, 314–318

AddInts program, 134

Addition

complex numbers, 402–403

floating-point numbers, 24–26

integers, 22

spatial vectors, 442–443

Addresses, 94

Adjacency matrix, 692

Adjacent vertices, 671

Albers, Josef, 342

AlbersSquares program, 341–342

Alex, 380

Algorithms, 493

performance. See Performance

searching. See Searches

sorting. See Sorts

Aliasing

arrays, 516

bugs from, 439, 441

references, 363

Allocating memory, 94, 367

Amortized analysis, 580–581

Ampersands (&), 26–27

And operation, 26–27

Animations

BouncingBall, 152–153

double buffering, 151

Antisymmetric property, 546

Application programming interfaces (APIs)

access modifiers, 384

Body, 480

built-in data types, 30–32

Charge, 383

Color, 343

Comparable, 545

Complex, 403

Counter, 436–437

data types, 388

designing, 233, 429–431

Draw, 361

Graph, 675–679

Histogram, 392

implementing, 231

In, 354

libraries, 29, 230–232

modular programming, 432

Out, 355

PathFinder, 683

Picture, 347

Queue, 592

SET, 652

Sketch, 459

spatial vectors, 442–443

ST, 625

StackOfStrings, 568

StdArray, 237

StdAudio, 159

StdDraw, 149, 154

StdIn, 132–133

StdOut, 130

StdRandom, 233

StdStats, 244

StockAccount, 410

Stopwatch, 390

String, 332–333

symbol tables, 625–627

Turtle, 394

Universe, 483

Vector, 443

Arbitrary-size input streams, 137–138

args argument, 7, 208

Arguments

arrays as, 207–210

command-line, 7–8, 11, 127

constructors, 333, 385

methods, 30

passing, 207–210, 364–365

printf(), 130–132

static methods, 197

Ariane 5 rocket, 35

Arithmetic expression evaluation, 586–589

Arithmetic operators, 22

ArrayIndexOutOfBoundsException, 95, 116, 466

Arrays

aliasing, 516

as arguments, 207–210

assigning, 117

associative, 630

binary searches, 538–539

bitonic, 563

bounds checking, 95

comparing, 117

coupon collector problem, 101–103

decks of cards, 97–100

declaring, 91, 116

default initialization, 93

exchanging values, 96

FIFO queues, 596

hash tables, 636

I/O libraries, 237–238

images, 346–347

immutable types, 439–440

iterable classes, 6031

memory, 91, 94, 515–517

multidimensional, 111

overview, 90–92

parallel, 411

plotting, 246–248

precomputed values, 99–100

references, 365

resizing, 578–581, 635

as return values, 210

setting values, 95–96

shuffling, 97

side effects, 208–210

Sieve of Eratosthenes, 103–105

stacks, 568–570, 578–581

summary, 115

transposition, 120

two-dimensional. See Two-dimensional arrays

Arrays.binarySearch(), 559

Arrays.sort(), 559

ArrayStackOfStrings program, 568–570, 603

Arrival rate in M/M/1 queues, 597–598

Assertions, 466–467

Assignments

arrays, 117

chained, 43

compound, 60

description, 17

references, 363

Associative arrays, 630

Associativity, 17

Asterisks (*)

comments, 9

floating-point numbers, 24–26

integers, 22–23

Audio

plotting sound waves, 249

standard, 155–159

superposition, 211–215

Autoboxing, 457, 585–586

Automatic promotion, 33

Average-case performance, 648

Average magnitude, 164

Average path lengths, 693

Average power, 164

Average program, 137–138

B

Backslashes (), 19

Bacon, Kevin, 684

Balanced binary trees, 661

Ball animation, 152–153

Barnsley ferns, 240–243

Base cases

binary search trees, 640

recursion, 264–265, 281

Base classes, 452–453

Basic scaffolding, 302–304

Basic statistics, 244–246

Beck exploit, 529

Beckett, Samuel, 273

Beckett program, 274–275

Behavior of objects, 340

Benford’s law, 224

Bernoulli, Jacob, 398

Bernoulli program, 249–250

Best-case performance

binary search trees, 647

insertion sort, 544

Big-O notation, 520–521

Binary digits, 22

Binary number system

conversions, 67–69

description, 38

Binary operators, 17

Binary program, 67–69

Binary reflected Gray code, 274

Binary search trees (BSTs)

implementation, 645–646

insert process, 644–645

ordered operations, 651

overview, 640–643

performance, 647–648

search process, 643–644

symbol tables, 624–625

traversing, 649–650

Binary searches

binary representation, 536

correctness proof, 535

exception filters, 540

inverting functions, 536–538

overview, 533–534

random web surfer, 176

running time, 535

sorted arrays, 538–539

symbol tables, 635

weighing objects, 540–541

Binary trees

balanced, 661

heap-ordered, 661

isomorphic, 661

BinarySearch program, 538–539

Binomial coefficients, 125

Binomial distributions, 125, 249

Biology

genomics application, 336–340

graphs, 672

Bipartite graphs, 682

Bisection searches, 537

Bitmapped images, 346

Bitonic arrays, 563

Bits

binary number system, 38

description, 22

memory size, 513

register, 1051

Bitwise operations,39

Black–Scholes formula, 222, 565

Blobs, 709

Blocks

statements, 50

variable scope, 200

Bodies

loops, 53

static methods, 196

Body program

memory, 514

n-body simulation, 479–482

Bollobás–Chung graph model, 713

Book indexes, 632–633

Booksite, 2–3

Boole, George, 986

boolean data type

conversion codes, 131–132

description, 14–15

input, 133

memory size, 513

overview, 26–27

Boolean logic, 27

Boolean matrices, 302

BouncingBall program, 152–153

Bounding boxes for drawings, 146

Bounds of arrays, 95

Box–Muller formula, 47

Boxing, 457, 585–586

Breadth-first search, 683, 687–692

break statements, 74

Bridges, Brownian, 278–280

Brin, Sergey, 184

Brown, Robert, 400

Brownian bridges, 278–280

Brownian motion, 400–401

Brownian program, 278–280

Brute-force algorithm, 535–536

BST program, 645–646

BSTs. See Binary search trees (BSTs)

Buffer overflow, 95

Buffering drawings, 151

Bugs

aliasing, 363, 439, 441

overview, 6

testing for, 318

Built-in data types

boolean, 26–27

characters and strings, 19–21

comparisons, 27–29

conversions, 32–35

floating-point numbers, 24–26

integers, 22–24

library methods, 29–32

overview, 14–15

summary, 35–36

terminology, 15–18

Built-in interfaces, 451

byte data type, 24

Bytecode, 589

Bytes memory size, 513

C

Caches

and instruction time, 509

in dynamic programming, 284

Callbacks in event-based programming, 451

Calls, 193

chaining, 404

methods, 30, 197, 340

reverse Polish notation, 591

Canvas, 151

Card decks, arrays for, 97–100

Carroll, Lewis, 710

Cartesian representation, 433

Casts, 33–34

Cat program, 356

Centroids, 164

Chained assignments, 43

Chained comparisons, 43

Chaining method calls, 404

Characters and char data type

description, 15

memory size, 513

Unicode, 894–895

working with, 19–21

Charge program, 383–389, 515

Checksums

description, 86

formula, 220

Chords, 211

Chromatic scale, 156

Ciphers, Kamasutra, 377

Circular linked lists, 622

Circular queues, 620

Circular shifts, 375

.class extension, 3, 8, 228

ClassDefFoundError, 160

Classes, 4–5

accessing, 227–229

description, 226

implementing, 383–389

inner, 609

modules as, 228

variables, 284

Client code

data types, 430

library methods, 230

Clouds, plasma, 280

Clustering coefficients

global, 713

local, 693–694

CMYK color format, 48–49, 371

Code and coding

description, 2

encapsulating, 438

incremental development, 319, 701

reuse, 226, 253, 701

static methods, 205–206

Codebooks, 992

Codons, genes, 336

Coercion, 33

Coin flip, 52–53

Collatz problem, 296–297

Collatz sequence, 948

Collections

description, 566

iterable, 601–605

objects, 582–583

queues. See Queues

stacks. See Stacks

symbol tables. See Symbol Tables

Colons (:), 601–602

Color and Color data type

blobs, 709

compatibility, 344

conversion, 48–49

drawings, 150

grayscale, 344

luminance, 343

memory, 514

overview, 341–343

Columns in 2D arrays, 106, 108

Comma-separated-value (.csv) files, 358, 360

Command-line arguments, 7–8, 11, 127

Commas (,)

arguments, 30

constructors, 333

lambda expressions, 450

methods, 30, 196

two-dimensional arrays, 108

Comments, 5, 9

Commercial data processing, 410–413

Common sequences, longest, 285–288

Comparable interface, 451, 545

Comparable keys

sorting, 546

symbol tables, 626–627

CompareDocuments program, 462–463

compareTo() method

description, 451

String, 332

user defined, 545–546

Comparisons

arrays, 117

chained, 43

objects, 364, 545–546

operators, 27–29

performance, 508–509

sketches, 462–463

Compile-time errors, 6

Compilers, 3, 589

Compiling

array values set at, 95–96, 108

classes in, 229

description, 2

programs, 3

Complement operation

bitwise, 891

Boolean algebra, 990

Complete small-world graphs, 694

Complex program

chaining method calls, 404

encapsulation, 433–434

instance variables, 403–404

objects, 404

overview, 402–403

program, 405

Complex numbers, 406–409

Compound assignments, 60

Computer animations, 151

Computer speed in performance, 507–508

Computing sketches, 459–460

Concatenation

files, 356

strings, 19–20

Concert A, 155

Concordances, 659

Conditionals and loops, 50

applications, 64–73

break statement, 74

continue statement, 74

do-while loops, 75

examples, 61

for loops, 59–61

if statement, 50–53

infinite loops, 76

miscellaneous, 74–75

in modular programming, 227–228

nesting, 62–64

performance analysis, 500, 510

static methods, 193–195

summary, 77

switch statement, 74–75

while loops, 53–59

Connected components, 709

Connecting programs, 141

Constant order of growth, 503

Constants, 16

Constructors

data types, 384–385

String, 333

Containing symbol table keys, 624

continue statements, 74

Contracts

APIs, 230–231

design by contract, 465–467

interface, 446–447

Control flow

conditionals and loops. See Conditionals and loops

static method calls, 193–195

Conversion codes, 131–132

Conversion specifications, 130–131

Conversions

casts, 33–34

color, 48–49

data types, 339

decimal to binary, 877

explicit, 34–35

implicit, 33

numbers, 21, 67–69

overview, 32

strings, 21, 453

Conway, John, 326

Coordinates

drawing, 144–146

images, 347

polar, 47

Corner cases, 236

Cosine similarity measure, 462

Cost of immutable types, 440

Coulomb’s law, 383

Counter program, 436–437

Coupon collector problem, 101–103

Coupon program, 206

CouponCollector program, 101–103, 205

CPUs. See Central processing units (CPUs)

Craps game, 259

Cray, Seymour, 971

Crichton, Michael, 424

Cross products of vectors, 472

<Ctrl-C> keys, 76

<Ctrl-D> keys, 137

<Ctrl-Z> keys, 137

Cubic order of growth, 505–508

Cumulative distribution function, 202–203

Curly braces ({})

statements, 5, 78–79

static methods, 196

two-dimensional arrays, 108

Curves

Brownian bridges, 278–280

Dragon, 49, 424

Koch, 397

space-filling, 425

spirals, 398–399

Cycles per second, 155

D

Data abstraction, 329, 382

Data compression, 814

Data-driven code, 141, 171, 184

Data mining example, 458–459

Data structures, 493

arrays. See Arrays

binary search trees. See Binary search trees (BSTs)

linked lists, 571–578

queues. See Queues

resource allocation, 606–607

stacks. See Stacks

stock example, 411

summary, 608

symbol tables. See Symbol tables

Data-type design

APIs, 429–431

data mining example, 458–464

design by contract, 465–467

encapsulation, 432–438

immutability, 439–446

subclassing, 452–457

subtyping, 446–451

overview, 428

Data types

access modifiers, 384

APIs, 383

built-in. See Built-in data types

classes, 383

Color, 341–345

Complex, 402–405

constructors, 384–385

conversions, 34–35, 339

creating, 382

definitions, 331–335

DrunkenTurtle, 400–401

elements summary, 383

generic, 583–585

Histogram, 392–393

image processing, 346–352

immutable, 364, 439

input and output, 353–362

insertion sorts, 545–548

instance methods, 385–386

instance variables, 384

Koch, 397

Mandelbrot, 406–409

output, 355

overview, 330

reference, 362–369

Spiral, 398–399

StockAccount, 410–413

Stopwatch, 390–391

String. See Strings and String data type

summary, 368

Turtle, 394–396

type safety, 18

variables within methods, 386–388

Data visualization, 307–309

Dead Sea Scrolls, 659

Debugging

assertions, 466–467

encapsulation for, 432

immutable types, 440

incremental, 317, 319

linked lists, 596

modular programming, 251–254

test client main() for, 235

unit testing, 246

Decimal number system, 38

Decks of cards, 97–100

Declaration statements, 15–16

Declaring

arrays, 91, 116

String variables, 333

DeDup program, 652–653

Default values

arrays, 93, 106–107

canvas size, 145

ink color, 150

instance variables, 415

Node objects, 572

pen radius, 146

Defensive copies, 441

Defining

functions, 192

interfaces, 446

static methods, 193, 196

Definite integration, 816

Degrees of separation

description, 670

shortest paths, 684–686

Denial-of-service attacks, 512

Dependencies in subclasses, 453

Dependency graphs, 252

Deprecated methods, 469

Depth-first search

vs. breadth-first search, 690

percolation case study, 312

Deques, 618

Derived classes, 452

Descartes, René, 398

Design

APIs, 233

by contract, 465–467

data types. See Data-type design

Diameters of graphs, 711

Diamond operators (<>), 585

Dice

Sicherman, 259

simulation, 121

Dictionary lookup, 624, 628–632

Digital image processing

digital images, 346–347

fade effect, 351–352

grayscale, 347–349

overview, 346

scaling, 349–350

Digital signal processing, 155, 158

Dijkstra, Edsger

Dutch-national-flag problem, 564

two-stack algorithm, 587

Dijkstra’s algorithm, 692

Diophantine, 816

Directed graphs, 711

Directed percolation, 317

Discrete distributions, 172

Distances of graph paths, 683, 687–688

Divide-and-conquer approach

linearithmic order of growth, 504

mergesort, 550–551, 554

Division

floating-point numbers, 24–26

integers, 22–23

polar representation, 433

DivisorPattern program, 62–64

DNA computers, 795

DNS (domain name system), 629

do-while loops, 75

Documents, searching for, 464

Dollar signs ($) in REs, 731

Domain name system (DNS), 629

Domains, function, 192

Dot products

function implementation, 209

vectors, 92, 442–443

Double buffering drawings, 151

double data type

conversion codes, 132

description, 14–15

input, 133

memory size, 513

overview, 24–26

Double.parseDouble() method

calls to, 30–31

type conversion, 21, 34

Double quotes ("")

escape sequences, 19

text, 5, 10

Doublet game, 710

Doubling hypotheses, 496, 498–499

DoublingTest program, 496, 498–499

Downscaling in image processing, 349

Dragon curves, 49, 424

Dragon program, 163

Draw library, 361

Drawings

recursive graphics, 276–277

standard. See Standard drawing

DrunkenTurtle program, 400

DrunkenTurtles program, 401

Dumping virtual machines, 960–961

Dutch-national-flag problem, 564

Dynamic dictionaries, 628

Dynamic dispatch, 448

Dynamic programming

bottom-up, 285

longest common subsequence, 285–288

overview, 284

summary, 289

top-down, 284

E

Eccentricity in vertices, 711

Edges

graphs, 671, 674

self-loops and parallel, 676

Efficiency

n-body simulation, 488

random web surfer, 185

Efficient algorithms, 532

Einstein, Albert, 400

Election voting machine errors, 436

Electric charge, 383–389

Element distinctness problem, 554

Elements in arrays, 90

else clauses, 51–52

Empirical analyses, 496–497

Encapsulation

code clarity, 438

error prevention, 436–437

example, 433–434

modular programming, 432

overview, 432

planning for future, 435

private access modifier, 433

End-of-file sequence, 137

Entropy

Shannon, 378

text corpus, 667–668

Equality of objects, 364, 454–456

equals() method

Color, 343

vs. equals signs, 369–370

Object, 453–455

String, 332

Equals signs (=)

assignment statements, 17

assignment vs. boolean, 42, 78

comparisons, 27–29, 364

compound assignments, 60

vs. equals(), 369–370

Equilateral triangles, 144–145

Erdös, Paul, 686

Erdös–Renyi model, 695, 712

Errors

aliasing, 363

debugging. See Debugging

encapsulation for, 436–437

overview, 6

syntax, 10–11

testing for, 318

Escape sequences, 19

Euclidean distance

sketch comparisons, 462–463

vectors, 118

Euclid’s algorithm

description, 85

recursion, 267–268

Euler, Leonhard, 89

Euler’s constant, 222

Euler’s sum-of-powers conjecture, 89

Euler’s totient function, 222

Evaluate program, 588–589

Evaluating expressions, 17, 586–589

Event-based programming, 451

Exception class, 465

Exception filters, 540

Exceptions, 465–467

Exchanging values

arrays, 96

function implementation, 209

Exclamation points (!)

not operator, 26–27

comparisons, 27–29

Explicit casts, 33–34

Exponential distributions, 597

Exponential order of growth, 505

overview, 272–273, 506

running time, 507–508

Expressions

arithmetic evaluation, 586–589

description, 17

lambda, 450

method calls, 30

Extensible libraries, 452

Extracting data, 358, 360

F

Factorials, 264–265

Factoring, 72–73

Factors program, 72–73

Fade effect, 351–352

Fade program, 351–352

Fair coin flip, 52–53

Falsifiable hypotheses, 495

Fecundity parameter, 89

Fermat’s Last Theorem, 89

Ferns, Barnsley, 240–243

Fibonacci numbers

formulas, 82

recursion, 282–283

FIFO queues. See First-in first-out (FIFO) queues

Files

concatenating and filtering, 356

format, 237

in I/O, 126

n-body simulation, 483

redirection, 139–141

splitting, 360

stock example, 411

symbol tables, 629

Filled shapes, 149

Filters

exception, 540

files, 356

image processing, 379

piping, 142–143

standard drawing data, 146–147

standard input, 140

final keyword

description, 384

immutable types, 440

instance variables, 404

Financial systems, graphs for, 673

Finite-state transducers, 762

Finite sums, 64–65

First-in first-out (FIFO) queues

applications overview, 597

array implementation, 596

linked-list implementation, 593

M/M/1, 597–600

overview, 566, 592–593

Flexibility, 702

Flip program, 52–53

float data type, 26, 513

Floating-point numbers

conversion codes, 131–132

overview, 24–26

precision, 40

storing, 40

Flow of control

conditionals and loops. See Conditionals and loops

static method calls, 193–195

Flowcharts, 51–52

for loops

continue statement, 74

examples, 61

nesting, 62–64

working with, 59–61

Foreach statements, 601–602

Format, files, 237

Format strings, 130–131

Formatted input, 135

Formatted printing, 130–132

Forth language, 590

Fortran language, 717

Fourier series, 211

Fractal dimensions, 280

Fractals, 278–280

Fractional Brownian motion, 278

Fragile base class problem, 453

Freeing memory, 367

Frequencies

counting, 555

sorting, 556

Zipf’s law, 556

FrequencyCount program, 555–557

Fully parenthesized arithmetic expressions, 587

Function calls

abstraction, 590–591

static methods, 197

traces, 195

trees, 269, 271

Function graphs, 148, 248

Functional interfaces, 450

Functional programming, 449

Functions

computing with, 449

defining, 192

inverting, 536–538

iterated function systems, 239–243

libraries. See Libraries

mathematical, 202–204

modules. See Modules

overview, 191

recursive. See Recursion

static methods, 193–201

G

Gambler program, 70–71

Gambler’s ruin simulation, 69–71

Game of Life, 326

Garbage collection, 367, 516

Gardner, Martin, 424

Gaussian distribution functions

API, 231

cumulative, 202–203

probability density, 202–203

Gaussian elimination, 830

Gaussian program, 203

Gaussian random numbers, 47

Generic types, 583–585

Genomics

application, 336–340

indexing, 634

symbol tables, 629

Geometric mean, 162

Get operations

hash tables, 639

symbol tables, 624

Gilbert–Shannon–Reeds model, 125

Glass filters, 379

Global clustering coefficients, 713

Global variables, 284

Glossary of terms, 721–726

Golden ratio, 83

Gore, Al, 436

Graph data type, 675–679

Graph program, 677

Graphics

recursive, 276–277, 397

turtle, 394–396

Graphs

bipartite, 682

client example, 679–682

connected components, 709

dependency, 252

description, 671

diameters, 711

directed, 711

examples, 695

function, 148, 248

generators, 700

Graph data type, 675–679

grid, 708

lessons, 700–702

matching, 713

overview, 670–671

random web surfer, 170

small-world, 693–699

systems examples, 671–674

Gravity, 481

Gray codes, 273–275

Grayscale

Color, 344

image processing, 347–349

Grayscale program, 347–349

Greater than signs (>)

comparisons, 27–29

lambda expressions, 450

redirection, 139–140

Greatest common divisor, 267–268

grep tool, 142–143

Grid graphs, 708

H

H-trees of order n, 276–277

Hadamard matrices, 122

Hamilton, William, 424

Hamming distances, 295

Handles for pointers, 371

Hardy, G. H., 86

Harmonic mean, 162

Harmonic numbers

finite sums, 64–65

function implementation, 199

Harmonic program, 193–195

HarmonicNumber program, 64–65

Harmonics and chords, 211

Hash codes and hashing operation

object equality, 454–455

sketches, 460

strings, 515

symbol tables, 624

Hash functions, 636

Hash tables, 636–639

Hash values, 636

Hashable keys, 626

hashCode() method

Object, 453, 455–456

String, 332

HashMap class, 655

HashST program, 637–638

Heap memory, 516

Heap-ordered binary trees, 661

Height in binary search trees, 640

HelloWorld program, 4–6

Hertz, 155

Hilbert, David, 425

Hilbert curves, 425

Histogram program, 392–393

Histograms, 177

Hoare, C. A. R., 518

Hollywood numbers, 711

Horner’s method, 223

Htree program, 276–277

Hurst exponent, 280

Hyperbolic functions, 256

Hyperlinks, 170

Hypotenuse of right triangles, 199

Hypotheses

doubling, 496, 498–499

falsifiable, 495

mathematical analysis, 498–502

overview, 496

I

I/O. See Input; Output

Identifiers, 15–16

Identities of objects, 338, 340

IEEE 754 standard, 40

if statements

nesting, 62

working with, 50–53

IFS program, 241, 251

IllegalFormatConversionException, 131

Immutable types, 364, 439

advantages, 440

arrays and strings, 439–440

cost, 440

example, 442–445

final modifier, 440

references, 441

symbol table keys, 625, 655

Implementation

API methods, 231

interfaces, 447

Implements clause, 447

Implicit type conversions, 33

In library, 354–356

Incremental development, 319, 701

Index program, 632–634

IndexGraph program, 680–682

Indexing

arrays, 90, 116

String, 332

symbol tables, 624, 632–634

zero-based, 92

Induced subgraphs, 705

Induction

mathematical, 262, 266

recursion step, 266

Infinite loops, 76

Infinity value, 26, 40

Information content of strings, 378

Inheritance

multiple, 470

subclassing, 452–457

subtyping, 446–451

Initialization

array, 93

inline, 18

instance variables, 415

two-dimensional array, 106–107

Inline variable initialization, 18

Inner classes, 609

Inner loops

description, 62

performance, 500, 510

Inorder tree traversal, 649

Input

array libraries, 237–238

clocks, 1060

command-line arguments, 7

data types, 353

file concatenation, 356

gates, 1013

insertion sorts, 548–549

overview, 126–129

in performance, 510

random web surfer, 171

screen scraping, 357–359

standard, 132–138

stream data type, 354–355

InputMismatchException, 135

Inserting

BST nodes, 644–645

linked list nodes, 573–574

Insertion program, 546–547

Insertion sorts

data types, 545–548

input sensitivity, 548–549

overview, 543–544

performance, 544–545

InsertionDoublingTest program, 548–549

Instance methods

data types, 385–386

invoking, 334

vs. static, 340

Instance variables

Complex program, 403–404

data types, 384

initial values, 415

Instances of objects, 333

Integer.parseInt() method

calls to, 30–31

type conversion, 21, 23, 34

Integers and int data type

conversion codes, 131–132

description, 14–15

input, 133–134

overview, 22–24

Integrals, approximating, 449

Integrated development environments (IDEs), 3

Integration, definite, 816

Interactions between modules, 319

Interactive user input, 135–136

Interface construct, 446

Interfaces

APIs, 430

built-in, 451

defining, 446

functional, 450

implementing, 447

using, 447–448

Internet DNS, 629–630

Internet Protocol (IP), 435

Interpolation in fade effect, 351

Interpreters, 589

IntOps program, 23

Invariants in assertions, 467

Inverse permutations, 122

Inverting functions, 536–538

Invoking instance methods, 334

IP (Internet Protocol), 435

IPv4, 435

IPv6, 435

ISBN (International Standard Book Number), 86

Isolated vertices in graphs, 703

Isomorphic binary trees, 661

Items in collections, 566

Iterable interface, 451, 602

Iterable collections, 601–605

arrays, 603

linked lists, 604–605

Queue, 604–605

SET, 652

Stack, 603

Iterated function systems, 239–243

Iterations in BSTs, 650

Iterator interface, 451, 602–605

J

Java command, 3, 134

.java extension, 3, 6, 8, 197, 383

Java language

benefits, 9

overview, 1–8

Java platform, 2

Java virtual machines, 3, 429

Josephus problem, 619

Julia sets, 427

K

K-ring graphs, 694–695

Kamasutra ciphers, 377

Kevin Bacon game, 684–686

Key-sorted tree traversal, 649

Keys

BSTs, 640–642, 650

immutable, 625

Kamasutra ciphers, 377

symbol tables, 624–626, 655

Key–value pairs, 624–626

Knuth, Donald

optimization, 518

running time, 496, 501

Koch program, 397

L

Ladders, word, 710

Lambda expressions, 450

Last-in first-out (LIFO), 566–567

Lattices in random walks, 112–115

LCS (longest common subsequence), 285–288

Leaf nodes in BSTs, 640

Leaks, memory, 367, 581

LeapYear program, 28–29

Left associativity, 17

Left subtrees, 640

Length

arrays, 91–92

graph paths, 674, 683

strings, 332

Less than signs (<)

comparisons, 27–29

redirection, 140–141

Let’s Make a Deal simulation, 88

Libraries

APIs, 230–232

array I/O, 237–238

clients, 230

extensible, 452

methods, 29–32

modifying, 255

in modular programming, 227–228, 251–254

modules, 191

overview, 226, 230

random numbers, 232–236

statistics, 244–250

stress testing, 236

unit testing, 235

LIFO (last-in first-out), 566–567

Linear algebra for vectors, 442–443

Linear interpolation, 351

Linear order of growth, 504–505, 507–508

Linearithmic order of growth, 504–505, 507–508

Linked lists

circular, 622

FIFO queues, 593, 596

hash tables, 636

iterable classes, 604–605

overview, 571–574

stacks, 574–576

summary, 578

symbol tables, 635

traversal, 574, 577

Linked structures. See Binary search trees (BSTs)

LinkedStackOfStrings program, 574–576

Links in BSTs, 640–642

Lipton, R. J., 856

Lissajous, Jules A., 168

Lissajous patterns, 168

Lists, linked. See Linked lists

Literals

array elements, 116

booleans, 26

characters, 18–19

description, 15

floating-point numbers, 24

integers, 22

strings, 19, 334

Little’s law, 598

LoadBalance program, 606–607

Local clustering, 693–694

Local variables

vs. instance variables, 384

static methods, 196

Logarithmic order of growth, 503

Logarithmic spirals, 398–399

Logo language, 400

Loitering condition, 581

Long data type, 24, 513

Longest common subsequence (LCS), 285–288

LongestCommonSubsequence program, 286–288

Lookup program, 630–632

Loops. See Conditionals and loops

Luminance, 343–345

Luminance program, 344–345

M

M/M/1 queues, 597–600

MAC addresses, 877

Magnitude

complex numbers, 402–403

spatial vectors, 442–443

Magritte, René, 363

main() methods, 4–5

multiple, 229

transfer of control, 193–194

Mandelbrot, Benoît, 297, 406

Mandelbrot program, 406–409

Maps, Mercator projections, 48

Markov, Andrey, 176

Markov chains

impact, 184

mixing, 179–184

overview, 176

power method, 180–181

squaring, 179–180

Markov model paradigm, 460

Markov program, 180–182

Markovian queues, 597

Marsaglia’s method, 85, 259

Matching graphs, 713

Math library, 192

accessing, 228

methods, 30–32, 193, 198

Mathematical analysis, 498–502

Mathematical functions, 202–204

Mathematical induction, 262, 266

Matlab language, 717

Matrices

boolean, 302

Hadamard, 122

images, 346–347

matrix multiplication, 109

sparse, 666

transition, 172–173

two-dimensional arrays, 106, 109–110

vector multiplication, 110, 180

Maximum keys in BSTs, 651

Maximum values in arrays, 209

Maxwell–Boltzmann distributions, 257

McCarthy’s 91 function, 298

Mechanical systems, graphs for, 673

Memoization, 284

Memory

arrays, 91, 94, 515–517

ArrayStackOfStrings, 569–570

available, 520

interfaces, 1054

leaks, 367, 581

linked lists, 571

memory bits, 1056

objects, 338, 514

performance, 513–517

recursion, 282

references, 367

safe pointers, 366

strings, 515

two-dimensional arrays, 107

Memoryless queues, 597

Mercator projections, 48

Merge program, 550–552

Mergesort

divide-and-conquer, 554

overview, 550–552

performance, 553

Method references, 470

Methods

abstract, 446

call chaining, 404

deprecated, 469

instance, 334, 385–386

instance vs. static, 340

library, 29–32

main(), 4–5

overriding, 452

static. See Functions; Static methods

stub, 303

variables within, 386–388

MIDI Tuning Standard, 161

Midpoint displacement method, 278, 280

Milgram, Stanley, 670

Minimum keys in BSTs, 651

Minus signs (-)

compound assignments, 60

floating-point numbers, 24–26

integers, 22

lambda expressions, 450

MIX machine, 947

Mixed-type operators, 27–29

Mixing Markov chains, 176, 179–184

MM1Queue program, 598–600

Modular programming, 191

classes in, 227–229

code reuse, 226, 253

debugging, 253

encapsulation, 432

flow of control in, 227–228

libraries in, 251–254

maintenance, 253

program size, 252–253

Modules

as classes, 228

CPU, 1076

interactions, 319

overview, 191

size, 319

summary, 254

Monochrome luminance, 343–344

Monte Carlo simulation, 300, 307–308

Moore’s law, 507–508

Move-to-front strategy, 620

Movie–performer graph, 680

Multidimensional arrays, 111

Multiple arguments, 197

Multiple inheritance, 470

Multiple main() methods, 229

Multiple return statements, 198

Multiple I/O streams, 143

Multiplication

complex numbers, 402–403

floating-point numbers, 24–26

integers, 22–23

matrices, 109–110

polar representation, 433

Music, 155–159

Mutable types, 364, 439

N

n-body simulation

Body data type, 479–480

file format, 483

force, 480–482

overview, 478–479

summary, 488

Universe data type, 483–487

Names

arrays, 91

methods, 5, 30, 196

objects, 362

variables, 16

vertices, 675

NaN value, 26, 40

Natural recursion, 262

Negative numbers

array indexes, 116

representing, 38

Neighbor vertices, 671

Nested classes

iterators, 574

linked lists, 603–605

Nesting conditionals and loops, 62–64

new keyword

constructors, 385

Node objects, 609

String objects, 333

Newcomb, Simon, 224

Newline characters ( )

compiler considerations, 10

escape sequences, 19

Newton, Isaac

dice question, 88

motion simulation, 478–479

square root method, 65

Newton’s law of gravitation, 481

Newton’s method, 65–67

Newton’s second law of motion, 480–481

90–10 rule, 170, 176

Nodes

BSTs, 640–642

linked lists, 571–573

new keyword, 609

Nondominant inner loops, 510

Normal distribution functions

cumulative, 202–203

probability density, 202–203

Not operation, 26–27

Null calls, 312

Null keys in symbol tables, 626

Null links in BSTs, 640

Null nodes in linked lists, 571–572

null keyword, 415

Null values in symbol tables, 626

NullPointerException, 370

Number conversions, 21, 67–69

Numerical integration, 449

Nyquist frequency, 161

O

Object class, 453–455

Object-oriented programming

data types. See Data types

description, 254

overview, 329

Objects

arrays, 365

collections, 582–583

comparing, 364, 545–546

Complex, 404

equality, 454–456

memory, 514

names, 362

orphaned, 366

references, 338–339

String, 333–334

type conversions, 339

uninitialized variables, 339

working with, 338–339

Observations, 495–496

Off-by-one errors, 92

Offscreen canvas, 151

One-dimensional arrays, 90

Onscreen canvas, 151

Opcodes, 911

Operands, 17

Operators and operations

boolean, 26–27

comparisons, 27–29, 364

compound assignments, 60

data types, 14, 331

description, 15

expressions, 17, 587

floating-point numbers, 24

integers, 22, 891

lambda, 450

overloading, 416

precedence, 17

reverse Polish notation, 590

stacks, 590

strings, 19, 21, 334, 453

Optimization, 518

Or operation, 26–27

Order in BSTs, 640, 642–643

Order-of-growth classifications

constant, 503

cubic, 505–508

exponential, 505–508

linear, 504–505, 507–508

linearithmic, 504–505, 507–508

logarithmic, 503

overview, 503

performance analysis, 500–501

quadratic, 504–505, 507–508

Order statistics, 651

Ordered operations

binary search trees, 651

symbol tables, 624

Orphaned objects, 366

Orphaned stack items, 581

Out library, 355–356

Outer loops, 62

Outline shapes, 149

Output

array libraries, 237–238

clocks, 1059–1060

data types, 353

file concatenation, 356

gates, 1013

print statements, 8

printf() method, 126–129

standard, 127, 129–132

standard audio, 155–159

standard drawing. See Standard drawing

stream data types, 355

two-dimensional arrays, 107

Overflow

arrays, 95

attacks, 963

integers, 23

negative numbers, 38

Overhead for objects, 514

Overloading

operators, 416

static methods, 198

Overriding methods, 452

P

Padding object memory, 514

Page, Lawrence, 184

Page ranks, 176–177

Palindromes, 374

Paper size, 294

Papert, Seymour, 400

Parallel arrays, 411

Parallel edges, 676

Parameter variables

lambda expressions, 450

static methods, 196–197, 207

Parameterized data types, 582–586

Parentheses ()

casts, 33

constructors, 333, 385

expressions, 17, 27

functions, 24, 197

lambda expressions, 450

methods, 30, 196

operator precedence, 17

stacks, 587, 590

static methods, 196

vectors, 442

Pascal’s triangle, 125

Passing arguments

references by value, 364–365

static methods, 207–210

PathFinder program, 683–686, 690–692

Paths

graphs, 674, 683–692

shortest. See Shortest paths

simple, 710

Peaks in terrain analysis, 167

Pell’s equation, 869

Pens

color, 150

drawings, 146

Pepys, Samuel, 88

Pepys problem, 88

Percent signs (%)

conversion codes, 131–132

remainder operation, 22–23

Percolation case study

adaptive plots, 314–318

lessons, 318–320

overview, 300–301

Percolation, 303–304

PercolationPlot, 315–317

PercolationProbability, 310–311

PercolationVisualizer, 308–309

probability estimates, 310–311

recursive solution, 312–314

scaffolding, 302–304

testing, 305–308

vertical percolation, 305–306

Performance

binary search trees, 647–648

binary searches, 535

caveats, 509–511

comparing, 508–509

guarantees, 512, 627

hypotheses, 496–502

importance, 702

insertion sorts, 544–545

memory use, 513–517

mergesort, 553

multiple parameters, 511

order of growth, 503–506

overview, 494–495

perspective, 518

prediction, 507–509

scientific method, 495–502

shortest paths, 690

wrapper types, 369

Performer program, 697–699

Periods (.), classes, 227

Permutations

inverse, 122

sampling, 97–99

Phase transitions, 317

Phone books, 628

Photographs, 346

Physical systems, graphs for, 672

Pi constant, 31–32

Picture library, 346–347

Piecewise approximation, 148

Piping

connecting programs, 141

filters, 142–143

Pixels in image processing, 346

Plasma clouds, 280

PlayThatTune program, 157–158

PlayThatTuneDeluxe program, 213–215

PlotFilter program, 146–147

Plotting

array values, 246–248

experimental results, 249–250

function graphs, 148, 248

percolation case study, 314–318

sound waves, 249

Plus signs (+)

compound assignments, 60

floating-point numbers, 24–26

integers, 22

string concatenation, 19–20

Pointers

array elements, 94

handles, 371

object references, 338

safe, 366

Poisson processes, 597

Polar coordinates, 47

Polar representation, 433–434

Polling, statistical, 167

Polymorphism, 448

Pop operation

reverse Polish notation, 590–591

in stacks, 567–568

Positional notation, 875

Postconditions in assertions, 467

Postfix notation, 590

Postorder tree traversal, 649

PostScript language, 400, 590

PotentialGene program, 336–337

Pound signs (#), 769

Power method, 180–181

Power source, 1003–1004

PowersOfTwo program, 56–58

Precedence of operators, 17

Precision

floating-point numbers, 25, 40

printf(), 130–131

standard output, 129–130

Precomputed array values, 99–100

Preconditions in assertions, 467

Prediction, performance, 507–509

Preferred attachment process, 713

Prefix-free strings, 564

Premature optimization, 518

Preorder tree traversal, 649

Primality-testing function, 198–199

Prime numbers

in factoring, 72–73

Sieve of Eratosthenes, 103–105

PrimeSieve program, 103–105

Primitive data types, 14

memory size, 513

overflow checking, 39

performance, 369

wrappers, 457

Principle of superposition, 483

print() method, 31

arrays, 237–238

impurity, 32

Out, 355

vs. println(), 8

standard output, 129–130

Print statements, 5

printf() method, 129–132, 355

Printing, formatted, 130–132

println() method, 31

description, 5

impurity, 32

Out, 355

vs. print(), 8

standard output, 129–130

string concatenation, 20

private keyword

access modifier, 384

encapsulation, 433

Probabilities, 308, 310–311

Probability density function, 202–203

Procedural programming style, 329

Program size, 252–253

Programming languages

indexing, 634

stack-based, 590

symbol tables, 629

Programming overview, 1

HelloWorld example, 4–6

input and output, 7–8

process, 2–3

public keyword

access modifiers, 384

description, 228

static methods, 196

Pure functions, 201

Pure methods, 32

Push operation

reverse Polish notation, 590–591

stacks, 567–568

Put operations

hash tables, 639

symbol tables, 624

Q

Quad play, 273

Quadratic order of growth, 504–505, 507–508

Quadratic program, 25–26

Quadrature integration, 449

Quaternions, 424

Questions program, 533–535

Queue program, 592–596, 604–605

Queues

circular, 620

deques, 618

FIFO. See First-in first-out (FIFO) queues

overview, 566

random, 596

summary, 608

Queuing theory, 597–600

Quotes (“) in text, 5

R

Ragged arrays, 111

Ramanujan, Srinivasa, 86

Ramanujan’s taxi, 86

Random graphs, 695

Random numbers

fair coin flips, 52–53

function implementation, 199

Gaussian, 47

impurity, 32

libraries, 232–236

Math.random(), 30–31

random sequences, 127–128

Sierpinski triangles, 239–240

simulations, 72–73

Random queues, 596

Random shortcuts, 699

Random walks

Brownian bridges, 278

self-avoiding, 112–115

two-dimensional, 86

undirected graphs, 712

Random web surfer case study

histograms, 177

input format, 171

lessons, 184–185

Markov chains, 176, 179–184

overview, 170–171

page ranks, 176–177

simulation, 174–178

transition matrices, 172–173

RandomInt program, 33–34

RandomSeq program, 127–128

RandomSurfer program, 175–177

RangeFilter program, 140–143

Ranges

binary search trees, 651

functions, 192

Ranks

binary search trees, 651

random web surfer, 176–177

Raphson, Joseph, 65

Raster images, 346

Recomputation, 282–283

Rectangle rule, 449

Recurrence relations, 272

Recursion, 191

base cases, 281

binary searches, 533

Brownian bridges, 278–280

BSTs, 640–641, 644, 649

considering, 320

convergence issues, 281–282

dynamic programming, 284–289

Euclid’s algorithm, 267–268

exponential time, 272–273

factorial example, 264–265

function-call trees, 269, 271

graphics, 276–277, 397

Gray codes, 273–275

linked lists, 571

mathematical induction, 266

memory requirements, 282

mergesort, 550

overview, 262–263

percolation case study, 312–314

perspective, 289

pitfalls, 281–283

recomputation issues, 282–283

towers of Hanoi, 268–272

Red–black trees, 648

Redirection, 139

piping, 142–143

standard input, 140–141

standard output, 139–140

Reduction

binary search trees, 640

mergesort, 554

recursion, 264–265

References

accessing, 339

aliasing, 363

arrays, 365

equality, 454–455

garbage collection, 367

immutable types, 364, 441

linked lists, 572

memory, 367

method, 470

object-oriented programming, 330

objects, 338–339

orphaned objects, 366

passing, 207, 210, 364–365

performance, 369

properties, 362–363

safe pointers, 366

Reflexive property, 454

Relative entropy, 667–668

Remainder operation, 22–23

Removing

array items, 569

collection items, 566, 602–603

linked list items, 573–574

queue items, 592, 596

set keys, 652

stack items, 567–569

symbol table keys, 624–627

Repetitive code, simplifying, 100

Representation in APIs, 431

Reproducible experiments, 495

Reserved words, 16

Resizing arrays, 578–581, 635

ResizingArrayStackOfStrings program, 578–581

Resource allocation

graphs for, 673

overview, 606–607

Resource-sharing systems, 606–607

return statements, 194, 196, 198

Return values

arrays as, 210

methods, 30, 196, 200, 207–210

reverse Polish notation, 591

Reuse, code, 226, 253, 701

Reverse Polish notation, 590

RGB color format, 48–49, 341, 371

Riemann integral, 449

Riffle shuffles, 125

Right subtrees, 640

Right triangles, 199

Ring buffers, 620

Ring graphs, 694–695, 699

Roots in binary search trees, 640

Rotation filters, 379

Roulette-wheel selection, 174

Round-robin policies, 606

Rows in 2D arrays, 106, 108

Ruler program, 19–20

Run-time errors, 6

Running time. See Performance

Running virtual machines, 969

RuntimeException, 466

S

Safe pointers, 366

Sample program, 98–99

Sample standard deviation, 246

Sample variance, 244

Sampling

audio, 156–157

function graphs, 148

scaling, 349–350

without replacement, 97–99

Saving audio files, 157

Scaffolding, 302–304

Scale program, 349–350

Scaling

drawings, 146

image processing, 349–350

spatial vectors, 442–443

Scientific method, 494–495

hypotheses, 496–502

observations, 495–496

Scientific notation, 131–132

Scope of variables, 60, 200

Screen scraping, 357–359

Searches

binary. See Binary searches

binary search trees. See Binary search trees (BSTs)

bisection, 537

breadth-first, 683, 687–692

data mining example, 458–464

depth-first, 312, 690

indexing, 634

overview, 532

for similar documents, 464

Secret messages, 992

Seeds for random numbers, 475

Select control lines, 1056

Self-avoiding walks, 112–115, 710

Self-loops for edges, 676

SelfAvoidingWalk program, 112–115

Semantics, 52

Semicolons (;)

for loops, 59

statements, 5

Sequential searches, 535–536

Servers, 606

Service rate, 597–598

SET library, 652–653

Sets

gates, 1045

graphs, 676

Julia, 427

Mandelbrot, 406–409

overview, 652–653

of values, 14

Shadow variables, 419

Shannon entropy, 378

Shapes, outline and filled, 149

short data type, 24

Shortcuts in ring graphs, 699

Shortest paths

adjacency-matrix, 692

breadth-first searches, 690

degrees of separation, 684–686

distances, 687–688

graphs, 674, 683

implementation, 691

performance, 690

single-source clients, 684

trees, 688–689

Shuffling arrays, 97

Sicherman dice, 259

Side effects

arrays, 208–210

assertions, 467

importance, 217

methods, 32, 126, 201

Sierpinski triangles, 239–240

Sieve of Eratosthenes, 103–105

Signatures

constructors, 385

methods, 30, 196

overloading, 198

Similarity measures, 462

Simple paths, 710

Simulations

coupon collector, 174–178

dice, 121

gambler’s ruin, 69–71

Let’s Make a Deal, 88–89

load balancing, 606–607

M/M/1 queues, 598–600

Monte Carlo, 300, 307–308

n-body. See n-body simulation

random web surfer, 174–178

Single-line comments, 5

Single quotes (’), 19

Singly linked lists, 571

Six degrees of separation, 670

Size

arrays, 578–581, 635

binary search trees, 651

modules, 319

paper, 294

problems, 495, 824

program, 252–253

symbol tables, 624

Sketch program, 459–462

Sketches

comparing, 462–463

computing, 459–460

hashing, 460

overview, 458–459

Slashes (/)

comments, 5

floating-point numbers, 24–26

integers, 22–23

Small-world case study. See Graphs

Small-world phenomenon, 670, 693

SmallWorld program, 696

Smith–Waterman algorithm, 286

Social network graphs, 672

Sorts

Arrays.sort(), 559

frequency counts, 555–557

insertion, 543–549

lessons, 558

mergesort, 550–555

overview, 532

Sound. See Standard audio

Sound waves

plotting, 249

superposition of, 211–215

Source vertices, 683

Space-filling curves, 425

Spaces, 10

Space–time tradeoff, 99–100

Sparse matrices, 666

Sparse small-world graphs, 693

Sparse vectors, 666

Spatial vectors, 442–445

Specification problem

APIs, 430

programs, 596

Speed

clocks, 1058

in performance, 507–508

Spider traps, 176

Spira mirabilis, 398

Spiral program, 398–399

Spirographs, 167

Split program, 358, 360

Spreadsheets, 108

Sqrt program, 65–67

Square brackets ([])

one-dimensional arrays, 91

two-dimensional arrays, 106

Square roots

computing, 65–67

double value, 25

Squares, Albers, 341–342

Squaring Markov chains, 179–180

ST library, 625–627

Stack program, 583–585

StackOfStrings program, 568

StackOverflowError, 282

Stacks

arithmetic expression evaluation, 586–589

arrays, 568–570, 578–581

function calls, 590–591

linked lists, 574–576

overview, 566

parameterized types, 582–586

pushdown, 567–568

stack-based languages, 590

summary, 608

Standard audio

concert A, 155

description, 126, 128–129

music example, 157–158

notes, 156

overview, 155

sampling, 156–157

saving files, 157

summary, 159

Standard deviation, 246

Standard drawing

control commands, 145–146

description, 126, 128–129

double buffering, 151

filtering data to, 146–147

function graphs, 148

outline and filled shapes, 149

overview, 144–145

summary, 159

text and color, 150

Standard input

arbitrary size, 137–138

description, 126, 128–129

formatted, 135

interactive, 135–136

multiple streams, 143

overview, 132–133

redirecting, 140–141

summary, 159

typing, 134

Standard output

description, 127

formatted, 130–132

multiple streams, 143

overview, 129–130

piping, 141–143

redirecting, 139–140

summary, 159

Standard statistics, 244–250

Standards, API, 429

Start codons, 336

Statements

assignment, 17

blocks, 50

declaration, 15–16

methods, 5

States, 340

Static methods, 191–192

accessing, 227–229

arguments, 197

for code organization, 205–206

control flow, 193–195

defining, 193, 196

function-call traces, 195

function calls, 197

implementation examples, 199

vs. instance, 340

libraries. See Libraries

overloading, 198

passing arguments, 207–210

returning values, 207–210

side effects, 201

summary, 215

superposition example, 211–215

terminology, 195–196

variable scope, 200

Static variables, 284

Statistical polling, 167

Statistics, 244–250

StdArrayIO library, 237–238

StdAudio library, 128–129, 155

StdDraw library, 128–129, 144–145, 150, 154

StdIn library, 128–129, 132–133

StdOut library, 129–131

StdRandom program, 232–236

StdStats program, 244–247

StockAccount program, 410–413

StockQuote program, 358–359

Stop codons, 336

Stopwatch program, 390–391

Streams

input, 354–355

output, 355

screen scraping, 357–359

Stress testing, 236

Strings and String data type

API, 332–333

circular shifts, 375

concatenation, 19–20

conversion codes, 131–132

conversions, 21, 453

description, 14–15

genomics application, 336–340

immutable types, 439–440

input, 133

internal storage, 37

invoking instance methods, 334

memory, 515

objects, 333–334

overview, 331

prefix-free, 564

as sequence of characters, 19

shortcuts, 334–335

unions, 723

variables, 333

vertices, 675

working with, 19–21

Strogatz, Stephen, 670, 693, 713

Stub methods, 303

Subclassing inheritance, 452–457

Subgraphs, induced, 705

Subtraction

floating-point numbers, 24–26

integers, 22

Subtrees, 640, 651

Subtyping inheritance, 446–451

Sum-of-powers conjecture, 89

Sums, finite, 64–65

Superclasses, 452

Superposition

force vectors, 483

sound waves, 211–215

Swirl filters, 379

switch statements, 74–75

Symbol tables

APIs, 625–627

BSTs. See Binary search trees

dictionary lookup, 628–632

graphs, 676

hash tables, 636–639

implementations, 635–636

indexing, 632–634

overview, 624–625

perspective, 654

sets, 652–653

Symmetric order in BSTs, 640

Symmetric property, 454

Syntax errors, 10–11

T

Tables

hash, 636–639

symbol. See Symbol tables

Tabs

compiler considerations, 10

escape sequences, 19

Taylor series approximations, 204

Templates, 50

TenHellos program, 54–55, 60

Terminal windows, 127

Terms, glossary for, 721–726

Terrain analysis, 167

Testing

for bugs, 318

importance, 701

percolation case study, 305–308

Text. See also Strings and String data type

drawings, 150

printing, 5, 10

Text editors, 3

this keyword, 445

3n+1 problem, 296–297

ThreeSum program, 497–502

Throwing exceptions, 465–466

Tilde notation, 500

Time

exponential, 272–273

performance. See Performance

Stopwatch timers, 390–391

TimePrimitives program, 519

Tools, building, 320

Top-level domains, 375

toString() method

Charge, 383, 387

Color, 343

Complex, 403, 405

Counter, 436–437

description, 339

Graph, 678–679

linked lists, 574, 577

Object, 453

Sketch, 459

Tape, 776

Vector, 443

Total orderings, 546

Totality problem, 811–812

Towers of Hanoi problem, 268–272

Tracing

function-call, 195

programs with random(), 103

variable values, 18, 56–57

Transfer of control, 193–195

Transition matrices, 172–173

Transition program, 172–173

Transitive property

comparisons, 546

equivalence, 454

Transposition of arrays, 120

Traversal

binary search trees, 649–650

linked lists, 574, 577

Tree nodes, 269

TreeMap library, 655

Trees

BSTs. See Binary search trees

function-call, 269, 271

H-trees, 276–277

shortest paths, 688–689

Triangles

drawing, 144–145

right, 199

Sierpinski, 239–240

Trigonometric functions, 256

Truth tables, 26–27

Turing, Alan, 410–411

Turtle program, 394–396

Twenty questions game, 135–136, 533–535

TwentyQuestions program, 135–136

Two-dimensional arrays

description, 90

initialization, 106–107

matrices, 109–110

memory, 107, 516

output, 107

overview, 106

ragged, 111

self-avoiding walks, 112–115

setting values, 108

spreadsheets, 108

Two’s complement, 38

Type arguments, 585, 611

Type conversions, 34–35

Type parameters, 585

Type safety, 18

Types. See Data types

U

Unboxing, 457, 585–586

Undirected graphs, 675

Unicode characters

description, 19

strings, 37

Uniform random numbers, 199

Uninitialized variables, 94, 339

Unit testing, 235

Universe program, 483–487

Unreachable code error, 216

Unsolvable problems, 430

Upscaling in image processing, 349

UseArgument program, 7–8

User-defined libraries, 230

V

Values

array, 95–96

data types, 14, 331

passing arguments by, 207, 210, 364–365

precomputed, 99–100

symbol tables, 624–626

Variables

assignment statements, 17

compound assignments, 60

constants, 16

description, 15–16

initial values, 415

inline initialization, 18

instance, 384

within methods, 196, 386–388

names, 16

scope, 60, 200

shadow, 419

static, 284

string, 333

tracing values, 18

uninitialized, 339

Vector images, 346

Vector program, 443–445, 515

Vectors

arrays, 92

cross products, 472

dot products, 92, 442–443

matrix–vector multiplication, 110

n-body simulation, 479–480

sparse, 666

spatial, 442–445

vector–matrix multiplication, 110, 180

Vertical bars (|)

boolean type, 26–27

piping, 141

Vertical percolation, 305–306

Vertices

bipartite graphs, 682

creating, 676

eccentricity, 711

graphs, 671, 674

isolated, 703

names, 675

PathFinder, 683

String, 675

Viterbi algorithm, 286

void keyword, 201, 216

Volatility

Black–Scholes formula, 565

Brownian bridges, 278, 280

Von Neumann, John, 554

Voting machine errors, 436

W

Walks

random. See Random walks

self-avoiding, 112–115, 710

Watson–Crick palindrome, 374

Watts, Duncan, 670, 693, 713

Watts–Strogatz graph model, 713

.wav format, 157

Wave filters, 379

Web graphs, 695

Web pages, 170

indexed searches, 634

preferential attachment, 713

Weighing objects, 540–541

Weighted averages, 120

Weighted superposition, 212

while loops, 53–59

examples, 61

nesting, 62

Whitelists, binary searches for, 540

Whitespace characters

compiler considerations, 10

input, 135

Wide interfaces

APIs, 430

examples, 610–611

Wind chill, 47

Word ladders, 710

Words of memory, 513

Worst-case performance

big-O notation, 520–521

binary search trees, 648

description, 512

insertion sort, 544

Wrapper types

autoboxing, 585–586

references, 369, 457

Y

Y2K problem, 435

Young tableaux, 530

Z

Zero-based indexing, 92

Zero crossings, 164

ZIP codes, 435

Zipf’s law, 556