Index

A

abba dabba search, 389–391

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

AVL trees, 278–281

B-trees, 288–289

2-3 trees, 283–284

addition

sparse matrices, 106–107, 109, 505–508

triangular arrays, 109, 504

addressing, open, 172–174, 182, 183, 480, 514

Adelson-Velskii, G. M., 278. See also AVL t rees

adjacent nodes, 326, 327, 328

Adleman, Leonard, 412

Advanced Encryption Standard (AES), 398, 409–410, 411, 416

after_me, 61–62

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

algorithm basics, 477–478

arrays, 479

balanced trees, 482

complexity theory, 485

cryptographic algorithms, 484–485

decision trees, 482–483

distributed algorithms, 485–486

hash tables, 480

interview puzzles, 486

linked lists, 478

network algorithms, 483–484

numeric algorithms, 478

queues, 479

recursion, 480–481

searching algorithms, 480

sorting algorithms, 479–480

stacks, 479

string algorithms, 484

trees, 481–482

algorithms

approach, 2

basics, 1–23

exercises, 20–23, 487–490

summary of concepts, 477–478

behavior, 2, 477

confusing, 6

correctness, 6, 477

data structures compared to, 3, 22, 477, 489

defined, 1, 3

efficiency, 7, 477

features, 6–7, 477

groupings, 2

intuitive approach, 2

maintainability, 6, 477

memory requirements, 2, 477

performance characteristics, 19

speed, 2, 477

themes, 2

all-pairs shortest paths, 345–350, 353, 483, 534

alphabets, special, 397

Alzheimer's, Folding@home project, 439

ancestors, 228, 230

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

array packing, 91, 95, 479

arrays, 83–109. See also one-dimensional arrays; sparse arrays; three-dimensional arrays; triangular arrays; two-dimensional arrays

Via, 346–349, 353, 534

associative, 170

basic concepts, 83–86

circular, 125–126, 128, 479

complete binary trees in, 139–140, 144, 145, 161, 236–237

defined, 83, 479

Distance, 346, 348, 349, 534

exercises, 108–109, 501–509

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

queues in, 124–127

randomizing, 31–33

rectangular, 109, 503

reversing, 117

scratch, 154

slice_size, 93–94

sorting algorithms, summary of characteristics, 159–160

special-purpose, 83, 108

stacks compared to, 108

stacks in, 113–115

summary of concepts, 479

systolic, 436–438, 446, 462, 485, 547

tetrahedral, 109, 503–504

Array.Sort, 18–19

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

AVL trees

adding values, 278–281

defined, 278, 482

deleting values, 281–282

exercises, 293–294, 524–525

inventors, 278

B

backlinks, 369–370, 373

back-of-the-envelope calculations, 467, 472

backtracking algorithms, 201–203. See also chess

balanced trees, 277–295

defined, 277

exercises, 293–295, 524–530

kinds, 277

node splits, 283–284, 291, 482

O(log N) time, 277, 281–282, 293

pictures, 277

rotations

left, 279–281, 524–525

right, 278–281, 524–525, 526

summary of concepts, 482

tall, thin trees, 147, 148, 233, 247, 271, 277, 283, 287, 293

bank examples

multiheaded queue, 129, 510

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 coin, 29–31, 52, 491

biased dice roll, 478, 491

biased PRNG, 29

defined, 29, 478

exercises, 52, 491

fairness from biased sources, 30–31

Big O notation

complexity theory, 420–421

described, 7–11, 477

log bases, 12, 14, 233

Big Omega notation, 420

Big Theta notation [Θ(g(N))], 420–421

bin packing, 318, 417, 429

bin sort. See bucketsort algorithm

binary node class, 234–235

binary search

described, 165–166, 169, 480

exercise, 168, 513

speed, 167

binary trees

complete

in arrays, 139–140, 144, 145, 161, 236–237

B-trees, 287

defined, 230

sorted, 12–13

defined, 230

facts, 232

fat, 233

properties, 231–233

sorted, 248, 250, 271, 278, 283

BinarySearch example program, 513

BinarySearch method, 163

bipartite detection problem, 432, 542–543

bipartite matching, 371, 426

bipartite network, 371, 376, 537

bitwise XOR operator, 408, 409, 410

block ciphers, 408–411, 484

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

branches, 227–228, 230, 481

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

B+trees, 291–293, 295, 530

B-trees, 287–290

defined, 287, 482

exercises, 294–295, 528–530

top-down, 291, 482

variations, 291–293

bubblesort algorithm

characteristics, 159

comparison, 159–160

described, 135–138, 479

exercises, 160–161, 511

improvements, 137–138

Bubblesort example program, 511

buckets

B-trees, 287, 291, 292, 295, 528

bucketsort, 157–159

hash table with chaining, 171–172

bucketsort algorithm

characteristics, 160

comparison, 159–160

described, 157–159, 480

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

calculus, 42, 46, 49

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

poker program, 52, 492

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

at beginning, 59–60

at end, 60–61

defined, 55, 478

deleting, 62–63

DPUs, 436–438

FindCellBefore algorithm, 58–59

finding, 57–58

InsertCell algorithm, 61–62, 64, 65–66, 69, 81, 498–500

IntegerCell class, 55–56

marking, 72–74

sentinels, 58–59, 478

chaining

described, 171–172, 480

sorted, 480, 513, 514

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

child node, 228, 230

chimneys in Detroit, interview puzzles, 471

Chinese postman problem, 429

ciphers

block, 408–411, 484

Caesar substitution, 404–405, 406, 407, 416, 417, 541

column transposition, 401–403, 409, 417, 541

Feistel, 410–411, 416

one-time pads, 404, 408, 418, 484, 541, 542

route, 403–404

row/column transposition, 399–401, 402, 417

simple substitution, 404, 407–408

substitution, 404–408, 416

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

circular linked lists, 71–72

circular queue, 125–127

CircularQueue sample program, 126–127

classes

Array class, BinarySearch method, 163

complexity theory, 421–424

heap and, 237

IntegerCell, 55–56

node class, 328–332, 483

tree nodes, 234–236

clique, 430

clique cover problem, 430

clock puzzles, 467, 475

clock synchronization, 460–461, 463–464, 486

clustering

defined, 480

primary, 175–177, 178

secondary, 177, 179

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-major mapping, 84–85

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

building, 236–237

defined, 12, 229, 230

complexity theory, 419–433. See also NP; P

Big O notation, 420–421

bipartite detection problem, 432, 542–543

bipartite matching, 371, 426

classes, 421–424

detection problem, 427–429, 432, 433, 485, 542–543, 546

DTIME, 422, 485

exercises, 432–433, 542–547

EXPTIME, 423, 485

mergesort algorithm, 419

N log N sorting, 419–420

NEXPTIME, 423, 485

NPSPACE, 423

NTIME, 423, 485

optimization problem, 427–429, 482, 485

quicksort algorithm, 420–421

reductions

described, 424–425, 485

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

clusters, 439, 446

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

NFAs, 386–387

nondeterministic, 421–422, 423, 424, 445, 485

quantum computing, 435, 446, 485

Turing machines, 421–422, 424, 425

virtual, 381, 439, 484

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

cookie examples, 30, 31

Cook-Levin theorem, 424

CopyEntries method, 109, 505, 508

copying linked lists, 67–68

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

comparison, 159–160

described, 156–157, 480, 542

exercises, 161, 432, 511, 512

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

exercises, 417–418, 540–542

RSA algorithm, 412–415, 416, 417, 418

summary of concepts, 484–485

cryptographically secure pseudorandom number generators. See CSPRNGs

cryptography

decryption

defined, 398

linear congruential generator, 26–29

defined, 397

digital signatures, 415–416

encryption

AES, 398, 409–410, 411, 416

Blowfish, 398

defined, 398

DES, 411, 416

public-key, 412–413, 415, 416, 485

symmetric-key, 412–415

unbreakable encryption scheme, 418, 542

GCDs, 33

goal, 398

hash values, 415

hieroglyphics, 397

history, 397–398

large exponentiation, 35, 36

obscurity, 397, 398, 399, 415, 540

online information, 416

other uses, 415–416

prime numbers, 37, 39, 40

quicksort, 19, 152

scytale method, 397, 399

security through obscurity, 397, 398, 399

terminology, 398–399

crystals, 314

CSPRNGs (cryptographically secure pseudorandom number generators)

described, 28–29, 31

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

defined, 326, 327

Floyd's cycle-finding algorithm, 78

Hamiltonian, 430, 433, 543, 544, 545

loops, 328, 332

odd-cycle problem, 432, 543

three-cycle problem, 432, 542–543

D

Data Encryption Standard (DES), 411, 416

data parallelism, 436, 440

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

enormity, 297–298

exercises, 322–323, 530–532

game trees

defined, 482

heuristics, 303–305, 482

initial moves and responses, 302–303, 482

minimax strategy, 298–302, 322, 482

Reversi game, 304–305

tic-tac-toe, 298–303, 322, 531

interview puzzles, 469

knapsack problem, 319–320

optimization problems, 482

partition problem, 305–317, 319, 320, 321, 323

SAT problem, 321–322

subset sum problem, 317–318

summary of concepts, 482–483

TSP, 320–321

declaration, 4, 5

decryption. See cryptography

degree

defined, 231, 327

in-degree, 326, 327, 328, 375, 535

out-degree, 326, 327, 328, 375, 535

degree-constrained spanning tree, 430

deleting cells, 62–63

deleting values

AVL trees, 281–282

B-trees, 289–290

sorted trees, 248–250

sparse arrays, 104–105

2-3 trees, 284–287

depth, node/tree, 229, 231

depth-first traversals, 243–244, 256, 272, 331–334, 335, 350, 355, 483, 520

deques (double-ended queues), 127–128, 129, 479, 510

Dequeue, 123–127

derivative, of function, 46, 49, 50

DES (Data Encryption Standard), 411, 416

descendants, 228, 231

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

exercises, 52, 53, 491, 492

PRNGs

biased, 478

nonuniform distributions, 33

true randomness, 26

dictionaries, 170. See also hash tables

difficult interview puzzles, 465, 467, 468, 469, 472, 552

digital signatures, 415–416

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

debugging, 446–447

dining philosophers problem, 445, 449–452, 462–463, 485, 548–549, 550

exercises, 462–464, 547–551

general and lieutenants problem, 453–455, 463, 549–550

leader election, 458–459, 486

mutexes, 442–445, 447, 462, 548

snapshot, 459–460, 486

summary of concepts, 485–486

two generals problem, 452–453, 463, 485

distributed computing, 436, 438–440, 446, 462, 485

distributed environments

clusters, 439, 446

grid computing, 439–440, 446, 462

distributed networks, 440

divide-and-conquer approach, 19, 153, 159, 469, 479

divider, 145–146

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

described, 63–65, 478

loops in, 80–81

DPUs (data processing units), 436–438

DrawRelative method, 196, 199

DrawTree example program, 520

DSPACE, 423

DTIME, 422, 485

duplicated letters, keys, 417

duplicates

permutations with, 214–215

selections with, 211–213

E

ED, 267, 269

edges, network, 325, 327

edit distance algorithm, 3, 374, 391–394, 396, 484, 540

efficiency, algorithm feature, 7, 477

eggs, golden, 475, 557–558

eight queens problem, 203–206, 208, 223, 224, 322, 518

embarrassingly parallel algorithms, 447–449, 485

encryption. See cryptography

Enqueue, 123–127

entanglement, 445

equation's roots, 49–51, 496

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

arrays, 108–109, 501–509

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

hash tables, 182–183, 513–515

interview puzzles, 474–475, 551–558

linked lists, 81–82, 497–500

network algorithms, 351–353, 375–376, 532–537

numerical algorithms, 52–54, 491–496

queues, 128–129, 509–510

recursion, 223–225, 515–518

searching algorithms, 168, 512–513

solutions, 487–558

sorting algorithms, 160–162, 510–512

stacks, 128–129, 509–510

string algorithms, 394–396, 537–540

trees, 271–275, 519–524

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

EXPTIME, 423, 485

extending partial ordering. See topological sorting

eXtensible Markup Language. See XML

external nodes, 228, 231

external sorting, 155, 159, 480

F

factorial algorithm

nonrecursive, 217, 225, 518

recursive, 223, 515

tail recursion, 216–217

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

ensuring, 29–30

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

Feistel ciphers, 410–411, 416

fence painting, 22, 185, 489

fencepost problem, 554

Fermat liars, 40, 41, 53

Fermat witnesses, 40–41

Fermat's little theorem, 40

Fermat's primality test, 6, 40, 52, 478

Fibonacci function, 23, 189, 218, 489–490

Fibonacci numbers, 188–189

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 cells, 57–58

finding items, linear arrays, 86

finding minimum, maximum, average, 86–88

finding nodes, sorted trees, 247

finding paths in networks. See networks

finding prime numbers, 39–40

finding zeros, 49–51

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

five-coloring maps, 363–367

flips. See coin flips

floating-point operations per second (flops), 439

floating-point values

1 million, 162, 512

64-bit double-precision, 188

10, 161, 511

flops. See floating-point operations per second

Floyd, Robert, 78, 345

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

selections with, 210–211

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

full trees, 229, 230, 231

function's antiderivative, 42

function's derivative, 46, 49, 50

G

game trees

defined, 482

heuristics, 303–305, 482

initial moves and responses, 302–303, 482

minimax strategy, 298–302, 322, 482

Reversi game, 304–305

tic-tac-toe, 298–303, 322, 531

garbage-collection method, 63, 105

gas cap puzzle, 465, 466

gaskets, Sierpinski, 200–201, 224, 517

GCDs (greatest common divisors)

cryptographic routines, 33

Euclid's algorithm, 33–35, 53, 413, 492

exercises, 53, 492, 494–495

GcdTimes example, 494

LCM, 53, 492

pseudocode example, 3–4

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

get method, 90, 94, 97

gigaflops, 439

girls/boys, percentage in population, 475, 555–556

glib answer, interview puzzles, 471

Go, game, 298

gold bricks, 475, 556–557

golden eggs, 475, 557–558

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

hash tables, 169–183

associative arrays, 170

BreakLoopHashtable sample program, 74–75

chaining

described, 171–172, 480

sorted, 480, 513, 514

clustering

defined, 480

primary, 175–177, 178

secondary, 177, 179

cryptography, 415

dictionaries, 170

exercises, 182–183, 513–515

fill percentage, 170, 173, 174, 181, 182

fundamentals, 170–171

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

requirements, 170, 480

resizing, 171

selections (combinations)

defined, 209

with duplicates, 211–213

without duplicates, 213–214

with loops, 210–211

simple example, 169–170

summary of concepts, 480

useful features, 171

hashing

defined, 170

double, 178–179, 181, 183, 480, 514–515

ordered, 179–181, 182, 515

heads/tails. See coin flips

heaps

classes, 237

defined, 187

described, 140–144

heap-based priority queues, 127, 142

heapsort algorithm, 139–145

characteristics, 159

comparison, 159–160

complete binary tree in array, 139–140, 144, 145, 161, 236–237

countingsort compared to, 157

exercises, 161, 511, 512

implementing, 144–145

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

exhaustive search, 307–308

hill climbing, 314–316, 320, 321, 323, 483

improving paths, 312–313, 483

map-coloring algorithms, 367

random path selection, 311–314

simulated annealing, 314, 320, 321, 483

sorted hill climbing, 316, 320, 323, 483

defined, 209, 303

exponential runtimes, 16

game trees, 303–305, 482

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

improving paths, 312–313, 483

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

arrays, 132–134

characteristics, 159

comparison, 159–160

definition, 479

For i loop, 160

linked lists, 68–69

O(N²) performance, 18, 82

QueueInsertionsort example program, 510

queues, 127, 129, 510

selectionsort compared to, 82, 500

StackInsertionsort example program, 509

stacks, 121–122, 128–129, 509

10 floating-point values, 161, 511

InsertionsortPriorityQueue example program, 510

int[,] numbers = new int[10, 20];, 84–85

IntegerCell class, 55–56

integrity, consensus problem, 456

interface, hash table, 182

intermediate values, storing, 218–219, 481

internal node, 228, 231

interpolation search

described, 166–167, 169, 480

exercises, 168, 513

recursion, 168, 513

speed, 167, 168

InterpolationSearch example program, 513

interview puzzles, 465–475

answering questions, 468–472

asking questions, 467–468

assumptions, 465

back-of-the-envelope calculations, 467, 472

bad, 465–466, 468

creativity, 465, 466, 467, 468, 472

critical-thinking ability, 465, 468, 472

discussion afterwards, 467–468, 473

exercises, 474–475, 551–558

failing, 468, 470–471, 473

glib answer, 471

impossible, 465, 467, 468, 469, 552

online, 473–474

panic, 468, 469, 473

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

ISP, 266, 267

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

described, 397–398

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 curves, 193–195

Koch snowflakes, 195, 223–224, 516

KochSnowflake example program, 516

L

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

leader election, 458–459, 486

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

level, node/tree, 229, 231

liars, Fermat, 40, 41, 53

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)

described, 164–165, 480

exercises, 168, 512

linked lists, 164

recursion, 168, 512

sorted arrays, 164

speed, 167

unsorted arrays, 86, 164–165

LinearLinkedListSearch example program, 512

LinearProbing example program, 175, 514

LinearSearch example program, 512

linked lists, 55–82. See also cells

arrays compared to, 56, 59

basic concepts, 55–56

circular, 71–72

doubly linked lists

described, 63–65, 478

loops in, 80–81

exercises, 81–82, 497–500

graphical representation, 56

linear search, 164

with loops, 71–81

multithreaded, 70–71, 82, 500

operations, 478

planets, 70–71, 82, 500

retracing, 75–76

reversal, 76–78

singly, 56–63

sorted, 65–66

sorting

copying lists, 67–68

insertionsort algorithm, 68–69

selectionsort algorithm, 69–70

summary of concepts, 478

threads, 70–71, 82, 500

linked-list queues, 123–124

linked-list stacks, 112–113

links. See also networks

backlinks, 369–370, 373

costs, 326, 327, 328, 329, 338, 340, 342, 344

defined, 326, 328

directed/undirected, 326, 328

edges, 325, 327

livelock, 450, 451, 452, 462, 485, 550

log bases, 12, 14, 233

log N, 12–14, 17, 478

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

in doubly linked lists, 80–81

For i loop, insertionsort algorithm, 160

linked list reversal, 76, 77–78

linked lists with, 71–81

nested, 10, 347, 349–350

networks, 326

selections with, 210–211

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

map coloring, 359–367

five-coloring, 363–367

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

array entries, 84–85

hash tables, 480

marbles, interview puzzles, 474, 486, 551–553

marking cells, 72–74

matching parentheses, 378–380, 381, 394

mathematical expressions. See expressions

matrices, 105–108

airline connectivity matrix, 94–95, 97

online article, 106

sparse

add, 106–107, 109, 505–508

column-ordered, 107

multiply, 107, 109, 508–509

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

algorithms, 2, 477

array packing, 91, 95, 479

garbage-collection method, 63, 105

heaps

classes, 237

defined, 187

described, 140–144

heap-based priority queues, 127, 142

mapping array entries to memory locations, 84–85

mergesort algorithm, 154–155

MoveMemory, 18

recursion algorithms, 187

RtlMoveMemory, 18

merges

node, 284, 285–286

root, 287, 290

mergesort algorithm

characteristics, 159

comparison, 159–160

described, 153–155

divide-and-conquer approach, 19, 153, 159

exercises, 511, 512

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

modulus operator, 4, 34

Monte Carlo integration, 48, 52, 54, 478, 496

Moore. See Boyer-Moore algorithm

Moore, Gordon E., 435

Moore's Law, 435, 462

MoveMemory, 18

multiheaded queue, 129, 510

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

triangular arrays, 109, 505

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, 15, 17, 478

N!. See factorial function

N log N, 15, 17, 419–420, 478

N², 15, 17, 478

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

Array.Sort, 18–19

BinarySearch method, 163

network algorithms, 325–376

exercises, 351–353, 375–376, 532–537

map coloring, 359–367

five-coloring, 363–367

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

summary of concepts, 483–484

topological sorting, 355–359, 375, 484

traversals, 331–339

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

bipartite, 371, 376, 537

capacitated, 368–370, 376

connected components, 326, 327, 335, 336–337, 351, 359, 361, 362, 363, 364, 532

connectivity testing, 335–337, 350, 483

cycle, 326, 327, 328, 332

cycle detection, 359

directed, 326–327, 328, 329, 351, 532

distributed, 440

edges, 325, 327

finding paths, 339–350

all-pairs shortest paths, 345–350, 353, 483, 534

any path, 339–340

label-correcting shortest paths, 344–345, 352, 483, 533

label-setting shortest paths, 340–343, 344, 350, 352, 483, 533

as graphs, 325

links

backlinks, 369–370, 373

costs, 326, 327, 328, 329, 338, 340, 342, 344

defined, 326, 328

directed/undirected, 326, 328

edges, 325, 327

maximal flow, 368–370, 371, 373, 374, 376, 426, 484, 536

minimal flow cut problem, 372–374, 376, 537

node class, 328–332, 483

nodes

adjacent, 326, 327, 328

neighbors, 325, 328, 329, 333, 334, 335

partial ordering, 356–357, 484

planar, 363, 367, 375, 430, 431

representations, 328–331, 483

residual capacity, 369–370, 373, 376, 448, 535

spanning trees

defined, 337

described, 337–338

minimal, 329, 338–339, 350, 352, 483, 533

strongly connected, 326, 328

terminology, 325–328

trees compared to, 227, 322, 325, 332

undirected, 326, 327, 328, 329, 335, 337, 360, 545

weakly connected, 326, 328

work assignments, 370–371, 376, 426, 484, 536, 537

Newton-Cotes formulas, 42–44

Newton-Raphson method, 49–51, 54, 488, 496

NewtonsMethod sample program, 51

NEXPSPACE, 423

NEXPTIME, 423, 485

NextIndex1, NextIndex2 and, 115–116, 128, 509

NFAs. See nondeterministic finite automata

node class, networks, 328–332, 483

node merges, 284, 285–286

node splits, 283–284, 291, 482

nodes. See also networks; trees

branches, 227–228, 230, 481

child, 228, 230

classes for, 234–236

defined

networks, 325, 328

trees, 231

external, 228, 231

first common ancestor, 229, 231

height, 229, 231, 271

internal, 228, 231

leaf, 228, 231, 232, 481

level/depth, 229, 231

network

adjacent, 326, 327, 328

defined, 325, 328

in-degree, 326, 327, 328, 375, 535

neighbors, 325, 328, 329, 333, 334, 335

out-degree, 326, 327, 328, 375, 535

reachable, 326, 327, 328, 335

parent, 228, 231

root, 228, 229, 231

sorted trees

adding, 245–247

deleting, 248–250

finding, 247

3-node, 282

2-node, 282

vertices, 325, 430, 431

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

1 million integers, 162, 512

PRNGs, 33

nonzero lower bounds, 89–91, 108, 479, 511

not_sorted, 136

NP

defined, 423

NP-complete, 424, 425, 426, 427, 429–431

NP-hardness, 426–427

P equal NP question, 423, 431, 485

P is subset of NP, 423

quantum computing, 445

NPSPACE, 423

NTIME, 423, 485

null, 13

numeric quadrature. See numerical integration

numerical algorithms, 25–54

adaptive quadrature, 44–47, 52

data structures, 52

exercises, 52–54, 491–496

fast exponentiation, 35–36, 41, 53, 413, 478, 492–493

GCDs

cryptographic routines, 33

Euclid's algorithm, 33–35, 53, 413, 492

exercises, 53, 492, 494–495

GcdTimes example, 494

LCM, 53, 492

pseudocode example, 3–4

Monte Carlo integration, 48, 52, 54, 478, 496

prime factors

Carmichael numbers and prime factors algorithm, 53, 494–495

described, 37–39

prime numbers, 36–41

composite numbers, 36, 41, 53

defined, 36

Fermat's primality test, 6, 40, 52, 478

finding, 39–40

sieve of Eratosthenes, 39–40, 53, 422, 478, 494

testing for primality, 40–41

summary of concepts, 478

uses, 51

numerical integration, 42–48

rectangle rule, 42–43, 44, 478

trapezoid rule, 43–45, 478

O

O(1), 9, 11

O(log N), 12, 14, 15. See also balanced trees

O(N), 8, 9, 10, 11, 15

O(N log N), 15, 69, 88. See also sorting algorithms

O(N²), 7, 10, 15, 18, 20. See also sorting algorithms

O(N³), 11, 15, 350, 483, 489

O(sqrt(N)), 14, 38, 39

Θ(g(N)), 420

Θ(N log N), 420, 421

object references, 234, 481

obscurity, 397, 398, 399, 415, 540

octtrees, 266, 482

odd-cycle problem, 432, 543

1 (constant), 11, 17, 478

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

100,000 names, 162, 512

1 million floating-point values, 162, 512

1 million integers, 162, 512

one-dimensional arrays (linear arrays)

exercises, 108, 501

finding items, 86

finding minimum, maximum, average, 86–88

graphical representation, 84

inserting items, 88–89

int[,] numbers = new int[10, 20];, 84

median of, 87–88, 108, 501–502

removing items, 89, 109, 502

sample variance, 108, 501

standard deviation, 108, 501

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

bin packing, 318, 417, 429

complexity theory, 427–429, 482, 485

decision trees, 482

knapsack problem, 433, 546

partition problem, 306–310, 317, 323

ordered hashing, 179–181, 182, 515

ordered tree, 229, 231

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

painting fences, 22, 185, 489

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

data, 436, 440

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

types, 436, 485

parent node, 228, 231

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

pattern matching, 381–387

P-boxes, 409

perfect tree, 231

permutation boxes, 409

permutations

defined, 209

with duplicates, 214–215

without duplicates, 215–216

petaflop, 439

phase king algorithm, 456–458

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

poker program, 52, 492

polynomial time. See NP; P

polynomials

functions, 18

Newton-Cotes formulas, 42–44

runtimes, 15, 20, 483

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

described, 37–39

prime numbers, 36–41

composite numbers, 36, 41, 53

defined, 36

Fermat's primality test, 6, 40, 52, 478

finding, 39–40

sieve of Eratosthenes, 39–40, 53, 422, 478, 494

testing for primality, 40–41

priority inversion problem, 444

priority queues, 127, 129, 142, 161, 479, 510, 511

PriorityQueue example program, 511

PRNGs (pseudorandom number generators)

biased, 29

CSPRNGs

described, 28–29, 31

disadvantages, 29

unbreakable encryption scheme, 418, 542

dining philosophers problem, 450

fair, 29

linear congruential generators, 26–29

nonuniform distributions, 33

seed values, 26–28, 450

TRNGs, 25–26

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

described, 3–6, 477

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

quadtrees, 260–266, 482, 523

quantum computing, 435, 446, 485

quantum-size transistors, 435, 445

qubits, 445

queens problem. See eight queens problem

QueueInsertionsort example program, 510

queues, 123–128

in arrays, 124–127

arrays compared to, 108

circular, 125–127

defined, 123, 479

deques, 127–128, 129, 479, 510

exercises, 128–129, 509–510

FIFO, 123, 128, 244, 334, 335, 479

insertionsort algorithm, 127, 129, 510

linked-list, 123–124

multiheaded, 129, 510

priority, 127, 129, 142, 161, 479, 510, 511

selectionsort algorithm, 129, 510

specialized, 127–128

summary of concepts, 479

uses, 111, 128, 479

QueueSelectionsort example program, 510

quicksort algorithm, 145–152

characteristics, 159

comparison, 159–160

countingsort compared to, 157

divide-and-conquer strategy, 153

exercises, 161, 511, 512

implementation

in place, 149–152

with stacks, 149

mergesort compared to, 153–155

parallelism, 152, 154, 159, 480

picking dividing item, 148

randomization, 31, 479

runtime analysis, 146–148

sub O(N log N) algorithms, 156

upper and lower bounds, 420–421

using, 152

when to use, 19

worst-case performance O(N²), 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

randomization, 25–33

arrays, 31–33

dining philosophers problem, 450

hash tables, 480

interview puzzles, 469

quicksort algorithm, 31, 479

summary, 478

Random.org, 26

RandomTrees program, 27–28

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

rectangular arrays, 109, 503

recursion, 185–225

backtracking algorithms, 201–203

defined, 185

drawbacks, 216, 223

eight queens problem, 203–206, 208, 223, 224, 322, 518

exercises, 223–225, 515–518

factorial algorithm

nonrecursive, 217, 225, 518

recursive, 223, 515

tail recursion, 216–217

factorial function (N!), 15, 16, 17, 18, 20, 186–188, 189, 478, 481

Fibonacci numbers, 188–189

graphical algorithms, 193–201

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 curves, 193–195

Koch snowflakes, 195, 223–224, 516

linear search, 168, 512

memory, 187

permutations

defined, 209

with duplicates, 214–215

without duplicates, 215–216

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

summary of concepts, 480–481

Tower of Hanoi puzzle, 119–121, 189–193, 223, 515–516

RecursiveBinarySearch example program, 513

RecursiveInterpolationSearch example program, 513

RecursiveLinearSearch example program, 512

reductions

described, 424–425, 485

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

linear arrays, 89, 109, 502

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

retracing, linked list, 75–76

retreat, attack. See consensus problem reversal

arrays, 117

linked list, 76–78

stacks, 128, 509

Reversi game, 304–305

right rotation, 279–281, 524–525, 526

Rivest, Ron, 412

rolls. See dice rolls

root at top, tree data structures, 228, 271

root merge, 287, 290

root split, 283, 284, 289

roots. See also nodes

of equations, 49–51, 496

root node, 228, 229, 231

rotations

left, 279–281, 524–525

right, 278–281, 524–525, 526

round manhole covers, 465, 466

route ciphers, 403–404

row/column transposition cipher, 399–401, 402, 417

RowColumnTransposition example program, 540

row-major mapping, 84–85, 91

RSA algorithm, 412–415, 416, 417, 418

RtlMoveMemory, 18

Rule 1, 7, 8

Rule 2, 7, 8–9

Rule 3, 7, 9

Rule 4, 8, 9–10

Rule 5, 8, 10

runtime functions, 11–17

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

quicksort, 146–148

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

scytale method, 397, 399

searching

abba dabba example, 389–391

brute-force, 299, 388, 389, 396, 410, 432, 448

nonindexed database, 448

random, 448

strings, 387–391

tools, 163

traversal and, 237

searching algorithms, 163–168

binary search

described, 165–166, 169, 480

exercise, 168, 513

speed, 167

exercises, 168, 512–513

interpolation search

described, 166–167, 169, 480

exercises, 168, 513

recursion, 168, 513

speed, 167, 168

linear search (exhaustive search)

described, 164–165, 480

exercises, 168, 512

linked lists, 164

recursion, 168, 512

sorted arrays, 164

speed, 167

unsorted arrays, 86, 164–165

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

seed values, 26–28, 450

selections (combinations)

defined, 209

with duplicates, 211–213

without duplicates, 213–214

with loops, 210–211

selectionsort algorithm

arrays, 134–135

characteristics, 159

comparison, 159–160

defined, 479

insertionsort compared to, 82, 500

linked lists, 69–70

program, 160

queues, 129, 510

QueueSelectionsort example program, 510

stacks, 122–123, 129, 509–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

sentinels, 58–59, 246, 478

set method, 90, 94, 97

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

siblings, 228, 231

SierpDown, 199, 516

Sierpinski, Waclaw Franciszek, 201

Sierpinski carpet, 201, 224, 517–518

Sierpinski curves, 197–200, 224, 516, 517

Sierpinski gaskets, 200–201, 224, 517

SierpLeft, 199, 516

SierpRight, 199, 516

SierpUp, 199, 516–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

singly linked lists, 56–63

six-sided dice. See dice rolls

64-bit double-precision floating-point number, 188

slice_size array, 93–94

snapshot, 459–460, 486

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 linked lists, 65–66

sorted trees. See also balanced trees

building, 245–247

defined, 12, 241, 482

nodes

adding, 245–247

deleting, 248–250

finding, 247

sentinels, 246

SortedChaining example program, 513

sorting

external, 155, 159, 480

linked lists

copying lists, 67–68

insertionsort algorithm, 68–69

selectionsort algorithm, 69–70

stable, 155

tools, 132

topological, 355–359, 375, 484

train cars

stack algorithms, 117–119

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

exercises, 160–162, 510–512

O(N log N) algorithms, 138–155

O[N²] algorithms, 132–138

reasons for using, 131

runtime performance, 131

sub O(N log N) algorithms, 156–159

summary of concepts, 479–480

types, 131

space-filling curves, 200

spaghetti. See dining philosophers problem

spanning trees

defined, 337

degree-constrained, 430

described, 337–338

maximum leaf spanning tree, 430

minimal, 329, 338–339, 350, 352, 483, 533

minimum degree spanning tree, 430

sparse arrays, 97–105

defined, 97, 479

deleting values, 104–105

find row or column, 100

getting values, 101

setting values, 101–104

sparse matrices

add, 106–107, 109, 505–508

column-ordered, 107

multiply, 107, 109, 508–509

sparse triangular array, 109, 504

special alphabets, 397

specialized queues, 127–128

specialized tree algorithms, 256–270

animal game, 256–258, 274, 482, 521–522

expression evaluation, 258–260, 274–275

octtrees, 266, 482

quadtrees, 260–266, 482, 523

tries, 266–270, 275, 512, 523–524

special-purpose arrays. See arrays

speed, algorithms, 2, 477

splits

node, 283–284, 291, 482

root, 283, 284, 289

spring-loaded stack, of plates, 111–112

sqrt N, 14, 17, 478

stable sorting, 155

stack algorithms, 117–123

StackInsertionsort example program, 509

stacks, 111–123

in arrays, 113–115

arrays compared to, 108

defined, 111, 187, 479

double, 115–117, 128, 509

exercises, 128–129, 509–510

insertionsort algorithm, 121–122, 128–129, 509

LIFO, 111, 117, 128, 333, 479

linked-list, 112–113

quicksort implementation, 149

reversal, 128, 509

selectionsort algorithm, 122–123, 129, 509–510

shortest-path algorithms, 117

summary of concepts, 479

uses, 111, 128, 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

string algorithms, 377–396

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

exercises, 394–396, 537–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

string searching, 387–391

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

subtrees, 229, 231

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

clocks, 460–461, 463–464, 486

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

target_value, 12–13

task parallelism, 440

10 floating-point values, 161, 511

teraflop, 439

termination, consensus problem, 455

terminology

cryptography, 398–399

networks, 325–328

trees, 227–231

test_node, 12–13

tetrahedral arrays, 109, 503–504

TextDisplay example program, 520

thin trees. See tall, thin trees

threaded trees, 250–256

building, 251–254

defined, 250

symmetrically, 251

traversal steps, 251, 255–256

using, 254–256

ThreadedTree example program, 521

threads

defined, 250, 482

linked lists, 70–71, 82, 500

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

systolic arrays, 437–438

zero-time sort algorithm, 438, 446, 462, 547–548

tic-tac-toe (naughts and crosses)

exercise, 322, 531

initial moves and responses, 302–303

minimax strategy, 298–302

top variable, 56, 57

top-down B-tree, 291, 482

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

trapezoid rule, 43–45, 478

TrapezoidRule sample program, 43–44, 45, 46

traveling salesman problem (TSP), 16, 200, 320–321, 417, 423, 429, 431, 432

traversals, 237–244

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

properties, 231–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

sorted, 12–13

exercises, 271–275, 519–524

family tree analogy, 228

fat, 233

full, 229, 230, 231

height, 171, 229, 231

intuitive description, 227–228

knowledge, 256–258, 274, 482, 521

level/depth, 229, 231

networks compared to, 227, 322, 325, 332

ordered, 229, 231

parse, 380, 383, 387, 395, 396, 484, 539

properties, 481–482

RandomTrees program, 27–28

recursive definition, 229

root at top, 228, 271

sorted

adding nodes, 245–247

building, 245–247

defined, 12, 241, 482

deleting nodes, 248–250

finding nodes, 247

sentinels, 246

spanning trees

defined, 337

degree-constrained, 430

described, 337–338

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

octtrees, 266, 482

quadtrees, 260–266, 482, 523

tries, 266–270, 275, 512, 523–524

summary of concepts, 481–482

tall, thin, 147, 148, 233, 246, 247, 271, 277, 283, 287, 293

terminology, 227–231

threaded, 250–256

building, 251–254

defined, 250

symmetrically, 251

traversal steps, 251, 255–256

using, 254–256

unordered, 229, 273

XML and, 236

treesort algorithm, 247

triangles. See Koch snowflakes; Sierpinski gaskets

triangular arrays, 94–97

add, 109, 504

lower, 109, 502

multiply, 109, 505

sparse, 109, 504

sparse arrays compared to, 97, 98–99

tetrahedral arrays, 109, 503–504

upper, 94, 109, 502

tries (prefix trees), 266–270, 275, 512, 523–524

triple DES, 411, 416

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-3 trees, 282–287

adding values, 283–284

defined, 282, 482

deleting values, 284–287

exercise, 294, 527

variations, 291–293

2^N, 16, 17, 478

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

nonzero local bounds, 90–91

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

1 million integers, 162, 512

unordered trees, 229, 273

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

vertices, 325, 430, 431

Via array, 346–349, 353, 534

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

WAN, 267, 269, 270

WANE, 266–267, 269

WANT, 266, 267, 269

WANTED, 267, 269, 270

Warnsdorff's heuristic, 209, 216, 225, 518

weakly connected network, 326, 328

While loop

described, 4

Euclid's algorithm, 34–35

finding cells, 57–58

general recursion removal, 220

heaps, 143

iteration over linked list, 57

ordered hash table, 181

quicksort algorithm, 151–152

sentinels, 59

tail recursion, 218

threaded trees, 255, 256

“Why Are Manhole Covers Round?” article, 466

WISP, 266, 267

witnesses, Fermat, 40–41

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

XOR operator, 408, 409, 410

Z

zeros, finding, 49–51

zero-time sort algorithm, 438, 446, 462, 547–548