A
adaptive Monte Carlo integration, 54, 496
adaptive quadrature, 44–47, 52
adaptive techniques, 47, 469, 478
AdaptiveGridIntegration program, 47, 48, 496
AdaptiveMidpointIntegration sample program, 44–46
AdaptiveTrapezoidIntegration program, 46
AddEntries method, 109, 506, 508
adding values
addition
sparse matrices, 106–107, 109, 505–508
addressing, open, 172–174, 182, 183, 480, 514
Adelson-Velskii, G. M., 278. See also AVL t rees
Adleman, Leonard, 412
Advanced Encryption Standard (AES), 398, 409–410, 411, 416
age of brother, interview puzzle, 467, 475, 553–554
agreement, consensus problem, 456
AIDS, Folding@home project, 439
airline connectivity matrix, 94–95, 97
algorithmic concepts, summary, 477–486
arrays, 479
balanced trees, 482
complexity theory, 485
cryptographic algorithms, 484–485
distributed algorithms, 485–486
hash tables, 480
interview puzzles, 486
linked lists, 478
numeric algorithms, 478
queues, 479
searching algorithms, 480
stacks, 479
string algorithms, 484
approach, 2
confusing, 6
data structures compared to, 3, 22, 477, 489
groupings, 2
intuitive approach, 2
performance characteristics, 19
themes, 2
all-pairs shortest paths, 345–350, 353, 483, 534
alphabets, special, 397
Alzheimer's, Folding@home project, 439
AngleSnowflake example program, 516
animal game, 256–258, 274, 482, 521–522
annealing, simulated, 314, 320, 321, 483
antiderivative, of function, 42
Applied Cryptography: Protocols, Algorithms, and Source Code in C (Schneier), 416
approximate routing, 200
arithmetic expressions. See expressions
Array class, BinarySearch method, 163
arrays, 83–109. See also one-dimensional arrays; sparse arrays; three-dimensional arrays; triangular arrays; two-dimensional arrays
associative, 170
complete binary trees in, 139–140, 144, 145, 161, 236–237
graphical representations, 84
higher dimension, nonzero lower bounds, 91–94
linked lists compared to, 56, 59
median of, 87–88, 108, 501–502
nonzero lower bounds, 89–91, 108, 479, 511
queues compared to, 108
reversing, 117
scratch, 154
sorting algorithms, summary of characteristics, 159–160
stacks compared to, 108
summary of concepts, 479
systolic, 436–438, 446, 462, 485, 547
Arrays.sort library method, Java, 152, 155
art gallery problem, 429
ASCII characters, 66
associative arrays, 170. See also hash tables
asymptotic performance, 7, 9, 18, 145
atmospheric noise, 26
attack, retreat. See consensus problem
augmenting paths, 369, 370, 373, 376, 484, 535
average, one-dimensional arrays, 86–88
inventors, 278
B
back-of-the-envelope calculations, 467, 472
backtracking algorithms, 201–203. See also chess
defined, 277
kinds, 277
node splits, 283–284, 291, 482
O(log N) time, 277, 281–282, 293
pictures, 277
rotations
summary of concepts, 482
tall, thin trees, 147, 148, 233, 247, 271, 277, 283, 287, 293
bank examples
snapshot, 460
baseballs, in school bus, 467, 471
Beginning XML, 5th Edition (Fawcett, et al), 236
behavior, of algorithms, 2, 477
Berkeley Open Infrastructure for Network Computing (BOINC), 439
BGP. See byzantine generals problem
bias concept
biased PRNG, 29
fairness from biased sources, 30–31
Big O notation
Big Omega notation, 420
Big Theta notation [Θ(g(N))], 420–421
bin sort. See bucketsort algorithm
binary search
speed, 167
binary trees
complete
in arrays, 139–140, 144, 145, 161, 236–237
B-trees, 287
defined, 230
defined, 230
facts, 232
fat, 233
sorted, 248, 250, 271, 278, 283
BinarySearch example program, 513
BinarySearch method, 163
bipartite detection problem, 432, 542–543
bipartite network, 371, 376, 537
bitwise XOR operator, 408, 409, 410
Blowfish, 398
BOINC (Berkeley Open Infrastructure for Network Computing), 439
book copies to five people example, 32–33, 52, 491–492
bottleneck traveling salesman problem, 429. See also traveling salesman problem
bottom-up B-tree, 291
Boyer-Moore algorithm, 377, 388–391, 394, 484
boys/girls, percentage in population, 475, 555–556
brainstorm, interview puzzles, 470
branch and bound technique, 309–310, 318, 320, 321, 323, 432, 483, 531
breadth-first traversal, 334–335, 342, 350, 355, 483
BreakLoopHashtable sample program, 74–75
BreakLoopMarking sample program, 73
BreakLoopTortoiseAndHare example program, 500
brother's age, interview puzzle, 467, 475, 553–554
Brownian motion, 26
brute-force, 299, 388, 389, 396, 410, 432, 448
bubblesort algorithm
characteristics, 159
Bubblesort example program, 511
buckets
B-trees, 287, 291, 292, 295, 528
hash table with chaining, 171–172
bucketsort algorithm
characteristics, 160
exercises, 161, 432, 511, 512, 513, 542
parallelism, 480
bully algorithm, 458–459, 463, 550
byte streams, 399
byzantine generals problem (BGP), 453–455, 457, 485
C
Caesar, Julius, 404
Caesar substitution, 404–405, 406, 407, 416, 417, 541
cafeteria plates, stack of, 111–112
call stack, 187
call tree, 146, 147, 154, 188–189
cancers, Folding@home project, 439
capacitated network, 368–370, 376
capacity
defined, 327
residual capacities, 369–370, 373, 376
residual capacity networks, 369–370, 373, 376, 448, 535
cards
interview puzzles, 486
randomization, 31, 52, 478, 492
Carmichael numbers, 53, 494–495
CarmichaelNumbers example program, 495
carpet, Sierpinski, 201, 224, 517–518
cells. See also linked lists
adding, 56
FindCellBefore algorithm, 58–59
InsertCell algorithm, 61–62, 64, 65–66, 69, 81, 498–500
chaining
Chaining example program, 513
Chandy, K. Mani, 460
Chandy/Misra solution, 451, 462, 548
checkers, 298
chess
eight queens problem, 203–206, 208, 223, 224, 322, 518
game tree, 202, 298, 300, 302, 303
heuristics, 304
knight's tour problem, 206–209, 216, 223, 225, 518
chimneys in Detroit, interview puzzles, 471
Chinese postman problem, 429
ciphers
Caesar substitution, 404–405, 406, 407, 416, 417, 541
column transposition, 401–403, 409, 417, 541
one-time pads, 404, 408, 418, 484, 541, 542
row/column transposition, 399–401, 402, 417
simple substitution, 404, 407–408
substitution-permutation network, 409–410, 416
transposition, 399–404, 409, 417, 484
Vigenère, 405–407, 408, 411, 416, 417, 541
ciphertext, 398
circular arrays, 125–126, 128, 479
CircularQueue sample program, 126–127
classes
Array class, BinarySearch method, 163
heap and, 237
clique, 430
clique cover problem, 430
clock synchronization, 460–461, 463–464, 486
clustering
defined, 480
clusters, 439, 446. See also distributed environments
coin flips, fair, 30–31, 52, 478, 491
collision, 170
collision-resolution policy, 170, 173, 174, 480
column transposition cipher, 401–403, 409, 417, 541
column-ordered sparse matrices, 107
combinations. See selections
comments, pseudocode, 4
commutative, edit distance algorithm, 396, 540
complete binary trees. See binary trees
complete trees
complexity theory, 419–433. See also NP; P
bipartite detection problem, 432, 542–543
detection problem, 427–429, 432, 433, 485, 542–543, 546
mergesort algorithm, 419
NPSPACE, 423
optimization problem, 427–429, 482, 485
reductions
polynomial-time reductions, 424, 425, 426, 431, 432, 433, 485, 544
reporting problem, 427–429, 433, 485, 546
subset sum problem, 427, 428, 431
summary of concepts, 485
3SAT problem, 321–322, 425, 431
composite numbers, 36, 41, 53. See also Carmichael numbers
computational complexity theory. See complexity theory
computers. See also distributed algorithms
DFAs, 381–386, 394, 395, 396, 421, 484, 537, 538, 539
distributed computing, 436, 438–440, 446, 462, 485
flops, 439
grid computing, 439–440, 446, 462
multiple cores, 435, 440, 446, 462, 485
multiple CPUs, 155, 432, 438–439, 440, 449, 485
nondeterministic, 421–422, 423, 424, 445, 485
quantum computing, 435, 446, 485
Turing machines, 421–422, 424, 425
confusing algorithms, 6
congruential generators, linear, 26–29
connected components, networks, 326, 327, 335, 336–337, 351, 359, 361, 362, 363, 364, 532
connectivity matrix, airline, 94–95, 97
connectivity testing, 335–337, 350, 483
consensus problem, 455–458, 486
ContainsDuplicates, 10, 15, 20
contention, 448
Cook-Levin theorem, 424
CopyEntries method, 109, 505, 508
cores, multiple, 435, 440, 446, 462, 485
correctness, algorithm feature, 6, 477
costs, links, 326, 327, 328, 329, 338, 340, 342, 344
Cotes formulas. See Newton-Cotes formulas
counting combinations, eight queens problem, 204
counting permutations
with duplicates, 214
without duplicates, 216
countingsort algorithm
characteristics, 160
CountTicTacToeBoards example program, 530–531
CPUs. See computers
Cracking the Coding Interview (McDowell), 474
creativity, interview puzzles, 465, 466, 467, 468, 472
critical-thinking ability, interview puzzles, 465, 468, 472
cryptanalysis, 398
cryptographic algorithms, 397–418. See also ciphers
RSA algorithm, 412–415, 416, 417, 418
cryptographically secure pseudorandom number generators. See CSPRNGs
cryptography
decryption
defined, 398
linear congruential generator, 26–29
defined, 397
encryption
Blowfish, 398
defined, 398
public-key, 412–413, 415, 416, 485
unbreakable encryption scheme, 418, 542
GCDs, 33
goal, 398
hash values, 415
hieroglyphics, 397
obscurity, 397, 398, 399, 415, 540
online information, 416
security through obscurity, 397, 398, 399
crystals, 314
CSPRNGs (cryptographically secure pseudorandom number generators)
disadvantages, 29
unbreakable encryption scheme, 418, 542
cubes, 21–22, 488–489. See also dice rolls
curves. See specific curves
cutting stock problem, 318–319
cycle detection, 359
cycles. See also networks; tortoise-and-hare algorithm
Floyd's cycle-finding algorithm, 78
Hamiltonian, 430, 433, 543, 544, 545
three-cycle problem, 432, 542–543
D
Data Encryption Standard (DES), 411, 416
data processing units (DPUs), 436–438
data structures
algorithms compared to, 3, 22, 477, 489
defined, 3
interview puzzles, 469
numerical algorithms, 52
dead beef, 466
deadlock, 444–445, 450, 451, 462, 485
debugging
distributed algorithms, 446–447
parallel algorithms, 485
decision trees, 297–323. See also heuristics
bin packing, 318
cutting stock problem, 318–319
game trees
defined, 482
initial moves and responses, 302–303, 482
minimax strategy, 298–302, 322, 482
tic-tac-toe, 298–303, 322, 531
interview puzzles, 469
optimization problems, 482
partition problem, 305–317, 319, 320, 321, 323
degree
in-degree, 326, 327, 328, 375, 535
out-degree, 326, 327, 328, 375, 535
degree-constrained spanning tree, 430
deleting values
depth-first traversals, 243–244, 256, 272, 331–334, 335, 350, 355, 483, 520
deques (double-ended queues), 127–128, 129, 479, 510
derivative, of function, 46, 49, 50
DES (Data Encryption Standard), 411, 416
detection problem, 427–429, 432, 433, 485, 542–543, 546
DetectKnapsack, 546
deterministic complexity classes, 422–423
deterministic finite automata (DFAs), 381–386, 394, 395, 396, 421, 484, 537, 538, 539
Detroit chimneys, interview puzzles, 471
DFAMatch example program, 538
DFAs. See deterministic finite automata
dice rolls
cookie example, 30
PRNGs
biased, 478
nonuniform distributions, 33
true randomness, 26
dictionaries, 170. See also hash tables
difficult interview puzzles, 465, 467, 468, 469, 472, 552
dining philosophers problem, 445, 449–452, 462–463, 485, 548–549, 550
directed networks, 326–327, 328, 329, 351, 532
discussion, during puzzle solutions, 467–468, 473
disk bound application, 448
disk contention, 448
Distance array, 346, 348, 349, 534
distributed algorithms, 435–464. See also parallel algorithms; parallelism
byzantine generals problem, 453–455, 457, 485
clock synchronization, 460–461, 463–464, 486
consensus problem, 455–458, 486
deadlock, 444–445, 450, 451, 462, 485
dining philosophers problem, 445, 449–452, 462–463, 485, 548–549, 550
general and lieutenants problem, 453–455, 463, 549–550
mutexes, 442–445, 447, 462, 548
two generals problem, 452–453, 463, 485
distributed computing, 436, 438–440, 446, 462, 485
distributed environments
grid computing, 439–440, 446, 462
distributed networks, 440
divide-and-conquer approach, 19, 153, 159, 469, 479
dividing items, 145–153, 157, 161, 511, 512
dominating set, 430
DoSomething, 6
double hashing, 178–179, 181, 183, 480, 514–515
double stacks, 115–117, 128, 509
double-ended queues. See deques
DoubleHashing example program, 514
DoubleIt, 6
doubly linked lists
DPUs (data processing units), 436–438
DrawTree example program, 520
DSPACE, 423
duplicated letters, keys, 417
duplicates
E
edit distance algorithm, 3, 374, 391–394, 396, 484, 540
efficiency, algorithm feature, 7, 477
eight queens problem, 203–206, 208, 223, 224, 322, 518
embarrassingly parallel algorithms, 447–449, 485
encryption. See cryptography
entanglement, 445
Eratosthenes, sieve of, 39–40, 53, 422, 478, 494
Euclid's algorithm, 33–35, 53, 413, 492
Euler's totient function, 412, 413, 414
EvaluateBoolean example program, 537
EvaluateExpression example program, 537
exercises
algorithm basics, 20–23, 487–490
balanced trees, 293–295, 524–530
complexity theory, 432–433, 542–547
cryptographic algorithms, 417–418, 540–542
decision trees, 322–323, 530–532
distributed algorithms, 462–464, 547–551
interview puzzles, 474–475, 551–558
network algorithms, 351–353, 375–376, 532–537
numerical algorithms, 52–54, 491–496
searching algorithms, 168, 512–513
sorting algorithms, 160–162, 510–512
string algorithms, 394–396, 537–540
exhaustive search, decision trees, 307–308
exponential runtimes, 15, 16, 20, 191
ExponentiateMod program, 414, 418, 493
exponentiation, fast, 35–36, 41, 53, 413, 478, 492–493
expressions. See also regular expressions
evaluation
specialized tree algorithms, 258–260, 274–275
subexpressions, 258–259, 384–386, 387
matching parentheses, 378–380, 381, 394
EXPSPACE, 423
extending partial ordering. See topological sorting
eXtensible Markup Language. See XML
external sorting, 155, 159, 480
F
factorial algorithm
Factorial example program, 515
factorial function (N!), 15, 16, 17, 18, 20, 186–188, 189, 478, 481
failing, interview puzzles, 468, 470–471, 473
failures, phase king algorithm, 456, 457, 458
fairness
coin flips, 30–31, 52, 478, 491
family tree analogy, 228
fast exponentiation, 35–36, 41, 53, 413, 478, 492–493
FastExponentiation example program, 492–493
FastFibonacci example program, 518
fat trees, 233
Fawcett, Joe, 236
feedback vertex set, 430
Feistel, Horst, 412
fencepost problem, 554
Fermat's little theorem, 40
Fermat's primality test, 6, 40, 52, 478
Fibonacci function, 23, 189, 218, 489–490
FibonacciNumbers example program, 515
FibonacciValues array, 218–219
FIFO (first-in-first-out), 123, 128, 244, 334, 335, 479
file processing, 448
fill percentage, 170, 173, 174, 181, 182
FindCellBefore algorithm, 58–59
finding items, linear arrays, 86
finding minimum, maximum, average, 86–88
finding nodes, sorted trees, 247
finding paths in networks. See networks
FindZero algorithm, 50
first common ancestor (least common ancestor), 229, 231
first-in-first-out. See FIFO
five people, books for, 32–33, 52, 491–492
flips. See coin flips
floating-point operations per second (flops), 439
floating-point values
64-bit double-precision, 188
flops. See floating-point operations per second
Floyd's cycle-finding algorithm, 78. See also tortoise-and-hare algorithm
Floyd–Warshall algorithm, 345
Folding@home, 439
For i loop, insertionsort algorithm, 160
For loop
arrays
inserting items, 89
insertionsort, 133
selectionsort, 134
described, 5
FindZero algorithm, 50
Ford-Fulkerson algorithm, 370
forks. See dining philosophers problem
4×4×3 three-dimensional array, 92
four-coloring, 362–363, 367, 375, 484
four-person general and lieutenant problem, 455, 463
fractals
embarrassingly parallel algorithms, 447
self-similar, 193–194, 200, 223, 481
full complete binary tree, 14
function's antiderivative, 42
function's derivative, 46, 49, 50
G
game trees
defined, 482
initial moves and responses, 302–303, 482
minimax strategy, 298–302, 322, 482
tic-tac-toe, 298–303, 322, 531
garbage-collection method, 63, 105
gaskets, Sierpinski, 200–201, 224, 517
GCDs (greatest common divisors)
cryptographic routines, 33
Euclid's algorithm, 33–35, 53, 413, 492
GcdTimes example, 494
GcdTimes example program, 494
genealogy, 227, 325. See also networks; trees
general number field sieve, 445
generals problem
byzantine generals problem, 453–455, 457, 485
consensus problem, 455–458, 486
general and lieutenants problem, 453–455, 463, 549–550
two generals problem, 452–453, 463, 485
generator curve, 193–194, 223, 224, 481, 516
gigaflops, 439
girls/boys, percentage in population, 475, 555–556
glib answer, interview puzzles, 471
Go, game, 298
Google, interview puzzles, 465, 473
graphical algorithms, recursion, 193–201
GraphicalTowerOfHanoi example program, 515
graphs
networks as, 325
trees as, 227
greatest common divisors. See GCDs
grid computing, 439–440, 446, 462
guess and check, interview puzzles, 470
H
HAM. See Hamiltonian path problem
HAMC. See Hamiltonian cycle
Hamiltonian completion, 430
Hamiltonian cycle (HAMC), 430, 433, 543, 544, 545
Hamiltonian path problem (HAM), 429, 430, 432, 440, 444, 446, 462, 543, 544, 545
hare and tortoise. See tortoise-and-hare algorithm
associative arrays, 170
BreakLoopHashtable sample program, 74–75
chaining
clustering
defined, 480
cryptography, 415
dictionaries, 170
fill percentage, 170, 173, 174, 181, 182
interface, 182
linear probing, 174–176, 177, 178, 183, 480, 514, 515
open addressing, 172–174, 182, 183, 480, 514
pseudorandom probing, 178, 179, 181, 183, 515
quadratic probing, 176–178, 181, 183, 480, 514, 515
randomization, 480
removing items, 174
resizing, 171
selections (combinations)
defined, 209
summary of concepts, 480
useful features, 171
hashing
defined, 170
double, 178–179, 181, 183, 480, 514–515
heads/tails. See coin flips
heaps
classes, 237
defined, 187
heap-based priority queues, 127, 142
characteristics, 159
complete binary tree in array, 139–140, 144, 145, 161, 236–237
countingsort compared to, 157
mergesort compared to, 154
quicksort compared to, 152
sub O(N log N) algorithms, 156
height, trees/nodes, 229, 231, 271
heuristics
decision trees
branch and bound technique, 309–310, 318, 320, 321, 323, 432, 483, 531
hill climbing, 314–316, 320, 321, 323, 483
map-coloring algorithms, 367
random path selection, 311–314
simulated annealing, 314, 320, 321, 483
sorted hill climbing, 316, 320, 323, 483
exponential runtimes, 16
Warnsdorff's heuristic, 209, 216, 225, 518
hieroglyphics, 397
higher dimension arrays, nonzero lower bounds, 91–94
Hilbert curves, 196–197, 199, 200, 220–222, 224, 225, 516, 518
hill climbing, 314–316, 320, 321, 323, 367, 375, 483
horticulture, 227. See also trees
Huntington's disease, Folding@home project, 439
I
impossible interview puzzles, 465, 467, 468, 469, 472, 552
ImprovedBubblesort example program, 511
in-degree, nodes, 326, 327, 328, 375, 535
inductive reasoning, tree theorems, 233, 481, 519–520
initial moves and responses, 302–303, 482
initiator curve, 193–194, 195, 196, 481
inorder traversal, 240–241, 244, 245, 247, 250–251, 254, 272, 273, 482, 520–521
InsertCell algorithm, 61–62, 64, 65–66, 69, 81, 498–500
insertionsort algorithm
characteristics, 159
definition, 479
For i loop, 160
QueueInsertionsort example program, 510
selectionsort compared to, 82, 500
StackInsertionsort example program, 509
10 floating-point values, 161, 511
InsertionsortPriorityQueue example program, 510
int[,] numbers = new int[10, 20];, 84–85
integrity, consensus problem, 456
interface, hash table, 182
intermediate values, storing, 218–219, 481
interpolation search
InterpolationSearch example program, 513
assumptions, 465
back-of-the-envelope calculations, 467, 472
creativity, 465, 466, 467, 468, 472
critical-thinking ability, 465, 468, 472
discussion afterwards, 467–468, 473
glib answer, 471
impossible, 465, 467, 468, 469, 552
problem-solving ability, 467, 473, 486
problem-solving tips, 470
salvaging bad questions, 468
summary of concepts, 486
trivia, 467, 468–469, 472, 486
working backwards, 466, 467, 472, 486
intuitive approach, to algorithms, 2
intuitive description, trees, 227–228
iterating, over linked lists, 57
J
Java's Arrays.sort library method, 152, 155
job interview puzzles. See interview puzzles
job shop scheduling, 430
K
keys
duplicated letters, 417
public-key encryption, 412–413, 415, 416, 485
symmetric-key encryption, 412, 415
kitchen remodeling, 355–359, 375
knapsack problem, 16, 319–320, 417, 423, 430, 431, 432, 433, 448, 546
knight's tour problem, 206–209, 216, 223, 225, 518
knowledge trees, 256–258, 274, 482, 521
Koch snowflakes, 195, 223–224, 516
KochSnowflake example program, 516
label-correcting shortest paths, 344–345, 352, 483, 533
label-setting shortest paths, 340–343, 344, 350, 352, 483, 533
Lamport, Leslie, 460
Landis, E. M., 278. See also AVL trees
last_added, 67
last-in-first-out. See LIFO
LCM. See least common multiple
LeadsToSolution, 202
leaf nodes, 228, 231, 232, 481
least common ancestor (first common ancestor), 229, 231
least common multiple (LCM), 53, 492
left rotations, 279–281, 524–525
lieutenants. See generals problem
LIFO (last-in-first-out), 111, 117, 128, 333, 479
linear arrays. See one-dimensional arrays
linear congruential generators, 26–29
linear probing, 174–176, 177, 178, 183, 480, 514, 515
linear search (exhaustive search)
linked lists, 164
sorted arrays, 164
speed, 167
LinearLinkedListSearch example program, 512
LinearProbing example program, 175, 514
LinearSearch example program, 512
linked lists, 55–82. See also cells
doubly linked lists
graphical representation, 56
linear search, 164
operations, 478
sorting
insertionsort algorithm, 68–69
selectionsort algorithm, 69–70
summary of concepts, 478
links. See also networks
costs, 326, 327, 328, 329, 338, 340, 342, 344
livelock, 450, 451, 452, 462, 485, 550
longest path, 430
loops. See also cycles; For loop; While loop
algorithms, 8
BreakLoopHashtable sample program, 74–75
BreakLoopMarking sample program, 73
BreakLoopTortoiseAndHare example program, 500
circular linked lists, 72
For i loop, insertionsort algorithm, 160
linked list reversal, 76, 77–78
networks, 326
lower bound, nonzero, 89–90, 108, 479, 511
lower triangular arrays, 109, 502
loyalty. See generals problem
M
mad cow, Folding@home project, 439
maintainability, algorithm feature, 6, 477
Mandelbrot set, 447
manhole covers, round, 465, 466
four-coloring, 362–363, 367, 375, 484
hill-climbing strategy, 367
other algorithms, 367
three-coloring, 362, 363, 364, 367, 375, 484, 535, 537
two-coloring, 360–361, 375, 484, 537
Map2DArray, 85
mapping
hash tables, 480
marbles, interview puzzles, 474, 486, 551–553
matching parentheses, 378–380, 381, 394
mathematical expressions. See expressions
airline connectivity matrix, 94–95, 97
online article, 106
sparse
column-ordered, 107
maximal flow algorithm, 368–370, 371, 373, 374, 376, 426, 484, 536
maximum, one-dimensional arrays, 86–88
maximum independent set, 430
maximum leaf spanning tree, 430
McDowell, Gayle Laakmann, 474
median, of arrays, 87–88, 108, 501–502
memory. See also stacks
garbage-collection method, 63, 105
heaps
classes, 237
defined, 187
heap-based priority queues, 127, 142
mapping array entries to memory locations, 84–85
MoveMemory, 18
recursion algorithms, 187
RtlMoveMemory, 18
merges
mergesort algorithm
characteristics, 159
divide-and-conquer approach, 19, 153, 159
external sorting, 155, 159, 480
Java's Arrays.sort library method, 152, 155
multiple processors, 449
parallelism, 154, 155, 159, 480
performance Θ(N log N), 420, 421
sub O(N log N) algorithms, 156
Microsoft, interview puzzles, 465, 473, 555
MidpointRectangleRule example program, 495–496
MilkyWay@home, 439
minimal flow cut problem, 372–374, 376, 537
Minimal Flow Cut tool, 372, 537
minimal spanning trees, 329, 338–339, 350, 352, 483, 533
minimax strategy, 298–302, 322, 482
minimum, one-dimensional arrays, 86–88
minimum degree spanning tree, 430
minimum k-cut, 430
Misra/Chandy solution, 451, 462, 548
modeling accuracy, 478. See also rectangle rule; trapezoid rule
Monte Carlo integration, 48, 52, 54, 478, 496
Moore. See Boyer-Moore algorithm
Moore, Gordon E., 435
MoveMemory, 18
MultiHeadedQueue example program, 510
multiple cores, 435, 440, 446, 462, 485
multiple CPUs, 155, 432, 438–439, 440, 449, 485
multiple linear congruential generators, 27
multiplication
sparse matrices, 107, 109, 508–509
two-dimensional matrices, 106
multiplicative inverse, 412, 413–414
MultiplicativeInverse program, 414, 418
multithreaded linked lists, 70–71, 82, 500
mutexes, 442–445, 447, 462, 548
N
N!. See factorial function
naughts and crosses. See tic-tac-toe
NDArray sample program, 94
neighbors, 325, 328, 329, 333, 334, 335
nested loops, 10, 347, 349–350
.NET Framework
BinarySearch method, 163
exercises, 351–353, 375–376, 532–537
four-coloring, 362–363, 367, 375, 484
hill-climbing strategy, 367
other algorithms, 367
three-coloring, 362, 363, 364, 367, 375, 484, 535, 537
two-coloring, 360–361, 375, 484, 537
topological sorting, 355–359, 375, 484
breadth-first traversal, 334–335, 342, 350, 355, 483
depth-first traversal, 331–334, 335, 350, 355, 483, 520
NetworkMaker example program, 351, 532–533, 534, 535, 536, 537
networks
augmenting paths, 369, 370, 373, 376, 484, 535
connected components, 326, 327, 335, 336–337, 351, 359, 361, 362, 363, 364, 532
connectivity testing, 335–337, 350, 483
cycle detection, 359
directed, 326–327, 328, 329, 351, 532
distributed, 440
all-pairs shortest paths, 345–350, 353, 483, 534
label-correcting shortest paths, 344–345, 352, 483, 533
label-setting shortest paths, 340–343, 344, 350, 352, 483, 533
as graphs, 325
links
costs, 326, 327, 328, 329, 338, 340, 342, 344
maximal flow, 368–370, 371, 373, 374, 376, 426, 484, 536
minimal flow cut problem, 372–374, 376, 537
nodes
neighbors, 325, 328, 329, 333, 334, 335
partial ordering, 356–357, 484
planar, 363, 367, 375, 430, 431
residual capacity, 369–370, 373, 376, 448, 535
spanning trees
defined, 337
minimal, 329, 338–339, 350, 352, 483, 533
trees compared to, 227, 322, 325, 332
undirected, 326, 327, 328, 329, 335, 337, 360, 545
work assignments, 370–371, 376, 426, 484, 536, 537
Newton-Raphson method, 49–51, 54, 488, 496
NewtonsMethod sample program, 51
NEXPSPACE, 423
NextIndex1, NextIndex2 and, 115–116, 128, 509
NFAs. See nondeterministic finite automata
node class, networks, 328–332, 483
node splits, 283–284, 291, 482
nodes. See also networks; trees
defined
trees, 231
first common ancestor, 229, 231
network
in-degree, 326, 327, 328, 375, 535
neighbors, 325, 328, 329, 333, 334, 335
out-degree, 326, 327, 328, 375, 535
sorted trees
finding, 247
3-node, 282
2-node, 282
noise, atmospheric, 26
nondeterministic complexity classes, 423
nondeterministic computers, 421–422, 423, 424, 445, 485
nondeterministic finite automata (NFAs), 386–387
nondeterministic polynomial time. See NP
nonindexed database searches, 448
nonrecursive Factorial algorithm, 217, 225, 518
nonrecursive Hilbert curve algorithm, 220, 221–222, 225, 518
NonrecursiveFactorial example program, 518
NonrecursiveFibonacci example program, 518
NonrecursiveFibonacci2 example program, 518
NonrecursiveHilbert example program, 518
nonuniform distributions
PRNGs, 33
nonzero lower bounds, 89–91, 108, 479, 511
not_sorted, 136
NP
defined, 423
NP-complete, 424, 425, 426, 427, 429–431
P equal NP question, 423, 431, 485
P is subset of NP, 423
quantum computing, 445
NPSPACE, 423
null, 13
numeric quadrature. See numerical integration
adaptive quadrature, 44–47, 52
data structures, 52
fast exponentiation, 35–36, 41, 53, 413, 478, 492–493
GCDs
cryptographic routines, 33
Euclid's algorithm, 33–35, 53, 413, 492
GcdTimes example, 494
Monte Carlo integration, 48, 52, 54, 478, 496
prime factors
Carmichael numbers and prime factors algorithm, 53, 494–495
defined, 36
Fermat's primality test, 6, 40, 52, 478
sieve of Eratosthenes, 39–40, 53, 422, 478, 494
summary of concepts, 478
uses, 51
rectangle rule, 42–43, 44, 478
O
O(log N), 12, 14, 15. See also balanced trees
O(N log N), 15, 69, 88. See also sorting algorithms
O(N2), 7, 10, 15, 18, 20. See also sorting algorithms
Θ(g(N)), 420
obscurity, 397, 398, 399, 415, 540
1,000 integers, 511
1,000 names, 512
100,000 integers with values between 0 and 1 billion, 161, 512
100,000 integers with values between 0 and 1,000, 161, 512
1 million floating-point values, 162, 512
one-dimensional arrays (linear arrays)
finding items, 86
finding minimum, maximum, average, 86–88
graphical representation, 84
int[,] numbers = new int[10, 20];, 84
median of, 87–88, 108, 501–502
one-time pads, 404, 408, 418, 484, 541, 542
OneTimePad example program, 542
open addressing, 172–174, 182, 183, 480, 514
optimization problems. See also decision trees
complexity theory, 427–429, 482, 485
decision trees, 482
partition problem, 306–310, 317, 323
ordered hashing, 179–181, 182, 515
OrderedDoubleHashing example program, 514
OrderedQuadraticHashing example program, 514
ordering, partial, 356–357, 484
out-degree, nodes, 326, 327, 328, 375, 535
P
P. See also NP
defined, 422
P equal NP question, 423, 431, 485
P is subset of NP, 423
panic, interview puzzles, 468, 469, 473
parallel algorithms
debugging, 485
embarrassingly parallel algorithms, 447–449, 485
multiple CPUs, 435
parallelism. See also distributed algorithms
bucketsort algorithm, 480
complexity theory, 432
distributed computing, 436, 438–440, 446, 462, 485
mergesort algorithm, 154, 155, 159, 480
multiple cores, 435, 440, 446, 462, 485
multiple CPUs, 155, 432, 438–439, 440, 449, 485
quantum computing, 435, 446, 485
quicksort algorithm, 152, 154, 159, 480
scarcity, 446
systolic arrays, 436–438, 446, 462, 485, 547
task, 440
parentheses, matching, 378–380, 381, 394
ParenthesisMatching example program, 537
Parkinson's disease, Folding@home project, 439
parse trees, 380, 383, 387, 395, 396, 484, 539
partial ordering, 356–357, 484
partition problem, 305–317, 319, 320, 321, 323, 431, 433
PartitionProblem example program, 531–532
passing methods, preorder traversal, 240
paths, network. See networks
P-boxes, 409
perfect tree, 231
permutation boxes, 409
permutations
defined, 209
petaflop, 439
philosophers problem, dining, 445, 449–452, 462–463, 485, 548–549, 550
pictures
balanced trees, 277
solving interview puzzles, 471
pill bottles, interview puzzles, 475, 558
placeholder. See sentinels
plaintext message, 398
planar network, 363, 367, 375, 430, 431
PlanetList example program, 500
planets, linked list, 70–71, 82, 500
playing cards. See cards
polynomial time. See NP; P
polynomials
functions, 18
polynomial-time reductions, 424, 425, 426, 431, 432, 433, 485, 544
popping items, 112, 113, 114, 115–116
postal services
Chinese postman problem, 429
TSP, 320
postorder traversal, 242–243, 244, 272, 482, 520
precalculated values, fast exponentiation, 478
prefix trees, 266. See also tries
preorder traversal, 238–240, 244, 271, 272, 331, 482, 520
Pretty Good Privacy program, 415
primary clustering, 175–177, 178
prime factors
Carmichael numbers and prime factors algorithm, 53, 494–495
defined, 36
Fermat's primality test, 6, 40, 52, 478
sieve of Eratosthenes, 39–40, 53, 422, 478, 494
priority inversion problem, 444
priority queues, 127, 129, 142, 161, 479, 510, 511
PriorityQueue example program, 511
PRNGs (pseudorandom number generators)
biased, 29
CSPRNGs
disadvantages, 29
unbreakable encryption scheme, 418, 542
dining philosophers problem, 450
fair, 29
linear congruential generators, 26–29
nonuniform distributions, 33
probabilistic algorithm, 41, 51, 478
probabilistic computers, 445
probabilistic method, interview puzzles, 469
probe sequences, 173, 174, 175, 176, 177, 178, 179, 180, 181, 183, 513, 514, 515
probing
linear, 174–176, 177, 178, 183, 480, 514, 515
pseudorandom, 178, 179, 181, 183, 515
quadratic, 176–178, 181, 183, 480, 514, 515
problem structure, interview puzzles, 469
problem-solving ability, 467, 473, 486
problem-solving tips, 470
proof-of-concept demonstrations, quantum computing, 445
proofs
four-coloring theorem, 363
inductive reasoning, tree theorems, 233, 481, 519–520
intuitive approach to algorithms, 2
leaf and full nodes, binary trees, 232
random array, 32
pseudocode
balanced trees, 277
problem, 6
pseudorandom number generators. See PRNGs
pseudorandom probing, 178, 179, 181, 183, 515
PseudoRandomProbing example program, 514
PSPACE, 423
public grid projects, 439–440, 446, 462
public-key encryption, 412–413, 415, 416, 485
pushdown stack, 112
pushing items, 112, 113, 114, 115–116
puzzles. See interview puzzles
Q
quadratic equation, 96
quadratic probing, 176–178, 181, 183, 480, 514, 515
QuadraticProbing example program, 177, 514
quadrature, adaptive, 44–47, 52
quantum computing, 435, 446, 485
quantum-size transistors, 435, 445
qubits, 445
queens problem. See eight queens problem
QueueInsertionsort example program, 510
arrays compared to, 108
deques, 127–128, 129, 479, 510
FIFO, 123, 128, 244, 334, 335, 479
insertionsort algorithm, 127, 129, 510
priority, 127, 129, 142, 161, 479, 510, 511
selectionsort algorithm, 129, 510
summary of concepts, 479
QueueSelectionsort example program, 510
characteristics, 159
countingsort compared to, 157
divide-and-conquer strategy, 153
implementation
with stacks, 149
mergesort compared to, 153–155
parallelism, 152, 154, 159, 480
picking dividing item, 148
sub O(N log N) algorithms, 156
upper and lower bounds, 420–421
using, 152
when to use, 19
worst-case performance O(N2), 7
QuicksortQueue example program, 511
QuicksortStack example program, 511
R
race conditions, 440–444, 446, 462, 548
radiation detector, 26
radio waves, static, 26
radioactive sample, 26
random number generators, true, 25–26. See also PRNGs
random numbers, true, 26
random path selection, decision trees, 311–314
random searches, 448
dining philosophers problem, 450
hash tables, 480
interview puzzles, 469
summary, 478
Raphson method. See Newton-Raphson method
ray tracing, 447
reachable node, 326, 327, 328, 335
receiver, 398
rectangle rule, 42–43, 44, 478
RectangleRule sample program, 42–43
backtracking algorithms, 201–203
defined, 185
eight queens problem, 203–206, 208, 223, 224, 322, 518
factorial algorithm
factorial function (N!), 15, 16, 17, 18, 20, 186–188, 189, 478, 481
Hilbert curves, 196–197, 199, 200, 220–222, 224, 225, 516, 518
important features, 186
interpolation search, 168, 513
knight's tour problem, 206–209, 216, 223, 225, 518
Koch snowflakes, 195, 223–224, 516
memory, 187
permutations
defined, 209
removal, 216
general algorithm for, 220–222, 481
storing intermediate values, 218–219, 481
tail recursion removal, 216–218
Sierpinski carpet, 201, 224, 517–518
Sierpinski curves, 197–200, 224, 516, 517
Sierpinski gaskets, 200–201, 224, 517
Tower of Hanoi puzzle, 119–121, 189–193, 223, 515–516
RecursiveBinarySearch example program, 513
RecursiveInterpolationSearch example program, 513
RecursiveLinearSearch example program, 512
reductions
polynomial-time reductions, 424, 425, 426, 431, 432, 433, 485, 544
regular expressions, 381–387, 394, 395, 484, 537, 538
relational databases, B-trees, 293
remodeling kitchen, 355–359, 375
removal. See recursion
removing items
hash tables, 174
reporting problem, 427–429, 433, 485, 546
ReportKnapsack, 546
residual capacities, 369–370, 373, 376
residual capacity networks, 369–370, 373, 376, 448, 535
resizing hash tables, 171
resource hierarchy solution, dining philosophers problem, 450–451
retreat, attack. See consensus problem reversal
arrays, 117
right rotation, 279–281, 524–525, 526
Rivest, Ron, 412
rolls. See dice rolls
root at top, tree data structures, 228, 271
roots. See also nodes
rotations
round manhole covers, 465, 466
row/column transposition cipher, 399–401, 402, 417
RowColumnTransposition example program, 540
RSA algorithm, 412–415, 416, 417, 418
RtlMoveMemory, 18
Fibonacci function compared to, 23, 489–490
graph, 18
list, in order of increasing speed of growth, 478
visualizing, 17
runtime performance. See also Big O notation; sorting algorithms
recursive algorithms, 187
sorting algorithms, 131
Tower of Hanoi puzzle, 193
traversal, 244
understanding, 1
S
sales program, nonzero bounds, 90
salesman problem. See traveling salesman problem
salvaging bad questions, 468
sample variance, one-dimensional array, 108, 501
satisfiability problem (SAT), 321–322, 424–425, 431
S-boxes, 409
Schneier, Bruce, 416
school bus, baseballs in, 467, 471
scratch array, 154
searching
brute-force, 299, 388, 389, 396, 410, 432, 448
nonindexed database, 448
random, 448
tools, 163
traversal and, 237
binary search
speed, 167
interpolation search
linear search (exhaustive search)
linked lists, 164
sorted arrays, 164
speed, 167
summary of concepts, 480
searching decision trees. See decision trees
searching game trees. See game trees
secondary clustering, 177, 179
security through obscurity, 397, 398, 399
selections (combinations)
defined, 209
selectionsort algorithm
characteristics, 159
defined, 479
insertionsort compared to, 82, 500
program, 160
QueueSelectionsort example program, 510
StackSelectionsort example program, 509
10 floating-point values, 161, 511
SelectKofN example program, 518
self-similar fractals, 193–194, 200, 223, 481
sender, 398
Shamir, Adi, 412
Shannon number, 298
Shor's algorithm, 445
short circuiting, 308, 310, 323
shortest-path algorithms
all-pairs shortest paths, 345–350, 353, 483, 534
label-correcting shortest paths, 344–345, 352, 483, 533
label-setting shortest paths, 340–343, 344, 350, 352, 483, 533
stacks, 117
Sierpinski, Waclaw Franciszek, 201
Sierpinski carpet, 201, 224, 517–518
Sierpinski curves, 197–200, 224, 516, 517
Sierpinski gaskets, 200–201, 224, 517
sieves
general number field sieve, 445
sieve of Eratosthenes, 39–40, 53, 422, 478, 494
simple substitution cipher, 404, 407–408
Simpson's rule, 44
simulated annealing, 314, 320, 321, 483
single swap strategy, 313
six-sided dice. See dice rolls
64-bit double-precision floating-point number, 188
snowflakes, Koch, 195, 223–224, 516
Social Security number, 292
socks, interview puzzles, 474, 551
solar system's planets, linked list, 70–71, 82, 500
solutions. See exercises
sorted binary trees, 248, 250, 271, 278, 283
sorted chaining, 480, 513, 514
sorted hill climbing, 316, 320, 323, 483
sorted trees. See also balanced trees
nodes
finding, 247
sentinels, 246
SortedChaining example program, 513
sorting
insertionsort algorithm, 68–69
selectionsort algorithm, 69–70
stable, 155
tools, 132
topological, 355–359, 375, 484
train cars
stack insertionsort algorithm, 129, 509
stack selectionsort algorithm, 129, 509–510
zero-time sort algorithm, 438, 446, 462, 547–548
sorting algorithms, 131–162. See also specific sorting algorithms
characteristics/techniques, 159–160
O(N log N) algorithms, 138–155
reasons for using, 131
runtime performance, 131
sub O(N log N) algorithms, 156–159
types, 131
space-filling curves, 200
spaghetti. See dining philosophers problem
spanning trees
defined, 337
degree-constrained, 430
maximum leaf spanning tree, 430
minimal, 329, 338–339, 350, 352, 483, 533
minimum degree spanning tree, 430
find row or column, 100
getting values, 101
sparse matrices
column-ordered, 107
sparse triangular array, 109, 504
special alphabets, 397
specialized tree algorithms, 256–270
animal game, 256–258, 274, 482, 521–522
expression evaluation, 258–260, 274–275
tries, 266–270, 275, 512, 523–524
special-purpose arrays. See arrays
splits
spring-loaded stack, of plates, 111–112
stable sorting, 155
StackInsertionsort example program, 509
arrays compared to, 108
insertionsort algorithm, 121–122, 128–129, 509
quicksort implementation, 149
selectionsort algorithm, 122–123, 129, 509–510
shortest-path algorithms, 117
summary of concepts, 479
StackSelectionsort example program, 509
standard deviation, one-dimensional array, 108, 501
starvation, 444
state transition diagram, 382–383, 395, 396, 537, 538, 539
state transition table, 383
static, radio waves, 26
storing intermediate values, 218–219, 481
stride, 174, 176, 178, 179, 181, 514
Boyer-Moore algorithm, 377, 388–391, 394, 484
DFAs, 381–386, 394, 395, 396, 421, 484, 537, 538, 539
edit distance algorithm, 3, 374, 391–394, 396, 484, 540
matching parentheses, 378–380, 381, 394
parse trees, 380, 383, 387, 395, 396, 484, 539
regular expressions, 381–387, 394, 395, 484, 537, 538
summary of concepts, 484
strongly connected network, 326, 328
stupid questions, interview puzzles, 472
sub O(N log N) algorithms. See sorting algorithms
subexpressions, 258–259, 384–386, 387
subset sum problem, 317–318, 427, 428, 431
substitution ciphers, 404–408, 416
substitution-permutation network cipher, 409–410, 416
summary of algorithmic concepts. See algorithmic concepts
superposition, 445
SwapColumns example program, 540
swapping strategies, 313
SwapRowsAndColumns example program, 541
symmetric traversal. See preorder traversal
symmetrically threaded tree, 251
symmetric-key encryption, 412, 415
synchronization
generals' attacks, 452
synchronized philosophers, 450, 451, 452, 462, 548
systolic arrays, 436–438, 446, 462, 485, 547
T
tail recursion removal, 216–218
tails/heads. See coin flips
tall, thin trees, 147, 148, 233, 246, 247, 271, 277, 283, 287, 293. See also balanced trees
tape drives, mergesort algorithm, 155
task parallelism, 440
10 floating-point values, 161, 511
teraflop, 439
termination, consensus problem, 455
terminology
tetrahedral arrays, 109, 503–504
TextDisplay example program, 520
thin trees. See tall, thin trees
defined, 250
symmetrically, 251
ThreadedTree example program, 521
threads
3CNF (three-term conjunctive normal form), 425
3-node, 282
3SAT problem, 321–322, 425, 431
three-coloring maps, 362, 363, 364, 367, 375, 484, 535, 537
three-cycle problem, 432, 542–543
three-dimensional arrays
4×4×3, 92
graphical representation, 84
mapping, 85
row-major order, 85
three-dimensional shape, Monte Carlo integration, 54, 496
three-dimensional space, octtrees, 266, 482
three-partition problem, 431
three-person general and lieutenant problem, 454, 463
three-term conjunctive normal form (3CNF), 425
ticks
zero-time sort algorithm, 438, 446, 462, 547–548
tic-tac-toe (naughts and crosses)
initial moves and responses, 302–303
topological sorting, 355–359, 375, 484
tortoise-and-hare algorithm, 78–80, 82, 474, 500
totient function, Euler's, 412, 413, 414
Tower of Hanoi puzzle, 119–121, 189–193, 223, 515–516
TowerOfHanoi example program, 190, 515
train cars. See sorting
traitors. See generals problem
transposition ciphers, 399–404, 409, 417, 484
TrapezoidRule sample program, 43–44, 45, 46
traveling salesman problem (TSP), 16, 200, 320–321, 417, 423, 429, 431, 432
defined, 237
depth-first, 243–244, 256, 272, 331–334, 335, 350, 355, 483, 520
inorder, 240–241, 244, 245, 247, 250–251, 254, 272, 273, 482, 520–521
postorder, 242–243, 244, 272, 482, 520
preorder, 238–240, 244, 271, 272, 331, 482, 520
runtimes, 244
searching and, 237
steps, threaded tree, 251, 255–256
tree theorems, inductive reasoning, 233, 481, 519–520
trees, 227–275. See also balanced trees; decision trees; nodes; subtrees
binary
defined, 230
facts, 232
fat, 233
sorted, 248, 250, 271, 278, 283
call tree, 146, 147, 154, 188, 189
complete binary trees
in arrays, 139–140, 144, 145, 161, 236–237
B-trees, 287
defined, 230
family tree analogy, 228
fat, 233
intuitive description, 227–228
knowledge, 256–258, 274, 482, 521
networks compared to, 227, 322, 325, 332
parse, 380, 383, 387, 395, 396, 484, 539
recursive definition, 229
sorted
finding nodes, 247
sentinels, 246
spanning trees
defined, 337
degree-constrained, 430
maximum leaf spanning tree, 430
minimal, 329, 338–339, 350, 352, 483, 533
minimum degree spanning tree, 430
specialized tree algorithms, 256–270
animal game, 256–258, 274, 482, 521–522
expression evaluation, 258–260, 274–275
tries, 266–270, 275, 512, 523–524
tall, thin, 147, 148, 233, 246, 247, 271, 277, 283, 287, 293
defined, 250
symmetrically, 251
XML and, 236
treesort algorithm, 247
triangles. See Koch snowflakes; Sierpinski gaskets
sparse arrays compared to, 97, 98–99
tetrahedral arrays, 109, 503–504
tries (prefix trees), 266–270, 275, 512, 523–524
trivia, 467, 468–469, 472, 486
TRNGs. See true random-number generators
true random numbers, 26. See also dice rolls
true random-number generators (TRNGs), 25–26. See also PRNGs
TSP. See traveling salesman problem
Turing, Alan, 421
Turing machines, 421–422, 424, 425
two generals problem, 452–453, 463, 485
2-node, 282
two-coloring maps, 360–361, 375, 484, 537
TwoDArray sample program, 90–91
two-dimensional arrays
graphical representation, 84
int[,] numbers = new int[10, 20];, 84–85
two-dimensional matrices, multiply, 106
two-dimensional space. See quadtrees
U
unbounded knapsack, 431
unbreakable encryption scheme, 418, 542
undirected networks, 326, 327, 328, 329, 335, 337, 360, 545
uniform value distribution
bucketsort, 157, 160, 162, 512
upper triangular arrays, 94, 109, 502
V
validity, consensus problem, 456
values array, 91–94, 115, 154, 157
vehicle routing, 431
vertex coloring, 430
vertex cover, 431
Vigenère cipher, 405–407, 408, 411, 416, 417, 541
virtual backlinks, 369–370, 373
virtual computer, 381, 439, 484
visualizing runtime functions, 17
W
waiter, dining philosophers problem, 451, 550
Warnsdorff's heuristic, 209, 216, 225, 518
weakly connected network, 326, 328
While loop
described, 4
general recursion removal, 220
heaps, 143
iteration over linked list, 57
ordered hash table, 181
sentinels, 59
tail recursion, 218
“Why Are Manhole Covers Round?” article, 466
work assignment, 370–371, 376, 426, 484, 536, 537
work related questions, interview puzzles, 472
working backwards, interview puzzles, 466, 467, 472, 486
worst-case performance, algorithms, 7
X
XML (eXtensible Markup Language)
Beginning XML, 236
network data, 330
trees and, 236
Z