A-format instructions, 911
Absolute value function, 199
Abstract methods, 446
Abstraction
circuits, 1037–1039
data, 382
displays, 346
object-oriented programming, 329
printing as, 76
recursion, 289
vs. representation, 69
standard audio, 155
standard drawing, 144
Access modifiers, 384
Accessing references, 339
Account information
indexing, 634
Accuracy
n-body simulation, 488
random web surfer, 185
AddInts
program, 134
Addition
integers, 22
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
references, 363
Animations
double buffering, 151
Antisymmetric property, 546
Application programming interfaces (APIs)
access modifiers, 384
Body
, 480
Charge
, 383
Color
, 343
Comparable
, 545
Complex
, 403
data types, 388
Draw
, 361
Histogram
, 392
implementing, 231
In
, 354
modular programming, 432
Out
, 355
PathFinder
, 683
Picture
, 347
Queue
, 592
SET
, 652
Sketch
, 459
ST
, 625
StackOfStrings
, 568
StdArray
, 237
StdAudio
, 159
StdOut
, 130
StdRandom
, 233
StdStats
, 244
StockAccount
, 410
Stopwatch
, 390
Turtle
, 394
Universe
, 483
Vector
, 443
Arbitrary-size input streams, 137–138
methods, 30
static methods, 197
Ariane 5 rocket, 35
Arithmetic expression evaluation, 586–589
Arithmetic operators, 22
ArrayIndexOutOfBoundsException
, 95, 116, 466
Arrays
aliasing, 516
assigning, 117
associative, 630
bitonic, 563
bounds checking, 95
comparing, 117
coupon collector problem, 101–103
default initialization, 93
exchanging values, 96
FIFO queues, 596
hash tables, 636
iterable classes, 6031
multidimensional, 111
parallel, 411
references, 365
as return values, 210
shuffling, 97
Sieve of Eratosthenes, 103–105
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
Assignments
arrays, 117
chained, 43
compound, 60
description, 17
references, 363
Associative arrays, 630
Associativity, 17
Asterisks (*
)
comments, 9
Audio
plotting sound waves, 249
Automatic promotion, 33
Average-case performance, 648
Average magnitude, 164
Average path lengths, 693
Average power, 164
Backslashes (), 19
Bacon, Kevin, 684
Balanced binary trees, 661
Base cases
binary search trees, 640
Beck exploit, 529
Beckett, Samuel, 273
Behavior of objects, 340
Benford’s law, 224
Bernoulli, Jacob, 398
Best-case performance
binary search trees, 647
insertion sort, 544
Binary digits, 22
Binary number system
description, 38
Binary operators, 17
Binary reflected Gray code, 274
Binary search trees (BSTs)
ordered operations, 651
binary representation, 536
correctness proof, 535
exception filters, 540
random web surfer, 176
running time, 535
symbol tables, 635
Binary trees
balanced, 661
heap-ordered, 661
isomorphic, 661
Binomial coefficients, 125
Binomial distributions, 125, 249
Biology
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
Bollobás–Chung graph model, 713
Boole, George, 986
boolean
data type
input, 133
memory size, 513
Boolean logic, 27
Boolean matrices, 302
Bounding boxes for drawings, 146
Bounds of arrays, 95
Box–Muller formula, 47
Breadth-first search, 683, 687–692
break
statements, 74
Brin, Sergey, 184
Brown, Robert, 400
Brute-force algorithm, 535–536
BSTs. See Binary search trees (BSTs)
Buffer overflow, 95
Buffering drawings, 151
Bugs
overview, 6
testing for, 318
Built-in data types
Built-in interfaces, 451
byte
data type, 24
Bytecode, 589
Bytes memory size, 513
Caches
and instruction time, 509
in dynamic programming, 284
Callbacks in event-based programming, 451
Calls, 193
chaining, 404
reverse Polish notation, 591
Canvas, 151
Card decks, arrays for, 97–100
Carroll, Lewis, 710
Cartesian representation, 433
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
Checksums
description, 86
formula, 220
Chords, 211
Chromatic scale, 156
Ciphers, Kamasutra, 377
Circular linked lists, 622
Circular queues, 620
Circular shifts, 375
ClassDefFoundError
, 160
description, 226
inner, 609
modules as, 228
variables, 284
Client code
data types, 430
library methods, 230
Clouds, plasma, 280
Clustering coefficients
global, 713
Code and coding
description, 2
encapsulating, 438
incremental development, 319, 701
Codebooks, 992
Codons, genes, 336
Coercion, 33
Collatz sequence, 948
Collections
description, 566
queues. See Queues
stacks. See Stacks
symbol tables. See Symbol Tables
Color and Color
data type
blobs, 709
compatibility, 344
drawings, 150
grayscale, 344
luminance, 343
memory, 514
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
two-dimensional arrays, 108
Commercial data processing, 410–413
Common sequences, longest, 285–288
Comparable
interface, 451, 545
Comparable keys
sorting, 546
CompareDocuments
program, 462–463
compareTo()
method
description, 451
String
, 332
Comparisons
arrays, 117
chained, 43
Compile-time errors, 6
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
objects, 404
program, 405
Compound assignments, 60
Computer animations, 151
Computer speed in performance, 507–508
Concatenation
files, 356
Concert A, 155
Concordances, 659
Conditionals and loops, 50
break
statement, 74
continue
statement, 74
do
-while
loops, 75
examples, 61
infinite loops, 76
in modular programming, 227–228
performance analysis, 500, 510
summary, 77
Connected components, 709
Connecting programs, 141
Constant order of growth, 503
Constants, 16
Constructors
String
, 333
Containing symbol table keys, 624
continue
statements, 74
Contracts
Control flow
conditionals and loops. See Conditionals and loops
Conversion specifications, 130–131
Conversions
data types, 339
decimal to binary, 877
implicit, 33
overview, 32
Conway, John, 326
Coordinates
images, 347
polar, 47
Corner cases, 236
Cosine similarity measure, 462
Cost of immutable types, 440
Coulomb’s law, 383
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 ({}
)
static methods, 196
two-dimensional arrays, 108
Curves
Koch, 397
space-filling, 425
Cycles per second, 155
Data compression, 814
Data-driven code, 141, 171, 184
Data structures, 493
arrays. See Arrays
binary search trees. See Binary search trees (BSTs)
queues. See Queues
stacks. See Stacks
stock example, 411
summary, 608
symbol tables. See Symbol tables
Data-type design
overview, 428
Data types
access modifiers, 384
APIs, 383
built-in. See Built-in data types
classes, 383
creating, 382
elements summary, 383
instance variables, 384
Koch
, 397
output, 355
overview, 330
String
. See Strings and String data type
summary, 368
type safety, 18
variables within methods, 386–388
Dead Sea Scrolls, 659
Debugging
encapsulation for, 432
immutable types, 440
linked lists, 596
test client main()
for, 235
unit testing, 246
Decimal number system, 38
Declaring
String
variables, 333
Default values
canvas size, 145
ink color, 150
instance variables, 415
Node
objects, 572
pen radius, 146
Defensive copies, 441
Defining
functions, 192
interfaces, 446
Definite integration, 816
Degrees of separation
description, 670
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
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
overview, 346
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
Division
polar representation, 433
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
Double buffering drawings, 151
double
data type
conversion codes, 132
input, 133
memory size, 513
Double.parseDouble()
method
Double quotes (""
)
escape sequences, 19
Doublet game, 710
Doubling hypotheses, 496, 498–499
DoublingTest
program, 496, 498–499
Downscaling in image processing, 349
Dragon
program, 163
Draw
library, 361
Drawings
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
Eccentricity in vertices, 711
Edges
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
Element distinctness problem, 554
Elements in arrays, 90
Encapsulation
code clarity, 438
modular programming, 432
overview, 432
planning for future, 435
private access modifier, 433
End-of-file sequence, 137
Entropy
Shannon, 378
Equality of objects, 364, 454–456
equals()
method
Color
, 343
String
, 332
Equals signs (=
)
assignment statements, 17
assignment vs. boolean, 42, 78
compound assignments, 60
Equilateral triangles, 144–145
Erdös, Paul, 686
Errors
aliasing, 363
debugging. See Debugging
overview, 6
testing for, 318
Escape sequences, 19
Euclidean distance
vectors, 118
Euclid’s algorithm
description, 85
Euler, Leonhard, 89
Euler’s constant, 222
Euler’s sum-of-powers conjecture, 89
Euler’s totient function, 222
Evaluating expressions, 17, 586–589
Event-based programming, 451
Exception
class, 465
Exception filters, 540
Exchanging values
arrays, 96
function implementation, 209
Exclamation points (!
)
Exponential distributions, 597
Exponential order of growth, 505
Expressions
arithmetic evaluation, 586–589
description, 17
lambda, 450
method calls, 30
Extensible libraries, 452
Falsifiable hypotheses, 495
Fecundity parameter, 89
Fermat’s Last Theorem, 89
formulas, 82
FIFO queues. See First-in first-out (FIFO) queues
Files
concatenating and filtering, 356
format, 237
in I/O, 126
n-body simulation, 483
splitting, 360
stock example, 411
symbol tables, 629
Filled shapes, 149
Filters
exception, 540
files, 356
image processing, 379
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
First-in first-out (FIFO) queues
applications overview, 597
array implementation, 596
linked-list implementation, 593
Flexibility, 702
Floating-point numbers
precision, 40
storing, 40
Flow of control
conditionals and loops. See Conditionals and loops
for
loops
continue
statement, 74
examples, 61
Format, files, 237
Formatted input, 135
Forth language, 590
Fortran language, 717
Fourier series, 211
Fractal dimensions, 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
static methods, 197
traces, 195
Functional interfaces, 450
Functional programming, 449
Functions
computing with, 449
defining, 192
iterated function systems, 239–243
libraries. See Libraries
modules. See Modules
overview, 191
recursive. See Recursion
Gambler’s ruin simulation, 69–71
Game of Life, 326
Gardner, Martin, 424
Gaussian distribution functions
API, 231
Gaussian elimination, 830
Gaussian
program, 203
Gaussian random numbers, 47
Genomics
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
Golden ratio, 83
Gore, Al, 436
Graph
program, 677
Graphics
Graphs
bipartite, 682
connected components, 709
dependency, 252
description, 671
diameters, 711
directed, 711
examples, 695
generators, 700
grid, 708
matching, 713
random web surfer, 170
Gravity, 481
Grayscale
Color
, 344
Greater than signs (>
)
lambda expressions, 450
Greatest common divisor, 267–268
Grid graphs, 708
Hadamard matrices, 122
Hamilton, William, 424
Hamming distances, 295
Handles for pointers, 371
Hardy, G. H., 86
Harmonic mean, 162
Harmonic numbers
function implementation, 199
Harmonics and chords, 211
Hash codes and hashing operation
sketches, 460
strings, 515
symbol tables, 624
Hash functions, 636
Hash values, 636
Hashable keys, 626
hashCode()
method
String
, 332
HashMap
class, 655
Heap memory, 516
Heap-ordered binary trees, 661
Height in binary search trees, 640
Hertz, 155
Hilbert, David, 425
Hilbert curves, 425
Histograms, 177
Hoare, C. A. R., 518
Hollywood numbers, 711
Horner’s method, 223
Hurst exponent, 280
Hyperbolic functions, 256
Hyperlinks, 170
Hypotenuse of right triangles, 199
Hypotheses
falsifiable, 495
mathematical analysis, 498–502
overview, 496
I/O. See Input; Output
Identities of objects, 338, 340
IEEE 754 standard, 40
if
statements
nesting, 62
IllegalFormatConversionException
, 131
advantages, 440
cost, 440
final modifier, 440
references, 441
Implementation
API methods, 231
interfaces, 447
Implements clause, 447
Implicit type conversions, 33
Incremental development, 319, 701
String
, 332
zero-based, 92
Induced subgraphs, 705
Induction
recursion step, 266
Infinite loops, 76
Information content of strings, 378
Inheritance
multiple, 470
Initialization
array, 93
inline, 18
instance variables, 415
two-dimensional array, 106–107
Inline variable initialization, 18
Inner classes, 609
Inner loops
description, 62
Inorder tree traversal, 649
Input
clocks, 1060
command-line arguments, 7
data types, 353
file concatenation, 356
gates, 1013
in performance, 510
random web surfer, 171
InputMismatchException
, 135
Inserting
Insertion sorts
InsertionDoublingTest
program, 548–549
Instance methods
invoking, 334
vs. static, 340
Instance variables
data types, 384
initial values, 415
Instances of objects, 333
Integer.parseInt()
method
Integers and int
data type
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
Internet Protocol (IP), 435
Interpolation in fade effect, 351
Interpreters, 589
IntOps
program, 23
Invariants in assertions, 467
Inverse permutations, 122
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
arrays, 603
SET
, 652
Stack
, 603
Iterated function systems, 239–243
Iterations in BSTs, 650
Iterator
interface, 451, 602–605
.java
extension, 3, 6, 8, 197, 383
Java language
benefits, 9
Java platform, 2
Josephus problem, 619
Julia sets, 427
Kamasutra ciphers, 377
Key-sorted tree traversal, 649
Keys
immutable, 625
Kamasutra ciphers, 377
Knuth, Donald
optimization, 518
Koch
program, 397
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
Left associativity, 17
Left subtrees, 640
Length
strings, 332
Less than signs (<
)
Let’s Make a Deal simulation, 88
Libraries
clients, 230
extensible, 452
modifying, 255
in modular programming, 227–228, 251–254
modules, 191
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
hash tables, 636
summary, 578
symbol tables, 635
Linked structures. See Binary search trees (BSTs)
LinkedStackOfStrings
program, 574–576
Lipton, R. J., 856
Lissajous, Jules A., 168
Lissajous patterns, 168
Lists, linked. See Linked lists
Literals
array elements, 116
booleans, 26
description, 15
floating-point numbers, 24
integers, 22
Little’s law, 598
Local variables
vs. instance variables, 384
static methods, 196
Logarithmic order of growth, 503
Logo language, 400
Loitering condition, 581
Longest common subsequence (LCS), 285–288
LongestCommonSubsequence
program, 286–288
Loops. See Conditionals and loops
MAC addresses, 877
Magnitude
Magritte, René, 363
multiple, 229
Maps, Mercator projections, 48
Markov, Andrey, 176
Markov chains
impact, 184
overview, 176
Markov model paradigm, 460
Markovian queues, 597
Matching graphs, 713
Math
library, 192
accessing, 228
Mathematical analysis, 498–502
Mathematical functions, 202–204
Mathematical induction, 262, 266
Matlab language, 717
Matrices
boolean, 302
Hadamard, 122
matrix multiplication, 109
sparse, 666
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
available, 520
interfaces, 1054
linked lists, 571
memory bits, 1056
recursion, 282
references, 367
safe pointers, 366
strings, 515
two-dimensional arrays, 107
Memoryless queues, 597
Mercator projections, 48
Mergesort
divide-and-conquer, 554
performance, 553
Method references, 470
Methods
abstract, 446
call chaining, 404
deprecated, 469
instance vs. static, 340
overriding, 452
static. See Functions; Static methods
stub, 303
MIDI Tuning Standard, 161
Midpoint displacement method, 278, 280
Milgram, Stanley, 670
Minimum keys in BSTs, 651
Minus signs (-
)
compound assignments, 60
integers, 22
lambda expressions, 450
MIX machine, 947
Mixing Markov chains, 176, 179–184
Modular programming, 191
debugging, 253
encapsulation, 432
maintenance, 253
Modules
as classes, 228
CPU, 1076
interactions, 319
overview, 191
size, 319
summary, 254
Monte Carlo simulation, 300, 307–308
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
polar representation, 433
n-body simulation
file format, 483
summary, 488
Names
arrays, 91
objects, 362
variables, 16
vertices, 675
Natural recursion, 262
Negative numbers
array indexes, 116
representing, 38
Neighbor vertices, 671
Nested classes
iterators, 574
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
square root method, 65
Newton’s law of gravitation, 481
Newton’s second law of motion, 480–481
Nodes
new
keyword, 609
Nondominant inner loops, 510
Normal distribution functions
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
Numerical integration, 449
Nyquist frequency, 161
Object-oriented programming
data types. See Data types
description, 254
overview, 329
Objects
arrays, 365
Complex
, 404
memory, 514
names, 362
orphaned, 366
type conversions, 339
uninitialized variables, 339
Off-by-one errors, 92
Offscreen canvas, 151
One-dimensional arrays, 90
Onscreen canvas, 151
Opcodes, 911
Operands, 17
Operators and operations
compound assignments, 60
description, 15
floating-point numbers, 24
integers, 22, 891
lambda, 450
overloading, 416
precedence, 17
reverse Polish notation, 590
stacks, 590
Optimization, 518
Order-of-growth classifications
constant, 503
linearithmic, 504–505, 507–508
logarithmic, 503
overview, 503
Order statistics, 651
Ordered operations
binary search trees, 651
symbol tables, 624
Orphaned objects, 366
Orphaned stack items, 581
Outer loops, 62
Outline shapes, 149
Output
clocks, 1059–1060
data types, 353
file concatenation, 356
gates, 1013
print statements, 8
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
Padding object memory, 514
Page, Lawrence, 184
Palindromes, 374
Paper size, 294
Papert, Seymour, 400
Parallel arrays, 411
Parallel edges, 676
Parameter variables
lambda expressions, 450
Parameterized data types, 582–586
Parentheses ()
casts, 33
lambda expressions, 450
operator precedence, 17
static methods, 196
vectors, 442
Pascal’s triangle, 125
Passing arguments
PathFinder
program, 683–686, 690–692
Paths
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 (%
)
Percolation case study
PercolationProbability
, 310–311
PercolationVisualizer
, 308–309
probability estimates, 310–311
Performance
binary searches, 535
importance, 702
mergesort, 553
multiple parameters, 511
perspective, 518
shortest paths, 690
wrapper types, 369
Periods (.
), classes, 227
Permutations
inverse, 122
Phase transitions, 317
Phone books, 628
Photographs, 346
Physical systems, graphs for, 672
Piecewise approximation, 148
Piping
connecting programs, 141
Pixels in image processing, 346
Plasma clouds, 280
PlayThatTuneDeluxe
program, 213–215
Plotting
percolation case study, 314–318
sound waves, 249
Plus signs (+
)
compound assignments, 60
integers, 22
Pointers
array elements, 94
handles, 371
object references, 338
safe, 366
Poisson processes, 597
Polar coordinates, 47
Polling, statistical, 167
Polymorphism, 448
Pop operation
reverse Polish notation, 590–591
Positional notation, 875
Postconditions in assertions, 467
Postfix notation, 590
Postorder tree traversal, 649
PotentialGene
program, 336–337
Pound signs (#
), 769
Power source, 1003–1004
Precedence of operators, 17
Precision
floating-point numbers, 25, 40
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
Sieve of Eratosthenes, 103–105
Primitive data types, 14
memory size, 513
overflow checking, 39
performance, 369
wrappers, 457
Principle of superposition, 483
print()
method, 31
impurity, 32
Out
, 355
vs. println()
, 8
Print statements, 5
println()
method, 31
description, 5
impurity, 32
Out
, 355
vs. print()
, 8
string concatenation, 20
private
keyword
access modifier, 384
encapsulation, 433
Probability density function, 202–203
Procedural programming style, 329
Programming languages
indexing, 634
stack-based, 590
symbol tables, 629
Programming overview, 1
public
keyword
access modifiers, 384
description, 228
static methods, 196
Pure functions, 201
Pure methods, 32
Push operation
reverse Polish notation, 590–591
Put operations
hash tables, 639
symbol tables, 624
Quad play, 273
Quadratic order of growth, 504–505, 507–508
Quadrature integration, 449
Quaternions, 424
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
Quotes (“) in text, 5
Ragged arrays, 111
Ramanujan, Srinivasa, 86
Ramanujan’s taxi, 86
Random graphs, 695
Random numbers
function implementation, 199
Gaussian, 47
impurity, 32
Random queues, 596
Random shortcuts, 699
Random walks
Brownian bridges, 278
two-dimensional, 86
undirected graphs, 712
Random web surfer case study
histograms, 177
input format, 171
Ranges
binary search trees, 651
functions, 192
Ranks
binary search trees, 651
Raphson, Joseph, 65
Raster images, 346
Rectangle rule, 449
Recurrence relations, 272
Recursion, 191
base cases, 281
binary searches, 533
considering, 320
linked lists, 571
mathematical induction, 266
memory requirements, 282
mergesort, 550
percolation case study, 312–314
perspective, 289
Red–black trees, 648
Redirection, 139
Reduction
binary search trees, 640
mergesort, 554
References
accessing, 339
aliasing, 363
arrays, 365
garbage collection, 367
linked lists, 572
memory, 367
method, 470
object-oriented programming, 330
orphaned objects, 366
performance, 369
safe pointers, 366
Reflexive property, 454
Removing
array items, 569
collection items, 566, 602–603
set keys, 652
Repetitive code, simplifying, 100
Representation in APIs, 431
Reproducible experiments, 495
Reserved words, 16
ResizingArrayStackOfStrings
program, 578–581
graphs for, 673
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
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
Roots in binary search trees, 640
Rotation filters, 379
Roulette-wheel selection, 174
Round-robin policies, 606
Run-time errors, 6
Running time. See Performance
Running virtual machines, 969
RuntimeException
, 466
Safe pointers, 366
Sample standard deviation, 246
Sample variance, 244
Sampling
function graphs, 148
Saving audio files, 157
Scaling
drawings, 146
Searches
binary. See Binary searches
binary search trees. See Binary search trees (BSTs)
bisection, 537
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
Servers, 606
Sets
gates, 1045
graphs, 676
Julia, 427
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
implementation, 691
performance, 690
single-source clients, 684
Shuffling arrays, 97
Sicherman dice, 259
Side effects
assertions, 467
importance, 217
Sieve of Eratosthenes, 103–105
Signatures
constructors, 385
overloading, 198
Similarity measures, 462
Simple paths, 710
Simulations
dice, 121
n-body. See n-body simulation
Single-line comments, 5
Single quotes (’), 19
Singly linked lists, 571
Six degrees of separation, 670
Size
binary search trees, 651
modules, 319
paper, 294
problems, 495, 824
symbol tables, 624
Sketches
hashing, 460
Slashes (/
)
comments, 5
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
lessons, 558
overview, 532
Sound. See Standard audio
Sound waves
plotting, 249
Source vertices, 683
Space-filling curves, 425
Spaces, 10
Sparse matrices, 666
Sparse small-world graphs, 693
Sparse vectors, 666
Specification problem
APIs, 430
programs, 596
Speed
clocks, 1058
Spider traps, 176
Spira mirabilis, 398
Spirographs, 167
Spreadsheets, 108
Square brackets ([]
)
one-dimensional arrays, 91
two-dimensional arrays, 106
Square roots
double
value, 25
Squaring Markov chains, 179–180
StackOfStrings
program, 568
StackOverflowError
, 282
Stacks
arithmetic expression evaluation, 586–589
overview, 566
stack-based languages, 590
summary, 608
Standard audio
concert A, 155
notes, 156
overview, 155
saving files, 157
summary, 159
Standard deviation, 246
Standard drawing
double buffering, 151
function graphs, 148
outline and filled shapes, 149
summary, 159
text and color, 150
Standard input
formatted, 135
multiple streams, 143
summary, 159
typing, 134
Standard output
description, 127
multiple streams, 143
summary, 159
Standards, API, 429
Start codons, 336
Statements
assignment, 17
blocks, 50
methods, 5
States, 340
arguments, 197
for code organization, 205–206
function-call traces, 195
function calls, 197
implementation examples, 199
vs. instance, 340
libraries. See Libraries
overloading, 198
side effects, 201
summary, 215
superposition example, 211–215
variable scope, 200
Static variables, 284
Statistical polling, 167
StdAudio
library, 128–129, 155
StdDraw
library, 128–129, 144–145, 150, 154
StdIn
library, 128–129, 132–133
Stop codons, 336
Streams
output, 355
Stress testing, 236
Strings and String
data type
circular shifts, 375
input, 133
internal storage, 37
invoking instance methods, 334
memory, 515
overview, 331
prefix-free, 564
as sequence of characters, 19
unions, 723
variables, 333
vertices, 675
Strogatz, Stephen, 670, 693, 713
Stub methods, 303
Subclassing inheritance, 452–457
Subgraphs, induced, 705
Subtraction
integers, 22
Subtyping inheritance, 446–451
Sum-of-powers conjecture, 89
Superclasses, 452
Superposition
force vectors, 483
Swirl filters, 379
Symbol tables
BSTs. See Binary search trees
graphs, 676
perspective, 654
Symmetric order in BSTs, 640
Symmetric property, 454
Tables
symbol. See Symbol tables
Tabs
compiler considerations, 10
escape sequences, 19
Taylor series approximations, 204
Templates, 50
Terminal windows, 127
Terrain analysis, 167
Testing
for bugs, 318
importance, 701
percolation case study, 305–308
Text. See also Strings and String
data type
drawings, 150
Text editors, 3
this
keyword, 445
Tilde notation, 500
Time
performance. See Performance
TimePrimitives
program, 519
Tools, building, 320
Top-level domains, 375
toString()
method
Color
, 343
description, 339
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
Transitive property
comparisons, 546
equivalence, 454
Transposition of arrays, 120
Traversal
Tree nodes, 269
TreeMap
library, 655
Trees
BSTs. See Binary search trees
Triangles
right, 199
Trigonometric functions, 256
Twenty questions game, 135–136, 533–535
TwentyQuestions
program, 135–136
Two-dimensional arrays
description, 90
output, 107
overview, 106
ragged, 111
setting values, 108
spreadsheets, 108
Two’s complement, 38
Type parameters, 585
Type safety, 18
Types. See Data types
Undirected graphs, 675
Unicode characters
description, 19
strings, 37
Uniform random numbers, 199
Uninitialized variables, 94, 339
Unit testing, 235
Unreachable code error, 216
Unsolvable problems, 430
Upscaling in image processing, 349
User-defined libraries, 230
Values
passing arguments by, 207, 210, 364–365
Variables
assignment statements, 17
compound assignments, 60
constants, 16
initial values, 415
inline initialization, 18
instance, 384
names, 16
shadow, 419
static, 284
string, 333
tracing values, 18
uninitialized, 339
Vector images, 346
Vectors
arrays, 92
cross products, 472
matrix–vector multiplication, 110
sparse, 666
vector–matrix multiplication, 110, 180
Vertical bars (|
)
piping, 141
Vertices
bipartite graphs, 682
creating, 676
eccentricity, 711
isolated, 703
names, 675
PathFinder
, 683
String
, 675
Viterbi algorithm, 286
Volatility
Black–Scholes formula, 565
Von Neumann, John, 554
Voting machine errors, 436
Walks
random. See Random walks
Watson–Crick palindrome, 374
Watts–Strogatz graph model, 713
.wav
format, 157
Wave filters, 379
Web graphs, 695
Web pages, 170
indexed searches, 634
preferential attachment, 713
Weighted averages, 120
Weighted superposition, 212
examples, 61
nesting, 62
Whitelists, binary searches for, 540
Whitespace characters
compiler considerations, 10
input, 135
Wide interfaces
APIs, 430
Wind chill, 47
Word ladders, 710
Words of memory, 513
Worst-case performance
binary search trees, 648
description, 512
insertion sort, 544
Wrapper types
Y2K problem, 435
Young tableaux, 530
Zero-based indexing, 92
Zero crossings, 164
ZIP codes, 435
Zipf’s law, 556