M

M/M/1 queues, 597–600

MAC addresses, 877

Machine-language programming

arrays, 938–941

benefits, 945

description, 907

functions, 931–933

overview, 930

standard input, 936–938

standard output, 934–936

summary, 945–946

TOY machine, 914

Magnitude

complex numbers, 402–403

spatial vectors, 442–443

Magritte, René, 363

main() methods, 4–5

multiple, 229

transfer of control, 193–194

Majority function

adder circuits, 1028–1030

sum-of-products circuits, 1027

truth tables for, 1025

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

Markov systems, 802–803

Markovian queues, 597

Marsaglia’s method, 85, 259

Masking bitwise operations, 892–893

Matcher class for REs, 763

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

Mathematical models, 716

Matiyasevich, Yuri, 816

Matlab language, 1094

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

Mauchly, John, 924–925

Maximum values in arrays, 209

Maximum keys in BSTs, 651

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

bit-slice design, 1054–1056

circuits, 1054–1057

feedback loops as, 1048

flip-flops, 1049–1050

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

TOY machine, 908–909

two-dimensional arrays, 107

virtual, 972, 975–976

Memory dumps, 909

Memory instructions

address instructions, 912

TOY machine, 913

Memory writes for CPU, 1079

Memoryless queues, 597

Mercator projections, 48

Merge program, 550–552

Mergesort

divide-and-conquer, 554

overview, 550–552

performance, 553

Metacharacters, 724, 730–731

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

Minsky, Marvin, 780, 794

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

Models

circuit. See Circuit models

computational, 716

mathematical, 716

universal, 794–797

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

machine language, 932

maintenance, 253

program size, 252–253

Modules

abstraction layers, 1037

as classes, 228

CPU, 1076

description, 1034

interactions, 319

overview, 191

program counters, 1073

size, 319

summary, 254

Monochrome luminance, 343–344

Monte Carlo simulation, 300, 307–308

Moore’s Law

coping with, 971

description, 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

Multiplexers

bus switching, 1035

description, 1023

selection, 1019–1020

Multiplication

complex numbers, 402–403

floating-point numbers, 24–26

integers, 22–23, 885

matrices, 109–110

P search problems, 839

polar representation, 433

Multiway gates, 1015–1017, 1023

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

NAND function, 989–991

Nash, John, 840

Natural numbers, 875

Natural recursion, 262

Negation axiom, 990

Negative numbers

array indexes, 116

representing, 38, 886–888

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 (\n)

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

NFAs. See Nondeterministic finite-state automata (NFAs)

90–10 rule, 170, 176

Nodes

BSTs, 640–642, 942

linked lists, 571–573

new keyword, 609

Nondeterministic finite-state automata (NFAs)

DFA equivalence, 749–750

Kleene’s theorem. See Kleene’s theorem

overview, 744

RE equivalence, 750–751

recognition problem, 744–745

trace example, 747

Nondominant inner loops, 510

NOR function, 989–991

NOR gates

cross-coupled, 1050

description, 1014

Normal distribution functions

cumulative, 202–203

probability density, 202–203

NOT gates, 1013–1014

Not operation, 26–27, 987–989

NP-completeness

addressing problems, 852

boolean satisfiability, 853–856

classifying problems, 851

Cook–Levin theorem, 844–847

coping, 850–857

Karp’s reductions, 845–848

overview, 843–844

proving, 844–849

NP-hard problems, 858

NP search problems

difficult, 837

easy, 837

main question, 840–841

nondeterminism, 835

overview, 833

solutions, 835

subset sum, 834

TSP problem, 862

vertex cover problem, 834, 842

0/1 ILP problem, 835

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 transitions in NFAs, 744–746

Null values in symbol tables, 626

NullPointerException, 370

Numbers

conversions, 21, 67–69, 880–881

intractability, 827

negative, 886–888

real, 888–890

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

Occam’s Razor, 814

Octal representation, 898

Odd parity function

adder circuits, 1028–1030

sum-of-products circuits, 1026

truth tables for, 1026

Off-by-one errors, 92

Offscreen canvas, 151

Offset binary representation, 889

On computable numbers, with an application to the Entscheidungsproblem article, 717

On/off switches, 1005

One-dimensional arrays, 90

One-hot OR gates, 1023

Onscreen canvas, 151

Opcodes, 911

Operands, 17

Operators and operations

boolean, 26–27, 989–991

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

TOY machine, 906

Optimal data compression, 814

Optimization

NP problems, 835

premature, 518

Optimizing compilers, 814

OR function, 987–989

OR gates, 1014, 1023

Or operation

bitwise, 891–892

boolean type, 26–27

TOY machine, 913

Order in BSTs, 640, 642–643

Order statistics, 651

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

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

arithmetic logic units, 1032

array libraries, 237–238

circuit models, 1002–1004

clocks, 1059–1060

data types, 353

file concatenation, 356

gates, 1013

machine language, 934–936

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

virtual machines, 969–970

Overflow

arithmetic, 885

arrays, 95

attacks, 963

guarding against, 898

integers, 23

negative numbers, 38

Overhead for objects, 514

Overloading

operators, 416

static methods, 198

Overriding methods, 452

P

The P= NP Question and Gödel’s Lost Letter book, 856

P search problems, 837

examples, 839

main question, 840–841

Padding object memory, 514

Page, Lawrence, 184

Page ranks, 176–177

Palindromes

description, 719

Watson–Crick, 374

Paper size, 294

Paper tape, 934–938

Papert, Seymour, 400

Parallel arrays, 411

Parallel edges, 676

Parameter variables

lambda expressions, 450

static methods, 196–197, 207

Parameterized data types, 582–586

Parameters

in performance, 511

TOY-8 machine, 1070

Parentheses ()

casts, 33

constructors, 333, 385

expressions, 17, 27

functions, 24, 197

lambda expressions, 450

methods, 30, 196

operator precedence, 17

regular expressions, 724

stacks, 587, 590

static methods, 196

vectors, 442

Parity in ripple–carry adders, 1028

Parsing

instructions, 966–967

strings, 880–882

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

intractability problems, 829

shortest. See Shortest paths

simple, 710

Pattern class for REs, 763

PCs. See Program counters (PCs)

PDA (pushdown automata), 755–756

PDP-8 computers, 906

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

regular expressions, 724

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

Pigeonhole principle, 754–755

Piping

connecting programs, 141

filters, 142–143

Pixels in image processing, 346

Plasma clouds, 280

Playing card possibilities, 823

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

regular expressions, 731

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

Polynomial time, 823

Polynomial-time algorithms

intractability, 825–826

P search problems, 837, 839

usefulness, 858

Polynomial-time reductions, 841–843

Pop operation

reverse Polish notation, 590–591

in stacks, 567–568

Positional notation, 875

Post, Emil, 813–814

Post correspondence problem, 813–814

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

arithmetic operators, 17

regular expressions, 724

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

Problem reduction

overview, 811

program equivalence, 812

Rice’s theorem, 812–813

totality problem, 811–812

Problem size in intractability, 824

Procedural programming style, 329

Program counters (PCs)

bus connections, 1073–1074

connections and timing, 1075

control lines, 1074–1075

interfaces, 1073

modules, 1073

overview, 1073

TOY machine, 910

Program equivalence problem, 812

Program size, 252–253

Programming environments, 1094

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

Programs

connecting, 141

processing programs, 788–790, 964–966

Proof by contradiction, 754

Pseudo-code, 911

public keyword

access modifiers, 384

description, 228

static methods, 196

Pulses, clock, 1058

Punched cards, 940

Punched paper tape, 934–938

Pure functions, 201

Pure methods, 32

Push operation

reverse Polish notation, 590–591

stacks, 567–568

Pushbuttons for TOY machine, 916

Pushdown automata, 755–756

Pushdown stacks, 567–568

Put operations

hash tables, 639

symbol tables, 624

Putnam, Hilary, 816

Q

Quad play, 273

Quadratic Koch island fractal, 803

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

Quadratic program, 25–26

Quadrature integration, 449

Quaternions, 424

Question marks (?) in REs, 731

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

Race conditions in flip-flops, 1050

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

random sequences, 127–128

Sierpinski triangles, 239–240

simulations, 72–73

Math.random(), 30–31

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

Real numbers, 888–890

Receivers in cryptography, 992

Recognition problem

formal languages, 722

NFAs, 744–745

REs, 728–729, 735, 753

Recomputation, 282–283

Rectangle rule, 449

Recurrence relations, 272

Recursion, 191

base cases, 281

BSTs, 640–641, 644, 649

binary searches, 533

Brownian bridges, 278–280

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

Reduced instruction set computing (RISC), 974

Reductio ab absurdum, 808

Reduction

binary search trees, 640

mergesort, 554

polynomial-time, 841–843

problem, 811–813

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

Registers

implementing, 1052

machine language, 931

overview, 1051–1052

TOY machine, 909, 911

writing to, 1052–1053

Regular expressions (REs)

applications, 732–736

computational biology, 732–734

generalized, 730–732

NFA equivalence, 750–752

overview, 724–725

recognition problem, 728–729, 735, 753

regular languages, 725–727

searches, 734–736

shorthand notations, 730–731

validity checking, 732

Regular languages, 723

basic operations, 723–724

regular expressions. See Regular expressions (REs)

Reject states

DFAs, 738–739

Turing machines, 766–767

Relative entropy, 667–668

Relays in circuit models, 1006

Remainder operation, 22–23

Removing

array items, 569

collection items, 566, 602–603

linked list items, 573–574

NFA nodes, 751

queue items, 592, 596

set keys, 652

stack items, 567–569

symbol table keys, 624–627

Rendell, Paul, 805

Repetitive code, simplifying, 100

Representation in APIs, 431

Representing information

binary and hex, 875–880

bit manipulation, 891–893

characters, 894–895

integer arithmetic, 884–885

negative numbers, 886–888

overview, 874

real numbers, 888–890

strings, 880–883

summary, 896

Reproducible experiments, 495

Reserved words, 16

Resetting flip-flops, 1050

Resizing arrays, 578–581, 635

ResizingArrayStackOfStrings program, 578–581

Resource allocation

graphs for, 673

overview, 606–607

Resource-sharing systems, 606–607

Return addresses, 931

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

Rice, Henry, 812

Rice’s theorem, 812–813

Riemann integral, 449

Riffle shuffles, 125

Right shift operations

bitwise, 891–892

TOY machine, 913

Right subtrees, 640

Right triangles, 199

Ring buffers, 620

Ring graphs, 694–695, 699

Ripple–carry adders, 1028–1030

RISC (reduced instruction set computing), 974

Robinson, Julia, 816

Roots in binary search trees, 640

Rotation filters, 379

Roulette-wheel selection, 174

Round-robin policies, 606

Rows in 2D arrays, 106, 108

RR-format instructions, 911

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

SAT problem, 832

nondeterministic TM, 836

NP-completeness, 844–846, 853–856

SAT program, 855–856

Satisfiability, 830

boolean, 832, 836

integer linear inequality, 831

linear equation, 830

linear inequality, 831

NP-completeness, 844–846, 853–856

Saving audio files, 157

Scaffolding, 302–304

Scale program, 349–350

Scaling

drawings, 146

image processing, 349–350

spatial vectors, 442–443

Scientific computing, 1094

Scientific method, 494–495

hypotheses, 496–502

observations, 495–496

Scientific notation

conversion codes, 131–132

real numbers, 888–889

Scope of variables, 60, 200

Screen scraping, 357–359

Search problems

difficult, 837–838

easy, 837

nondeterminism, 836

overview, 833

solutions, 835

subset sum, 834

TSP problem, 862

vertex cover problem, 834, 842

0/1 ILP problem, 835, 842

Searches

binary. See Binary searches

binary search trees. See Binary search trees (BSTs)

bisection, 537

breadth-first, 683, 687–688, 690, 692

data mining example, 458–464

depth-first, 312, 690

indexing, 634

overview, 532

regular expressions, 734–736

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

Self-modifying code, 922–924

SelfAvoidingWalk program, 112–115

Semantics, 52

Semicolons (;)

for loops, 59

statements, 5

Sequential circuits

clocks, 1058–1061

description, 1008

feedback circuits, 1048–1049

flip-flops, 1049–1050

memory, 1054–1057

overview, 1048

registers, 1051–1053

summary, 1062–1063

Sequential searches, 535–536

Server farms, 976

Servers, 606

Service rate, 597–598

SET library, 652–653

Sets

elementary functions, 1001

gates, 1045

graphs, 676

Julia, 427

Mandelbrot, 406–409

overview, 652–653

of values, 14

Setting flip-flops, 1050

Shadow variables, 419

Shannon, Claude, 1013, 1041

Shannon entropy, 378

Shapes, outline and filled, 149

Shifts

bits, 891–892

circular, 375

linear feedback shift registers (LFSRs), 1000–1001

purpose, 898–899

TOY machine, 913

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

P search problems, 829, 839

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

Sign-and-magnitude, 886

Sign extension convention, 899

Signatures

constructors, 385

methods, 30, 196

overloading, 198

Similarity measures, 462

Simple paths, 710

Simplex method, 831

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

Singles quotes (’), 19

Singly linked lists, 571

Sipser, Michael, 780

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

words, 874, 897

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

Slide rules, 907–908

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

P search problems, 839

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

formal languages, 722

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 ([])

arrays, 91, 106

regular expressions, 731

Square roots

computing, 65–67

double value, 25

Squares, Albers, 341–342

Squaring Markov chains, 179–180

SR flip-flops, 1050

ST library, 625–627

Stable circuits with feedback, 1049

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

machine language, 936–938

multiple streams, 143

overview, 132–133

redirecting, 140–141

summary, 159

typing, 134

virtual machines, 969–970

Standard output

description, 127

formatted, 130–132

machine language, 934–936

multiple streams, 143

overview, 129–130

piping, 141–143

redirecting, 139–140

summary, 159

virtual machines, 969–970

Standard statistics, 244–250

Standards, API, 429

Start codons, 336

Statements

assignment, 17

blocks, 50

declaration, 15–16

methods, 5

States

DFAs, 738–739

NFAs, 744–746

objects, 340

Turing machines, 766–772

virtual machines, 968

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

Store instruction, 938, 1080

Stored-program computers, 922–924

Streams

input, 354–355

output, 355

screen scraping, 357–359

Stress testing, 236

Strings and String data type

alphabet symbols, 718

API, 332–333

binary, 718–719

circular shifts, 375

concatenation, 19–20, 723–724

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

parsing, 880–882

prefix-free, 564

representation, 882–883

as sequence of characters, 19

shortcuts, 334–335

string replacement systems, 795

unions, 723

variables, 333

vertices, 675

working with, 19–21

Strogatz, Stephen, 670, 693, 713

Structured programming, 926

Stub methods, 303

Subclassing inheritance, 452–457

Subgraphs, induced, 705

Subset sum problem

intractability, 827–828

NP, 834, 838

Subtraction

floating-point numbers, 24–26

integers, 22

negative numbers, 887

Subtrees, 640, 651

Subtyping inheritance, 446–451

Sum-of-powers conjecture, 89

Sum-of-products

adders, 1028

boolean representation, 996–997

circuits, 1024–1027

Sums, finite, 64–65

Superclasses, 452

Superposition

force vectors, 483

sound waves, 211–215

Swirl filters, 379

Switch control lines, 1005

Switch statements, 74–75

Switches

bus muxes, 1036

circuit models, 1002, 1005–1006

demultiplexers, 1022

gates, 1013

multiplexers, 1020

TOY machine, 916–917

Switching circuit analysis, 1007

Switching time of gates, 1013

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

machine language, 944

overview, 624–625

perspective, 654

sets, 652–653

Symbolic names in assembly, 981

Symbols

definition, 757

description, 718–719

DFA, 738

NFA, 744

regular expressions, 724

Turing machines, 766–767

Symmetric order in BSTs, 640

Symmetric property, 454

Syntax errors, 10–11

T

Tables

of functions, 907–908

hash, 636–639

symbol. See Symbol tables

Tabs

compiler considerations, 10

escape sequences, 19

Tape and tape readers

DFAs, 738–739

Turing machines, 766–769, 774–776

Tape program, 776

Taylor series approximations, 204

Templates, 50

TenHellos program, 54–55, 60

Terminal windows, 127

Terms, glossary for, 1097–1101

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

Theory of computing, 715–717

this keyword, 445

Thompson, Ken, 735

3n+1 problem, 296–297

ThreeSum program, 497–502

Throwing exceptions, 465–466

Thue word problem, 819

Ticks, clock, 1058

Tilde notation, 500

Tildes (~)

bitwise operations, 891

boolean type, 991

frequency analysis, 500

Time

exponential, 272–273, 823

performance. See Performance

polynomial, 823

Stopwatch timers, 390–391

TimePrimitives program, 519

Timesharing, 965

Tools, building, 320

Top-level domains, 375

toString() method

Charge, 383, 387

Color, 343

Complex, 403, 405

Convert, 881–882

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

TOY machine

arithmetic logic unit, 910

conditionals and loops, 918–921

family of computers, 972–977

fetch–increment–execute cycle, 910–911

first program, 914–915

historical note, 907–908

instruction register, 910

instructions, 909, 911–913

in Java, 966–972

machine-language programming. See Machine-language programming

memory, 908–909

operating, 916–917

overview, 906–907

program counter, 910

registers, 909

stored-program computer, 922–924

virtual. See Virtual machines

von Neumann machines, 924–925

TOY program, 967

TOY-8 machine, 974–975

basic parameters, 1070

control circuit, 1080–1082

CPU, 1076–1080

instruction set, 1070–1071

perspective, 1084–1087

sum.toy program, 1071–1072, 1082–1083

TOY-64 machine, 973–974

Tracing

function-call, 195

programs with random(), 103

variable values, 18, 56–57

Transfer of control, 193–195

Transistors, 1006

Transition matrices, 172–173

Transition program, 172–173

Transitions

DFAs, 738–739

NFAs, 744–746

Turing machines, 766–767

Transitive property

comparisons, 546

equivalence, 454

polynomial-time reduction, 843

Transposition of arrays, 120

Traveling salesperson problem, 862

Traversal

binary search trees, 649–650

linked lists, 574, 577

TreeMap library, 655

Tree nodes, 269

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, 988–989

TSP problem, 862

Turing, Alan, 766

bio, 410–411, 717

code breaking, 907

von Neumann influenced by, 924–925

Turing-complete models, 794

Turing machines

binary adders, 771

binary incrementers, 769–771

compact trace format, 770

constant factor, 824

efficiency, 772

frequency count, 772–773

model, 766–769

overview, 766

related machines, 770–771

restrictions, 792–793

SAT problem, 836

universal, 789–790

universal virtual, 774–779

universal virtual DFAs, 789

universality. See Universality

variations, 791–794

TuringMachine program, 777–778

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, 886–888

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

overview, 894–895

strings, 37

Uniform random numbers, 199

Uninitialized variables, 94, 339

Union operation in REs, 723

Unit testing, 235

Universal models, 794–797

Universal sets

elementary functions, 1001

gates, 1045

Universal Turing machines (UTMs), 789–790

Universal virtual DFAs, 741–743

Universal virtual TMs, 774–779

Universality

algorithms, 786–787

Church–Turing thesis, 790–791

overview, 786

programs processing programs, 788–790

Turing machine variations, 791–794

universal models, 794–797

virtual DFA/NFA, 788–789

Universe program, 483–487

Unreachable code error, 216

Unsigned integers, 884

Unsolvability proof, 810

Unsolvable problems, 430

blank tape halting problem, 820

definite integration, 816

description, 806

examples, 815

halting problem, 808–810

Hilbert’s 10th problem, 816

implications, 816–817

liar’s paradox, 807–808

optimal data compression, 814

optimizing compilers, 814

Post correspondence, 813–814

program equivalence, 812

totality, 811–812

Upper bounds, 825

Upscaling in image processing, 349

UseArgument program, 7–8

User-defined libraries, 230

UTF-8 encoding, 895

UTMs, 789–790

V

Validate program, 729

Validity checking, 732

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

boolean, 987, 994–997

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

Vertex cover problem

intractability, 828

NP-completeness, 846–847

NP search problems, 834, 842

Vertical bars (|)

bitwise operations, 891–892

boolean type, 26–27, 991

piping, 141

regular expressions, 724

Vertical OR gates, 1023

Vertical percolation, 305–306

Vertices

bipartite graphs, 682

creating, 676

eccentricity, 711

graphs, 671, 674

isolated, 703

names, 675

PathFinder, 683

String, 675

Virtual machines

booting, 959–960, 968–969

cautions, 961–963

and cloud computing, 924

description, 965

dumping, 960–961

instructions, 966–967

Moore’s law, 971

overview, 958–959

program development, 970–971

programs that process programs, 964–966

running, 969

standard input, 969–970

standard output, 969–970

states, 968

TOY machine family, 972–977

universal virtual DFAs, 742

universal virtual TM, 774–779

Viruses, 963

Viterbi algorithm, 286

void keyword, 201, 216

Volatility

Black–Scholes formula, 565

Brownian bridges, 278, 280

Von Neumann, John, 906

ballistics tables, 907

ENIAC improvements, 924–925

Gödel letter, 840

mergesort, 554

Von Neumann architecture, 790, 906, 924–925

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

indexes 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

Wildcard operation in REs, 724

Wiles, Andrew, 722

Wind chill, 47

Wires

circuit models, 1002–1004

gates, 1013

Word ladders, 710

Words

binary representation, 875

computer, 874

memory size, 513

size, 897

Worst-case performance

big-O notation, 520–521

binary search trees, 648

description, 512

insertion sort, 544

intractability, 825

NP-completeness, 852

Wrapper types

autoboxing, 585–586

references, 369, 457

Write control lines

CPU, 1079–1080

memory bits, 1056

register bits, 1051

X

XOR circuits

in arithmetic logic units, 1031

sum-of-products, 1024–1025

xor (exclusive or) operation, 891–892, 913

Y

Y2K problem, 435, 976

Young tableaux, 530

Z

Zero-based indexing, 92

Zero crossings, 164

Zero extension convention, 899

0/1 ILP problem, 831, 835

NP-completeness, 845–846

vertex cover problem, 842

Zeros, leading, 883

ZIP codes, 435

Zipf’s law, 556