A-format instructions, 911
Absolute value function, 199
Absorption identity, 990
Abstract methods, 446
Abstraction
data, 382
displays, 346
object-oriented programming, 329
printing as, 76
recursion, 289
vs. representation, 69
standard audio, 155
standard drawing, 144
Accept states
Access modifiers, 384
Accessing references, 339
Account information
indexing, 634
Accuracy
n-body simulation, 488
random web surfer, 185
Adders
binary, 771
combinational circuits, 1007
overview, 1028
sum-of-products, 1028
AddInts program, 134
Addition
negative numbers, 887
Address control lines, 1056
Addresses
array elements, 94
memory, 909
symbolic names, 981
Adelman, Leonard, 795
Adjacency matrix, 692
Adjacent vertices, 671
Albers, Josef, 342
AlbersSquares program, 341–342
Alex, 380
Algebra
Algorithms, 493
computability, 787
exponential-time, 826
overview, 786
performance. See Performance
searching. See Searches
sorting. See Sorts
Aliasing
arrays, 516
references, 363
Alphabets
metasymbols, 725
regular expressions, 730
ALUs. See Arithmetic logic units (ALUs)
Ampersands (&)
Analog circuits, 1013
AND circuits in ALUs, 1031
AND gates, 1014
And operation
TOY machine, 913
Animations
double buffering, 151
Annihilation identity, 990
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
Approximation algorithms, 852
Arbitrary-size input streams, 137–138
Arguments
methods, 30
static methods, 197
Ariane 5 rocket, 35
Arithmetic
CPU instructions, 1079
floating point numbers, 890
operators, 22
TOY machine instructions, 912
Arithmetic logic units (ALUs), 1031
bitwise operations, 1031
inputs, 1031
outputs, 1032
TOY machine, 910
Arithmetic expression evaluation, 586–589
Arithmetic shifts
ArrayIndexOutOfBoundsException, 95, 116, 466
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, 603
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
The Art of Computer Programming book, 947
Assemblers for TOY machine, 964
Assembly language
description, 930
symbolic names, 981
Assignments
arrays, 117
chained, 43
compound, 60
description, 17
references, 363
Associative arrays, 630
Associativity, 17
Asterisks (*)
comments, 9
regular expressions, 724
Audio
plotting sound waves, 249
Automatic promotion, 33
Average-case performance, 648
Average magnitude, 164
Average path lengths, 693
Average power, 164
Axioms in Boolean algebra, 990
Backslashes (\)
escape sequences, 19
regular expressions, 731
Backward compatibility, 976
Bacon, Kevin, 684
Balanced binary trees, 661
Base cases
binary search trees, 640
Base64 encoding, 904
Bases in positional notation, 875
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
BigInteger class, 827, 897–898
Binary adders, 771
Binary digits, 22
Binary frequency count equality, 772–773
Binary number system
description, 38
Binary operators, 17
Binary reflected Gray code, 274
Binary representation
decimal conversions, 877
description, 875
literals, 891
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
Binary16 format, 888
Binomial coefficients, 125
Binomial distributions, 125, 249
Biology
DNA computers, 795
graphs, 672
Bipartite graphs, 682
Bisection searches, 537
Bit-slice memory design, 1054–1056
Bitmapped images, 346
Bitonic arrays, 563
Bits
computer dependence, 874
description, 22
memory, 1056
memory size, 513
register, 1051
Bitwise operations
and, 913
arithmetic logic units, 1031
shift, 913
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
cryptography application, 992–994
description, 27
overview, 986
Boolean matrices, 302
Boolean satisfiability, 832, 836
boolean equation satisfiability problem, 838
NP-completeness, 844–846, 853–856
Bootstrapping, 971
Bounding boxes for drawings, 146
Bounds
arrays, 95
exponential time, 826
polynomial time, 825
Box–Muller formula, 47
Breadth-first searches, 683, 687–688, 690, 692
break statement, 74
Brin, Sergey, 184
Brown, Robert, 400
Brute-force algorithm, 535–536
BSTs. See Binary search trees (BSTs)
Buffer overflow
arrays, 95
attacks, 963
Buffering drawings, 151
Bugs
overview, 6
testing for, 318
Built-in interfaces, 451
CPU connections, 1077
program counter connections, 1073–1074
Buzzers, 1048
byte data type, 24
Bytecode
Java virtual machine, 965
Bytes memory size, 513
C conversion specification, 131
Caches
and instruction time, 509
in top-down dynamic programming, 284
Calculators, 908
Callbacks in event-based programming, 451
Calls, 193
chaining, 404
reverse Polish notation, 591
Canvas, 151
Card decks, arrays for, 97–100
Carets (^)
regular expressions, 731
Carroll, Lewis, 710
Carry bits in adders, 1028
Cartesian representation, 433
Cat program, 356
Cellular automata, 794
Central processing units (CPUs)
bus connections, 1077
execute phase, 1079
fetch phase, 1078
interfaces, 1076
load address, 1080
modules, 1076
overview, 985
Centroids, 164
Chained assignments, 43
Chained comparisons, 43
Chaining method calls, 404
Characters and char data type
ASCII, 894
conversion to numbers, 880–881
description, 15
memory size, 513
Checksums
description, 86
formula, 220
Chords, 211
Chromatic scale, 156
Church, Alonso, 790
Church–Turing thesis
extended, 823
Turing machine simulation, 798
virtual machines, 958
Ciphers, Kamasutra, 377
Ciphertext, 993
controlled switches, 1005–1006
conventions, 1004
Circuits
combinational. See Combinational circuits
description, 1010
Circular linked lists, 622
Circular queues, 620
Circular shifts, 375
ClassDefFoundError, 160
description, 226
inner, 609
modules as, 228
variables, 284
Classifying NP-complete problems, 851
Client code
data types, 430
library methods, 230
Clocks
run and halt inputs, 1060
Closure operation in REs, 724
Clouds, plasma, 280
Clustering coefficients
global, 713
Code and coding
description, 2
encapsulating, 438
incremental development, 319, 701
Codebooks, 992
Codons, genes, 336
Coefficients for floating-point numbers, 889
Coercion, 33
Collatz function, 784
Collatz sequence, 948
Collections
description, 566
queues. See Queues
stacks. See Stacks
symbol tables. See Symbol Tables
Colons (:)
in Turing machine tapes, 767
Color and Color data type
blobs, 709
compatibility, 344
drawings, 150
grayscale, 344
luminance, 343
memory, 514
Columns in 2D arrays, 106, 108
demultiplexers, 1022
layers of abstraction, 1037–1039
modules, 1034
multiplexers, 1023
overview, 1012
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
Commutative axiom, 990
Compact trace format, 770
Comparable interface, 451, 545
Comparable keys
sorting, 546
CompareDocuments program, 462–463
compareTo() method
description, 451
String, 332
Comparisons
arrays, 117
chained, 43
Compatibility
backward, 976
Color, 344
Compile-time errors, 6
Compilers
optimizing, 814
purpose, 788
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
Compression, optimal, 814
Computability
algorithms, 787
overview, 806
unsolvability proof, 810
unsolvable problems. See Unsolvable problems
Computation: Finite and Infinite Machines, 780
Computational biology, 732–734
Computational models, 716
Computer animations, 151
Computer speed in performance, 507–508
Computers and Intractability: A Guide to the Theory of NP-completeness book, 859
Computers Ltd.: What They Really Can’t Do book, 780
Computing devices
boolean logic. See Boolean logic
circuit models. See Circuit models
combinational circuits. See Combinational circuits
digital. See Digital devices
overview, 985
sequential circuits. See Sequential circuits
Computing machines
machine-language programming. See Machine-language programming
overview, 873
representing information. See Representing information
TOY. See TOY machine
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
Connections
buses, 1034
CPU, 1077
Constant order of growth, 503
Constants, 16
Constructors
String, 333
Containing symbol table keys, 624
Context-free languages, 755
Continue statements, 74
Contracts
machine-language, 932
Control characters, 894
Control circuit
CPU, 1078
fetch signals, 1080, 1082–1083
overview, 1080
Control flow
conditionals and loops. See Conditionals and loops
Control lines
memory bits, 1056
register bits, 1051
Controlled switches, 1002–1003, 1005–1006
Conversion specifications, 130–131
Conversions
data types, 339
decimal to binary, 877
implicit, 33
overview, 32
Cook–Levin theorem, 844–845, 847
Cook reduction, 841
Coordinates
images, 347
polar, 47
Corner cases, 236
Cosine similarity measure, 462
Cost of immutable types, 440
Coulomb’s law, 383
Counter circuits, 1008
Counter machines, 794
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-coupled NOR gates, 1050
Cross-coupled switches, 1049
Cross products of vectors, 472
Cryptographic keys, 992
Cryptography application, 992–994
<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
Dantzig, George, 831
Data compression, 814
Data-driven code, 141, 171, 184
Data paths for buses, 1034
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
overview, 428
access modifiers, 384
APIs, 383
boolean, 991
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
TOY machine, 907
type safety, 18
variables within methods, 386–388
Davis, Martin, 816
Dead Sea Scrolls, 659
abstraction layers, 1037
encapsulation for, 432
immutable types, 440
linked lists, 596
test client main() for, 235
unit testing, 246
Decimal number system
conversion to binary, 877
Decision problems, NP, 835
Declaring
String variables, 333
Decoding numbers, 889
Decryption devices, 992
Dedup operation
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
DeMorgan’s laws, 989–991, 1014–1015
Demultiplexers, 1022
Denial-of-service attacks, 512
Dependencies in subclasses, 453
Dependency graphs, 252
Deprecated methods, 469
Depth-first searches
vs. breadth-first searches, 690
percolation case study, 312
Deques, 618
Derived classes, 452
Descartes, René, 398
Design
APIs, 233
data types. See Data-type design
Deterministic finite-state automata (DFAs)
Kleene’s theorem. See Kleene’s theorem
operations, 739
overview, 738
summary, 756
Diameters of graphs, 711
Diamond operators (<>), 585
Dice
Sicherman, 259
simulation, 121
Dictionary lookup, 624, 628–632
Difficult problems
Digital circuits, 1013
Digital devices, 1070
Digital image processing
overview, 346
Digital signal processing, 155, 158
Dijkstra, Edsgar
Dutch-national-flag problem, 564
goto statements, 926
two-stack algorithm, 587
Dijkstra’s algorithm, 692
Diophantine, 816
Directed graphs, 711
Directed percolation, 317
Discrete distributions, 172
Disjunctive normal forms, 996–997
Distances of graph paths, 683, 687–688
Distributive axiom, 990
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.parseDouble() method
Double buffering drawings, 151
double data type
conversion codes, 132
input, 133
memory size, 513
Double negation identity, 990
Double negatives in gates, 1015–1016
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
Easy problems
intractability, 829
search, 837
Eccentricity in vertices, 711
Edges
self-loops and parallel, 676
n-body simulation, 488
random web surfer, 185
Turing machines, 772
Efficient algorithms, 532
Einstein, Albert, 400
Election voting machine errors, 436
Element distinctness problem, 554
Elements in arrays, 90
Empty strings with REs, 724
Emulators, 965
Encapsulation
code clarity, 438
modular programming, 432
overview, 432
planning for future, 435
private access modifier, 433
Encoding numbers, 889
Encryption devices, 992
End-of-file sequence, 137
Enhancements for Turing machines, 792–793
Enigma code, 717
Entropy
Shannon, 378
Equals signs (=)
assignment statements, 17
assignment vs. boolean, 42, 78
compound assignments, 60
Equality of objects, 364, 454–456
equals() method
Color, 343
String, 332
Equilateral triangles, 144–145
Equivalence problem for REs, 728
Equivalent models for Turing machines, 792–793
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
machine-language, 931
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 (!)
Exclusive or operation
Execute phase in CPU, 1079
Exponential distributions, 597
Exponential order of growth, 505
intractability, 826
playing card possibilities, 823
SAT problem, 856
usefulness, 858
Expressions
arithmetic evaluation, 586–589
description, 17
Lambda, 450
method calls, 30
regular. See Regular expressions
Extended Church–Turing thesis, 823
Extensible libraries, 452
ExtractFloat program, 893
Falsifiable hypotheses, 495
Fecundity parameter, 89
Fermat’s Last Theorem, 89, 722
Fetch–increment–execute cycle, 910–911
Fibonacci numbers
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
exponents, 889
precision, 40
storing, 40
Flow of control
conditionals and loops. See Conditionals and loops
for loops
continue statement, 74
examples, 61
DFAs. See Deterministic finite-state automata (DFAs)
recognition problem, 722
regular expressions. See Regular expressions (REs)
specification problem, 722
Format, files, 237
Formatted input, 135
Forth language, 590
Fortran language, 1094
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
Functional property of programs, 812–813
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
Gardner, Martin, 424
Garey, Michael R., 859
Gates
abstraction layers, 1037
AND, 1014
NOR, 1014
OR, 1014
overview, 1013
universal sets of, 1045
Gaussian distribution functions
API, 231
Gaussian elimination, 830
Gaussian program, 203
Gaussian random numbers, 47
General purpose computers, 790
Generalized multiway gates, 1016–1017
Generalized regular expressions, 730–732
Genomics
indexing, 634
regular expressions, 727, 732–734
symbol tables, 629
Geometric mean, 162
Geometry
German Enigma code, 717
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
Goldstine, Herman, 925
Gore, Al, 436
Gosper, R., 805
Goto statements, 926
Graphics
bipartite, 682
connected components, 709
dependency, 252
description, 671
DFAs, 738
diameters, 711
directed, 711
examples, 695
generators, 700
grid, 708
isomorphism problem, 859
matching, 713
random web surfer, 170
Gravity, 481
Grayscale
Color, 344
Greater than signs (>)
lambda expressions, 450
Greatest common divisor (gcd)
machine language, 931
Grep program, 736
grep tool
Grid graphs, 708
Guarantees
NP-complete problems, 852
worst-case analysis, 825
Hadamard matrices, 122
Halt instructions
CPU, 1079
TOY machine, 912
Hamilton, William, 424
Hamming distances, 295
Handles for pointers, 371
Hardy, G. H., 86
Harel, David, 780
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
Hexadecimal (hex) notation
conversions with binary, 876–877
literals, 891
memory, 909
Hilbert curves, 425
Hilbert’s 10th problem, 816
Histograms, 177
Hoare, C. A. R., 518
Hollywood numbers, 711
Horner, William, 957
Horner’s method, 223, 882, 956–957
Hurst exponent, 280
Hyperbolic functions, 256
Hyperlinks, 170
Hypotenuse of right triangles, 199
Hypotheses
falsifiable, 495
mathematical analysis, 498, 500–502
overview, 496
Identities
exclusive or function, 993
IEEE 754 standard, 40, 888–889
if statements
nesting, 62
IllegalFormatConversionException, 131
ILP problem (integer linear programming problem), 831
NP-completeness, 846
vertex cover problem, 842
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
Indexing
String, 332
zero-based, 92
Induced subgraphs, 705
Induction
recursion step, 266
Infinite tape for Turing machines, 769, 774
Information content of strings, 378
Information representation. See Representing information
Inheritance
multiple, 470
Initialization
array, 93
inline, 18
instance variables, 415
two-dimensional array, 106–107
Inline variable initialization, 18
Inner classes, 609
description, 62
Inorder tree traversal, 649
arithmetic logic units, 1031
clocks, 1060
command-line arguments, 7
data types, 353
demultiplexers, 1022
file concatenation, 356
gates, 1013
in performance, 510
random web surfer, 171
Input/off switches, 1005
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
Instruction register (IR), 910
Instructions
components, 911
execution time, 509
TOY machine, 909
Integer linear inequality satisfiability, 831, 838, 845
Integer linear programming, 831
NP-completeness, 846
vertex cover problem, 842
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
circuit models, 1003
CPU, 1076
defining, 446
functional, 450
implementing, 447
memory, 1054
multiplexers, 1020
program counters, 1073
Internet Protocol (IP), 435
Interpolation in fade effect, 351
Interpreters
Evaluate program, 589
TOY machine, 964
IntOps program, 23
Intractability
easy problems, 829
exponential-time algorithms, 826
NP-completeness. See NP-completeness
numbers, 827
path problems, 829
polynomial-time algorithms, 825–826
polynomial-time reductions, 841–843
problem size, 824
vertex cover, 828
worst case, 825
Introduction to the Theory of Computation book, 780
Invariants in assertions, 467
Inverse permutations, 122
Invoking instance methods, 334
IP (Internet Protocol), 435
IPv4
vs. IPv6, 435
IPv6
vs. IPv4, 435
number of addresses, 901
IR (instruction register), 910
IR write control line, 1082
ISBN (International Standard Book Number), 86
Isolated vertices in graphs, 703
Isomorphic binary trees, 661
Isomorphism in graphs, 859
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
libraries, 1094
Java platform, 2
Java Virtual Machine (JVM)
description, 3
as program, 788
Java virtual machines, 429
Johnson, David S., 859
Josephus problem, 619
Julia sets, 427
Jump and link instruction, 931
Jump register instruction, 931
Kamasutra ciphers, 377
Karp’s reductions
polynomial-time, 841
Key-sorted tree traversal, 649
Keys
cryptographic, 992
immutable, 625
Kamasutra ciphers, 377
Kleene, Stephen, 748
DFA, NFA, and RE equivalence, 749–752
overview, 748
proof strategy, 748
RE recognition, 753
Knuth, Donald
MIX machine, 947
optimization, 518
SAT solvers, 832
Koch program, 397
Ladders, word, 710
Ladner, R., 859
Lambda expressions, 450
Languages. See Formal languages; Programming languages
Last-in first-out (LIFO), 566–567
Lattices in random walks, 112–115
Layers of abstraction, 1037–1039
LCS (longest common subsequence), 285–288
Leading zeros, 883
Leaf nodes in BSTs, 640
Left associativity, 17
Left shift operations
TOY machine, 913
Left subtrees, 640
Length
strings, 332
Less than signs (<)
Let’s Make a Deal simulation, 88
Levin, Leonid, 845
clients, 230
extensible, 452
Java, 1094
modifying, 255
in modular programming, 227–228, 251–254
modules, 191
stress testing, 236
unit testing, 235
LIFO (last-in first-out), 566–567
Lights for TOY machine, 916
Lindenmayer systems, 803
Linear algebra for vectors, 442–443
Linear equation satisfiability problem, 830, 839
Linear feedback shift registers (LFSRs), 1000–1001
Linear inequality satisfiability problem, 831, 839
Linear interpolation, 351
Linear order of growth, 504–505, 507–508
Linear programming problem, 831
Linearithmic order of growth, 504–505, 507–508
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
binary and hex, 891
booleans, 26
description, 15
floating-point numbers, 24
integers, 22
Little’s law, 598
Load address instruction, 1080
Local variables
vs. instance variables, 384
static methods, 196
Logarithmic order of growth, 503
Logical switches
bus muxes, 1036
demultiplexers, 1022
multiplexers, 1020
Logo language, 400
Loitering condition, 581
Long path problems, 829
Longest common subsequence (LCS), 285–288
Longest path problem, 838
LongestCommonSubsequence program, 286–288
Loops. See Conditionals and loops
Lost letter, 840
Lower bounds, 826