- A
- A2Z Interviews: puzzles (website), 604
- accepting states, 497, 711
- acyclic networks, 439–440
- adaptive quadrature, 50–53, 711
- adaptive techniques, 599, 609
- adding
AddInterval
method, 329
AddItemToChild
method, 335–336
AddNote
method, 320
- Adelson-Velskii, G. M. (mathematician), 350
- adjacent, 405, 711
- Advanced Encryption Standard (AES), 520, 532–533, 711
- advanced linked-list operations, 609
- adversary, in cryptography, 520, 711
- AES (Advanced Encryption Standard), 520, 532–533, 711
- algorithmic goals, 607
- algorithms
- all-pairs shortest paths, 431–436, 617
- backtracking
- about, 252–253
- eight queens problem, 254–257, 718
- knight's tour problem, 257–260, 723
- basic exercises, 20–22
- basic network
- about, 403
- exercises, 447–450
- finding paths, 425–436
- network representations, 407–409
- network terminology, 403–406
- shortest path modifications, 441–446
- strongly connected components, 420–425
- transitivity, 436–441
- traversals, 409–420
- basic recursion, 228–238
- basics of, 607–608
- bees, 394, 712
- binary search, 203–204, 611
- Boyer-Moore, 493, 504–508, 618, 713
- branch-and-bound, 616
- Bron-Kerbosch, 475–480, 714
Bubblesort
, 171–174, 197, 714
Bucketsort
, 195–197
- bully, 587–588, 714
- characteristics of, 607
- community detection
- about, 483
- clique percolation method (CPM), 485
- Girvan-Newman, 483–485, 721
- maximal cliques, 473, 483, 724
ContainsDuplicates
, 10, 15
- ContainsNodes, 313–314
ContainsNodes
, 313–314
countingsort
, 192–193, 197, 716
- cryptographical, 619
- data structures and, –3
- defined, , 607, 711
- distributed
- about, 561–562, 573, 620
- byzantine generals problem (BGP), 581–584, 620, 714
- clock synchronization, 589–590, 620
- consensus problem, 584–587, 620, 716
- debugging, 573–574
- dining philosophers problem, 577–580, 620, 717
- embarassingly parallel, 574–576, 620
- embarassingly parallel algorithm, 574–576
- exercises, 591–593
- leader election, 587–588, 620
- mergesort, 576–577
mergesort
, 189–191, 197, 576–577, 620, 725
- mergesort algorithm, 576–577
- snapshot, 588–589, 620, 732
- two generals problem, 580–581, 620, 736
- types of parallelism, 562–572
- Double Metaphone, 514, 718
- edit distance, 618
- embarassingly parallel, 574–576, 620
- Euclidean, 36–37, 608, 719
- Euclid's, 36–37, 608, 719
- features of, –17
FindCellBefore
, 75
FindLargest
, –9, 14
- five-coloring, 459–462
- Fleury's, 486–487, 720
- Floyd-Warshall, 98–100, 431, 437, 735
- Ford-Fulkerson, 466, 720
- four-coloring, 459, 720
- Gaussian elimination, 61–62
- Girvan-Newman, 483–485, 721
- graphical
- about, 238
- gaskets, 246–247, 720
- Hilbert curve, 241–242, 722
- Koch curve, 239–241, 723
- Sierpiński curve, 243–246, 732
- skyline problem, 247–252, 732
Heapsort
, 175–181, 721
- Hierholzer's, 487–488, 722
InsertCell
, 88
insertionsort
- interpolation search, 611
- Kosaraju's, 421–422, 723
- Kosaraju-Sharir, 421–422, 732
- label-correcting shortest path, 617
- label-setting, 617
- LeadsToSolution, 253
- linked-list
- about, 86
- copying lists, 86–87
- sorting with
insertionsort
, 87–88
- sorting with
selectionsort
, 88–89
- list retracing, 94–95
- list reversal, 95–97
- map coloring
- about, 456, 462–463
- five-coloring, 459–462
- four-coloring, 459, 720
- three-coloring, 458–459
- two-coloring, 456–458
MergeRootsWithSameOrder
, 160–161
mergesort
, 189–191, 197, 576–577, 620, 725
- Metaphone, 513–514, 725
- network
- about, 451, 616–617, 616–618
- cliques, 473–482
- community detection, 473, 483–485, 721, 724
- cycle detection, 455, 716
- Eulerian cycles, 314–316, 485–488, 719
- Eulerian paths, 314–316, 485–488, 719
- exercises, 489–492
- map coloring, 456–463, 720
- maximal flow, 464–470, 617, 724
- minimal flow cut, 417–418, 468–470, 725
- network cloning, 470–473
- topological sorting, 451–455, 617, 734
- work assignment, 467–468
- numerical
- about, 23, 608–609
- exercises, 68–70
- finding greatest common divisor (GCD), 36–40
- finding zeros, 55–57
- Gaussian elimination, 57–62, 609, 721
- least square fits, 62–67, 723
- performing exponentiation, 40–41
- performing numerical integration, 47–55
- prime numbers, 42–47
- randomizing data, 23–36
- O(N2)
- about, 168
Bubblesort
, 171–174, 197, 714
Inserrtionsort
in arrays, 18, 87–88, 168–169, 197, 610
Selectionsort
in arrays, 88–89, 170–171, 197, 610
- parallel, debugging, 620
- phase king, 584–585, 728
- phonetic, 511–514, 618, 728
PigeonholeSort
, 193–195, 197, 728
- probabilistic, 47, 608, 729
quicksort
, 11, 19, 181–188, 197
- recursive, 612
- RSA, 534–537, 731
selectionsort
- Shor's, 572
- shortest path
- about, 441
- best-first search, 442–443
- bidirectional search, 442
- early stopping, 442
- prohibitions, 443–446
- shape points, 441–442
- turn penalties, 443–446
- Soundex, 511–513, 732
- specialized tree
- about, 322
- animal game, 322–324
- building trees, 328–329
- expression evaluation, 324–326
- intersecting with intervals, 330–332
- intersecting with points, 329–330
- interval trees, 326–328
- quadtrees, 332–337
- tries, 337–342
- stable sorting, 191
- stack
- about, 141
- reversing an array, 141
- stack insertionsort, 145–146
- stack selectionsort, 146–147
- tower of Hanoi, 143–145, 235–238, 735
- train sorting, 142–143
- stack insertionsort, 145–146
- stack selectionsort, 146–147
- string
- about, 493, 618
- calculating edit distance, 508–511
- exercises, 515–517
- matching parentheses, 494–496
- pattern matching, 497–504
- phonetic, 511–514, 618, 728
- string searching, 504–508
- swarm intelligence, 616
- three-coloring, 458–459
- tortoise-and-hare, 98–100, 431, 437, 735
- train sorting, 142–143
- two-coloring, 456–458
- alignment rule, 395
- all-pairs shortest paths algorithm, 431–436, 617
- amortized analysis, 163, 711
- amortized operations, 615
- analyzing
Quicksort
algorithm run time, 182–184
- ancestors, 286, 288, 712
- angle brackets,
- animal game, 322–324
- ant colony optimization, 393–394
- Appel, Kenneth (mathematician), 459
append
method (Python), 113, 136
- approximate optimization, 619
- approximate routing, 245–246
- arithmetic expressions, evaluating, 494–496
Array
class
- array packing, 610
- array queues, 148–151
- array stacks, 138–139
ArrayEntry
class, 121–122
ArrayRow
class, 121–122
- arrays
- about, 103, 610
- basic concepts, 103–106
- in C#, 104
- circular, 150, 715
- defined, , 712
- exercises, 132–134
Insertionsort
algorithm in, 168–169
- lower-triangular, 118, 724
- matrices, 129–131
- nonzero lower bounds, 114–118
- one-dimensional, 105, 106–113, 723
- in Python, 103
- randomizing, 29–30
Selectionsort
algorithm in, 170–171
- sparse, 121–129, 610, 732
- triangular, 118–121, 735
- two-dimensional, 105
- upper-triangular, 118, 736
Array.Sort
method, 18–19
- art gallery problem, 554
Assign
method, 421, 422, 424, 425
- associative arrays. See hash tables
- asymptotic performance, –8, 712
- attacker, in cryptography, 520, 712
- augmenting path, 712
- Augustus, 526
- average, finding, 107–108
- AVL trees
- B
- back substitution, 60–61, 712
- backtracking, 35, 613, 712
- backtracking algorithms
- about, 252–253
- eight queens problem, 254–257, 718
- knight's tour problem, 257–260, 723
- balanced trees
- about, 349, 615
- AVL trees, 350–353, 615, 712
- B-trees, 359–362, 615, 712
- B+trees, 363–364, 712
- defined, 609, 712
- exercises, 365–366
- top-down B-trees, 363, 615, 734
- 2-3 trees, 354–358, 615, 711
- variations of, 362–364
- base case, 228, 291, 712
- basic array operation, 610
- basic linked-list operations, 609
- basic network algorithms
- about, 403
- exercises, 447–450
- finding paths, 425–436
- network representations, 407–409
- network terminology, 403–406
- shortest path modifications, 441–446
- strongly connected components, 420–425
- transitivity, 436–441
- traversals, 409–420
- bees algorithm, 394, 712
- Beginning XML, 5th Edition (Fawcett), 295
- behavior, of algorithms, 607
- Bellaso, Giovan Battista (cryptologist), 527
- Berkeley Open Infrastructure for Network Computing (BOINC), 566
- best-first search, 442–443
- Bézout, Étienne (mathematician), 38
- Bézout's identity, 38–40, 712
- BGP (byzantine generals problem), 581–584, 620, 714
- biased, 712
- biased PRNG, 26–29, 608
- bidirectional search, 442
- Big O notation, –11, 544, 607, 713
- Big Omega notation, 544, 713
- Big Theta notation, 544, 713
BigInteger
data type, 41, 276
- bin packing problem, 554
- binary search, 203–204, 713
- binary search algorithm, 203–204, 611
- binary tree
BinaryNode
class, 299, 300, 304
Binary-Search
method, 201
- binomial coefficient, 474, 713
- binomial heaps
- binomial theorem, 713
- binomial trees
- bin-packing problem, 388
- bipartite detection, 713
- bipartite graph, 550
- bipartite matching, 713
- bipartite matching problem, 550
- bipartite network, 467, 713
- block ciphers
- about, 531
- defined, 619, 713
- Feistel cipher, 533–534, 719
- substitution-permutation network cipher, 531–533
- Blowfish, 520
- Boids, 395–397
- BOINC (Berkeley Open Infrastructure for Network Computing), 566
- bottleneck traveling salesman problem, 554
- bottom-up B-tree, 363, 713
- bottom-up programming, 277, 613
- Boyer-Moore algorithm, 493, 504–508, 618, 713
- branch and bound technique, 379–381, 714
- branch-and-bound algorithm, 616
- branches, 285, 288, 403, 406, 481–482, 614, 714, 724
- breadth-first search, 714
- breadth-first traversals
- about, 301–302
- defined, 714
- for networks, 412–413
- bridge link, 486, 714
- Bron, Coenraad (computer scientist), 475
- Bron-Kerbosch algorithm, 475–480, 714
- brute-force approach, 474–475, 481, 486, 714., See also exhaustive search
- brute-force searches, 575
- B-trees
- about, 359–360
- adding values, 360–361
- defined, 615, 712
- deleting values, 361–362
- B+trees, 363–364, 712
Bubblesort
algorithm, 171–174, 197, 714
- buckets, 211–213, 359, 714
Bucketsort
algorithm, 195–197
- building
- complete self-avoiding walks, 34–36
- complete trees, 295–296
- DFAs for regular expressions, 500–502
- mazes, 419–420
- parse trees, 496
- random walks, 31–36
- self-avoiding walks, 33–34
- specialized trees, 328–329
- threaded trees, 318–320
- trees in general, 292––295
- “Building a 270* Teraflops Deep Learning Box for Under $10,000,” 566
- bully algorithm, 587–588, 714
- bye, 267–273
- byzantine generals problem (BGP), 581–584, 620, 714
- C
- C#
- about, 41
Array
class, 114
- arrays in, 104
- automatic memory management and, 79
Dictionary
class, 209–210
- dictionary in, 111
- generating selections in, 474
HashTable
class, 209–210
IndexOf
method, 493
IntegerCell
class, 71–72
- sorting tools in, 168
Stack
class, 136
string
class, 493
- C programming language, 79
- C++ programming language, 79, 129
- Caesar, Julius, 526
- Caesar substitution cipher, 526–527, 714
- calculating
- edit distance, 508–511
- greatest common divisor (GCD), 36–38
- call stack, 714
- call tree, 190
- capacitated network, 464, 714
- capacity, 404, 714
- CareerCup (website), 604
- Carmichael numbers, 630–631
Case
statement,
- cells
- adding at the beginning of linked lists, 75–76
- adding at the end of linked lists, 76–77
- defined, 71, 609, 715
- deleting from linked lists, 78–79
- finding in linked lists, 73–74
- inserting after other cells in linked lists, 77–78
- marking, 92–93
- systolic arrays and, 562
- chaining, 211–213, 612
- Chandy/Misra, 579–580
- checking local links, 481–482
- child lists, 614
- child node, 286, 288, 715
- Chinese postman problem (CPP), 554, 715
- chromatic number, 715
- chromatic number problem, 555
- cipher, 715., See also specific ciphers
- ciphertext, 520, 715
- circular array, 150, 715
- circular linked lists
- about, 91–92
- defined, 715
- hash tables, 93–94
- list retracing algorithm, 94–95
- list reversal algorithm, 95–97
- marking cells, 92–93
- tortoise-and-hare algorithm, 98–100
- classes
ArrayEntry
, 121–122
ArrayRow
, 121–122
BinaryNode
, 299, 300, 304
- complexity, 545–547, 619
Dictionary
(C#), 209–210
ExpressionNode
, 325–326
HashTable
(C#), 209–210
IntegerCell
(C#), 71–72
Interval
, 328–329
IntervalNode
, 329
Link
, 407, 616
MatchUp
, 272
Node
, 407, 426, 430
Stack
(C#), 136
string
(C#), 493
TreeNode
, 293–294, 310, 311, 312
- clique cover problem, 555
- clique percolation method (CPM), 485
- clique problem, 555
- cliques
- about, 473–474
- Bron-Kerbosch algorithm, 475–480, 714
- brute-force approach, 474–475
- defined, 715
- finding triangles, 480–482
- clock synchronization, 589–590, 620
- clone references, 472–473
- closed tour, 723
- cluster, 565
- cluster computing, 715
- clustering, 612
- cocktail shaker sort, 173, 197, 715
- cohesion rule, 395
- collision, 211, 715
- collision-resolution policy, 211, 715
- colorability, 617
- column transposition cipher, 523–525
- column-major order, 105
- column-ordered sparse matrices, 131
- columns, finding, 122–123
- combinations. See selections
- common run time functions, 11–16
- community, 483–485
- community detection, 715
- community detection algorithms
- about, 483
- clique percolation method (CPM), 485
- Girvan-Newman, 483–485, 721
- maximal cliques, 473, 483, 724
- complete self-avoiding walks, 34–36
- complete trees
CompleteSelfAvoidingWalk
method, 35–36
- complexity classes, 545–547, 619
- complexity theory. See computational complexity theory
- composite number, 42, 715
- computational complexity theory
- about, 543–544, 619
- complexity classes, 545–547, 619
- defined, 715
- detection problem, 551–554, 619, 717
- exercises, 558–559
- notation, 544–545
- NP-complete problems, 554–556
- NP-hard, 550–551, 726
- optimization problem, 376–377, 551–554, 619, 727
- reductions, 548–550, 619
- reporting problem, 551–554, 619, 730
- condensation, 440, 715
- connected, 405, 716
- connected component, 404, 405, 716
- connectivity, 616
- connectivity matrix, 119, 716
- connectivity testing, 413–415
- consensus problem, 584–587, 620, 716
ContainsDuplicates
algorithm, 10, 15
ContainsNodes
algorithm, 313–314
- contention, 575–576, 620
- Cook-Levin theorem, 548
- Cook's theorem, 548
- CoolInterview puzzles (website), 604
- coprime, 730
- copying lists, 86–87
- costs, 404, 405, 716
- count method, 84
- counting
- combinations, 254–255
- defined, 611
- permutations with duplicates, 265
- permutations without duplicates, 266–267
countingsort
algorithm, 192–193, 197, 716
- covering network, 445–446, 716
- CPM (clique percolation method), 485
- cryptanalysis, 520, 716
- cryptographic hash function, 538, 716
- cryptographical algorithms, 619
- cryptographically secure pseudorandom number generator (CSPRNG), 26, 716
- cryptography
- about, 519–520, 618–619
- block ciphers, 531–534, 619, 713, 719
- defined, 716
- exercises, 540–541
- public-key encryption, 534–537, 619, 729
- RSA algorithm, 534–537, 731
- substitution ciphers, 526–531, 733
- terminology for, 520–521
- transposition ciphers, 521–526, 618, 735
- uses for, 538–539
- CSPRNG (cryptographically secure pseudorandom number generator), 26, 716
- cutting stock problem, 389–390, 716
- cycle, 404, 406, 716
- cycle detection, 455, 716
- D
- dance floor, 394
- data, randomizing, 23–36
- Data Encryption Standard (DES), 534, 716
- data parallelism, 562, 716
- data processing units (DPUs), 562, 717
- data structures
- algorithms and, –3
- defined, 607, 717
- data structures technique, 599
- deadlock, 571–572, 717
- debugging
- distributed algorithms, 573–574
- parallel algorithms, 620
- decipher, 520, 717
- decision trees
- about, 367–368, 615–616
- defined, 717
- exercises, 398–401
- searching game trees, 368–375
- searching general, 375–392
- swarm intelligence (SI), 392–397
- decision trees technique, 599
- decrypt, 520, 717
- defining heaps, 176–180
- degree
- degree-constrained spanning tree problem, 555
DeleteEntry
method, 126, 129
- deleting
- dendogram, 717
- depth, of nodes, 287, 288, 311–312, 717
- depth-first traversals
- defined, 717
- for networks, 410–412
- for trees, 297
- deque, 152, 162–163, 610, 717
Dequeue
method, 147–148
- DES (Data Encryption Standard), 534, 716
- descendants, 286, 289, 717
- detection problem, 551–554, 619, 717
- deterministic computer, 545
- deterministic finite automaton (DFA), 497–499, 500–502, 717
- deterministic finite state machine. See deterministic finite automaton (DFA)
- dictionary. See hash tables
Dictionary
class (C#), 209–210
- difficulty, 621
- digital signature, 538, 717
- dining philosophers problem, 577–580, 620, 717
- direct recursion, 718
- directed, 718
- directed branches, 286
- directed link, 404, 406
- disk bound, 576, 718
- distributed algorithms
- about, 561–562, 573, 620
- byzantine generals problem (BGP), 581–584, 620, 714
- clock synchronization, 589–590, 620
- consensus problem, 584–587, 620, 716
- debugging, 573–574
- dining philosophers problem, 577–580, 620, 717
- embarassingly parallel algorithm, 574–576, 620
- exercises, 591–593
- leader election, 587–588, 620
mergesort
algorithm, 189–191, 197, 576–577, 620, 725
- snapshot, 588–589, 620, 732
- two generals problem, 580–581, 620, 736
- types of parallelism, 562–572
- distributed computing, 565–567, 718
- divide-and-conquer approach, 249–252, 599, 611, 613
- dominating set, 718
- dominating set problem, 555
DoSomething
method,
- double hashing, 219
- double linked lists, 79–81
- Double Metaphone algorithm, 514, 718
- double stacks, 139–141, 610
DoubleIt
method,
- doubly linked lists
- DPUs (data processing units), 562, 717
DrawRelative
method, 242, 244–245
- DSPACE(f(n)), 718
- DTIME(f(n)), 619, 718
- duplicates
- permutations with, 265
- permutations without, 266–267
- selections with, 262–263
- selections without, 264
- E
- early stopping, 442
- edge betweenness, 483, 718
- edge graph, 445–446, 716
- edge network, 445–446, 716
- edges, 285, 288, 403, 406, 481–482, 614, 714, 724
- edge/vertex dual, 445–446, 716
- edit distance
- calculating, 508–511
- defined, 718
- edit distance algorithm, 618
- edit graph, 509–511
- eight queens problem, 254–257, 718
- Einstein@Home, 566
- Elements (Euclid), 36
- embarassingly parallel, 718
- embarassingly parallel algorithms, 574–576, 620
- EMST (Euclidean minimum spanning tree), 418–419
- encipher, 520, 719
- encrypt, 520, 719
End While
statement,
- enqueue, 161–162
Enqueue
method, 147–148
- entanglement, 719
- Euclid
- Euclidean algorithm, 36–37, 608, 719
- Euclidean minimum spanning tree (EMST), 418–419
- Euclidean spanning tree, 617
- Euclid's algorithm, 36–37, 608, 719
- Euler, Leonhard (mathematician), 485
- Euler tours, 314–316, 485–488, 719
- Eulerian cycles, 314–316, 485–488, 719
- Eulerian network, 485, 719
- Eulerian paths, 314–316, 485–488, 719
- Euler's totient function, 535–536, 719
Evaluate
method, 496
- evaluating arithmetic expressions, 494–496
- exact cover, 719
- exact cover problem, 555
- exercises
- algorithm basics, 20–22
- arrays, 132–134
- balanced trees, 365–366
- basic network algorithms, 447–450
- complexity theory, 558–559
- cryptography, 540–541
- decision trees, 398–401
- distributed algorithms, 591–593
- hash tables, 222–225
- interview puzzles, 604–605
- linked lists, 101–102
- network algorithms, 489–492
- numerical algorithms, 68–70
- recursion, 281–284
- searching, 208
- sorting, 198–200
- string algorithms, 515–517
- trees, 342–348
- exhaustive search, 106–107, 202–203, 377–379, 611, 719
ExhaustiveSearch
method, 378
- expanded node networks, 444–445
- exponential functions, 15–16
- exponentiation, performing, 40–41
- expression evaluation, 324–326
ExpressionNode
class, 325–326
- expressions, 614
- EXPTIME, 619, 719
- EXPSPACE, 719
- extending greatest common divisor (GCD), 38–40
ExtendWalk
method, 35–36
- Extensible Markup Language (XML), 295
- external node, 286, 289, 719
- external sorting, 191, 611, 719
- F
- Facebook interview puzzles group (website), 603
factorial
function, 16, 228–230, 232, 719
- fair, 719
- fair PRNG, 26–29, 608
- fairness, ensuring, 26–28
- Fawcett, Joe (author)
- Beginning XML, 5th Edition, 295
- feedback vertex set problem, 555
- Feistel, Horst (cryptographer), 533
- Feistel cipher, 533–534, 719
- Fermat liar, 46, 720
- Fermat primality test, 46
- Fermat witness, 46, 609, 720
- Fermat's little theorem, 608–609
Fibonacci
function, 231–232, 276
- Fibonacci numbers, 230–232, 720
- FIFO (first-in-first-out). See queues
- FIFO list, 720
- file processing, 575
- fill percentage, 211, 720
find
method (Python), 493
FindCellBefore
algorithm, 75
FindColumnBefore
method, 123–125, 127, 128
- finding
- average, 107–108
- cells in linked lists, 73–74
- columns, 122–123
- greatest common divisor (GCD), 36–40
- items, 106–107, 336–337, 341–342
- maximum, 107–108
- median, 108–109
- minimum, 107–108
- mode, 109–112
- nodes, 306
- paths, 425–436
- prime factors, 42–44
- prime numbers, 44–45
- rows, 122–123
- triangles, 480–482
- zeros, 55–57
FindLargest
algorithm, –9, 14
FindNode
method, 306
FindRowBefore
method, 124–125, 126–127, 128
- first common ancestor. See lowest common ancestor (LCA)
- first-in-first-out (FIFO). See queues
- five-coloring algorithm, 459–462
- Fleury's algorithm, 486–487, 720
- flops, 566, 720
- Floyd, Robert (mathematician), 98
- Floyd-Warshall algorithm, 98–100, 431, 437, 735
For
loop, , 56–57, 113, 261
- Ford-Fulkerson algorithm, 466, 720
- forest, 152, 720
- forward elimination, 58–60, 720
- four-coloring algorithm, 459, 720
- fractals, 575
free
function (C++), 129
- full node, 290
- full tree, 287, 289, 720
- functions
- cryptographic hash, 538, 716
- defined,
- Euler's totient, 535–536, 719
- exponential, 15–16
factorial
, 16, 228–230, 232, 719
Fibonacci
, 231–232, 276
free
(C++), 129
MoveMemory
, 18
N
, 14
N!
, 16
N log N
, 15, 543–544
N
2
, 15
- phi, 535–536, 719
pow
(Python), 41
RtlMoveMemory
, 18
- runtime, 11–16, 608
Sqrt N
, 14
- totient, 535–536, 719
2
N
, 15–16
- visualizing, 16–17
- G
- game trees, 615–616
- gaskets, 246–247, 720
- Gauss, Johann Carl Friedrich (mathematician and physicist), 58
- Gaussian elimination, 57–62, 609, 721
- Gaussian elimination algorithm, 61–62
- GCD. See greatest common divisor (GCD)
- general and lieutenants problem, 582, 721
- general networks, 440–441
- general recursion removal, 277–280, 613
- general trees, 312–314
- generalized partition problem, 387–388, 721
- generating
- nonuniform distributions, 30–31
- random values, 23–29
- values, 24–26
- generator, 239, 721
- geometric calculations, 443–444
get
method, 115
- GIMPS (Great Internet Mersenne Prime Search), 566
- Girvan, Michelle (physicist), 483
- Girvan-Newman algorithm, 483–485, 721
- GPUs (graphics processing units), 562
- graph, 406, 721
- graph isomorphism problem, 555, 721
- graphical algorithms
- about, 238
- gaskets, 246–247, 720
- Hilbert curve, 241–242, 722
- Koch curve, 239–241, 723
- Sierpiński curve, 243–246, 732
- skyline problem, 247–252, 732
- graphics processing units (GPUs), 562
- Great Internet Mersenne Prime Search (GIMPS), 566
- greatest common divisor (GCD)
- calculating, 36–38
- defined, 721
- extending, 38–40
- finding, 36–40
- grid computing, 565, 721
- grids, joining, 566
- Guthrie, Francis (mathematician), 459
- H
- Haidong Wang's interview puzzles (website), 603
- Haken, Wolfgang (mathematician), 459
- HAM (Hamiltonian path) problem, 440, 555, 721
- HAMC (Hamiltonian circuit) problem, 555, 721
- Hamiltonian, 721
- Hamiltonian circuit (HAMC) problem, 555, 721
- Hamiltonian completion problem, 555, 721
- Hamiltonian cycle problem, 440, 555
- Hamiltonian path (HAM) problem, 440, 555, 721
- hardware random number generator (HRNG), 24
- hash tables
- about, 93–94, 111, 209–210, 471–472, 612
- chaining, 211–213
- defined, 612, 717, 721
- exercises, 222–225
- fundamentals of, 210–211
- open addressing, 213–222
- resizing, 211
HashTable
class (C#), 209–210
- heaps
Heapsort
algorithm, 175–181, 721
- height
- Hierholzer's algorithm, 487–488, 722
- higher dimensions, 115–118
- Hilbert, David (mathematician), 241
- Hilbert curve, 241–242, 722
- hill climbing, 616, 722
- hill-climbing heuristic, 385–386
- How to Ace a Google Interview (website), 603
- HRNG (hardware random number generator), 24
- hybrid methods, 84–85
- I
- IBM Q System One, 572
If-Then-Else
statement,
- implementing
Heapsort
algorithm, 180–181
Quicksort
algorithm in place, 185–188
Quicksort
algorithm with stacks, 185
- round-robin scheduling, 271–273
- improving paths, 382–384
- in-degree, 404, 406, 722
- independent set, 722
IndexOf
method (C#), 493
- indirect recursion, 722
- inductive reasoning, 291, 614
- initial state, 497, 722
- initiator, 239, 722
- inorder traversal, 299–300, 722
insert
method (Python), 113
InsertCell
algorithm, 88
- inserting items, 112–113
insertionsort
algorithm
IntegerCell
class (C#), 71–72
- interchange networks, 445445–, 716
- internal node, 286, 289, 722
- interpolation search, 204–205, 722
- interpolation search algorithm, 611
- intersecting
- with intervals, 330–332
- with points, 329–330
Interval
class, 328–329
- interval trees, 326–328, 722
IntervalNode
class, 329
- intervals, intersecting with, 330–332
- interview puzzles
- about, 595–596, 621
- answering questions, 598–602
- asking questions, 597–598
- exercises, 604–605
- websites, 603–604
- Interview Puzzles Dissected: Solving and Understanding Interview Puzzles (Stephens), 604
- interview websites, 603–604
- isomorphic, 722
- iterating, over singly linked lists, 73
itertools.combinations
method (Python), 474
- J
- job shop scheduling, 723
- job shop scheduling problem, 555
- joining grids, 566
- K
- k-clique, 473, 723
- Kerbosch, Joep (computer scientist), 475
- key, 723
- knapsack problem, 16, 390, 555, 723
- knight's tour problem, 257–260, 723
- knowledge trees, 614
- Koch, Helge von (mathematician), 239
- Koch curve, 239–241, 723
- Koch snowflake, 241
- Kosaraju, Sambasiva Rao (professor), 421
- Kosaraju's algorithm, 421–422, 723
- Kosaraju-Sharir algorithm, 421–422, 732
- L
- label-correcting shortest path algorithm, 617
- label-correcting shortest paths, 430–431
- label-setting algorithm, 617
- label-setting shortest paths, 426–429
- Landis, E. M. (researcher), 350
- last-in-first-out (LIFO). See stack
- LCM (least common multiple), 69
- leader election, 587–588, 620
- LeadsToSolution algorithm, 253
- leaf node, 286, 289, 290, 723
- least common ancestor. See lowest common ancestor (LCA)
- least common multiple (LCM), 69
- least squares fit, 62–67, 723
- leaves, 614
- left-left case, 350–351
- level, of nodes, 287, 289, 723
- level-order traversal. See breadth-first traversal
- LIFO (last-in-first-out). See stacks
- LIFO lists. See stacks
- line network, 445–446, 716
- linear arrays. See one-dimensional arrays
- linear congruential generator, 24, 723
- linear least squares fit, 62–64
- linear probing, 215–217, 724
- linear search, 106–107, 202–203, 611, 724
Link
class, 407, 616
- linked lists
- about, 71, 609
- basic concepts, 71–72
- defined, 724
- doubly linked list, 79–81
- exercises, 101–102
- linked lists with loops, 91–100
- linked-list algorithms, 86–89
- multithreaded linked list, 90
- self-organizing linked list, 82–86
- singly linked list, 72–79
- sorted linked list, 81–82
- linked-list algorithms
- about, 86
- copying lists, 86–87
- sorting with
insertionsort
algorithm, 87–88
- sorting with
selectionsort
algorithm, 88–89
- linked-list queues, 148
- linked-list stacks, 136–138
- links. See branches
- list retracing, 724
- list retracing algorithm, 94–95
- list reversal, 724
- list reversal algorithm, 95–97
- lists, 86–87, 248–249
- livelock, 724
- logarithmic growth, 614
- logarithms, 12
- longest path problem, 556, 724
- loops
- lower-triangular array, 118, 724
- lowest common ancestor (LCA). See first common ancestor
- about, 289, 309
- defined, 287, 720
- Euler tours, 314–316
- general trees, 312–314
- pairs, 316
- parent pointers, 310–311
- parents and depths, 311–312
- sorted trees, 309–310
- Lucas, Edouard (Mathematician), 144
- M
- majority voting problem, 205–207, 724
MakeSkyline
method, 250–251
- map coloring, 724
- map coloring algorithms
- about, 456, 462–463
- five-coloring, 459–462
- four-coloring, 459, 720
- three-coloring, 458–459
- two-coloring, 456–458
Map2DArray
method, 106
- mapping, 612
- marking cells, 92–93
- matching, 724
- matching parentheses, 494–496
MatchUp
class, 272
- Math Is Fun (website), 129
- Math Olympiads (website), 604
- matrices, 129–131
- "Matrix" (website), 129
- maximal cliques, 473, 483, 724
- maximal flow, 617
- maximal flow problem, 464–466, 724
- maximum, finding, 107–108
- maximum independent set, 724., See also independent set
- maximum independent set problem, 556
- maximum leaf spanning tree, 724
- maximum leaf spanning tree problem, 556
- mazes, building, 419–420
- median, finding, 108–109
- memory requirements, for algorithms, 607
MergeRootsWithSameOrder
algorithm, 160–161
MergeSkylines
method, 251
mergesort
algorithm, 189–191, 197, 576–577, 620, 725
mergesort
method, 19
MergeTrees
method, 159–160
- merging
- binomial heaps, 156–161
- binomial trees, 155–156
- Metaphone algorithm, 513–514, 725
- method of gradient ascent, 385–386
- method of gradient descent, 385–386
- methods
AddInterval
, 329
AddItemToChild
, 335–336
AddNote
, 320
append
(Python), 113, 136
Array.Sort
, 18–19
Assign
, 421, 422, 424, 425
Binary-Search
, 201
CompleteSelfAvoidingWalk
, 35–36
- count, 84
- defined,
DeleteEntry
, 126, 129
Dequeue
, 147–148
DoSomething
,
DoubleIt
,
DrawRelative
, 242, 244–245
Enqueue
, 147–148
Evaluate
, 496
ExhaustiveSearch
, 378
ExtendWalk
, 35–36
find
(Python), 493
FindColumnBefore
, 123–125, 127, 128
FindNode
, 306
FindRowBefore
, 124–125, 126–127, 128
get
, 115
- hybrid, 84–85
IndexOf
(C#), 493
insert
(Python), 113
itertools.combinations
(Python), 474
MakeSkyline
, 250–251
Map2DArray
, 106
MergeSkylines
, 251
mergesort
, 19
MergeTrees
, 159–160
ModPow
(C#), 41
- Newton-Raphson, 55, 609, 726
- Newton's, 55, 609, 726
- passing, 299
- polygon, 728
pop
, 136–137, 728
push
, 136–137, 729
Rearrange
, 85–86
ReverseList
, 97
ScheduleRoundRobinOdd
, 273
set
, 115
shuffle
, 29
SierpDown
, 244–245
SierpLeft
, 244–245
SierpRight
, 244–245
SierpUp
, 244–245
StartExhaustiveSearch
, 378
- swap, 83–84, 733, 735
- transpose, 83–84, 733, 735
TraverseInorder
, 300
TraversePostorder
, 301
TraversePreorder
, 299
Visit
, 422
- mi flow cut, 468–470
- Microsoft's .NET Framework, 18–19
- min flow cut, 725
- min-cut, 468–470
- minimal flow cut problem, 468–470
- minimal spanning trees, 417–418, 725
- minimax, 369–372, 725
- minimum, finding, 107–108
- minimum cut, 468–470
- minimum degree spanning tree, 725
- minimum degree spanning tree problem, 556
- minimum equivalent digraph, 438
- minimum heap property, 154, 725
- minimum k-cut, 725
- minimum k-cut problem, 556
- minimum reductions, 438, 725
Mod
operator,
- mode, finding, 109–112
- modeling accuracy, 609
ModPow
method (C#), 41
- Monte Carlo integration, 54–55, 725
- Monte Carlo simulation, 609, 725
- Moore, Gordon E. (founder of Intel Corporation), 561, 721
- Moore's law, 561, 725
- move to front method (MTF), 83, 725
MoveMemory
function, 18
- multi-CPU processing, 567
- multiple recursion, 725
- multiplicative inverses, 536, 725
- multithreaded linked lists, 90
- mutex, 569, 620, 725
- N
N
function, 14
N!
function, 16
N log N
function, 15, 543–544
N
2
function, 15
- natural number, 725
- neighbors, 403, 406, 725
- .NET Framework (Microsoft), 18–19, 201
- network algorithms
- about, 451, 616–617, 616–618
- cliques, 473–482
- community detection, 473, 483–485, 721, 724
- cycle detection, 455, 716
- Eulerian cycles, 314–316, 485–488, 719
- Eulerian paths, 314–316, 485–488, 719
- exercises, 489–492
- map coloring, 456–463, 720
- maximal flow, 464–470, 617, 724
- minimal flow cut, 417–418, 468–470, 725
- network cloning, 470–473
- topological sorting, 451–455, 617, 734
- work assignment, 467–468
- network cloning, 470–473
- network coloring, 556, 726
- network coloring problem, 555
- network representations, 407–409
- networks
- acyclic, 439–440
- bipartite, 467
- capacitated, 464, 714
- covering, 445–446, 716
- Eulerian, 485, 719
- expanded node, 444–445
- general, 440–441
- interchange, 445–446, 716
- line, 445–446, 716
- residual capacity, 730
- transpose, 421, 735
- Newman, Mark (physicist), 483
- Newton-Cotes formula, 47, 726
- Newton-Raphson method, 55, 609, 726
- Newton's method, 55, 609, 726
- NEXPSPACE, 726
- NEXPTIME, 619, 726
Next i
statement,
- NFA (nondeterministic finite automaton), 502–504
Node
class, 407, 426, 430
- node merge, 357, 726
- node split, 355, 726
- nodes
- about, 406
- adding, 303–305
- child, 286, 288, 715
- defined, 285, 289, 403, 406, 726
- deleting, 306–309, 614
- external, 286, 289, 719
- finding, 306
- full, 290
- level of, 287, 289, 723
- parent, 286, 289, 311–312, 727
- reachable, 404, 406
- root, 286, 289, 731
- sibling, 732
- nondeterministic computer, 546
- nondeterministic finite automaton (NFA), 502–504
- nonindexed database searches, 575
- non-self-intersecting walk, 33–34, 608
- nonuniform distributions, 30–31
- nonzero lower bounds
- about, 114
- higher dimensions, 115–118
- two dimensions, 114–115
- Norishige Chiba (computer scientist), 481
- notation, complexity theory, 544–545
- NP, 619, 726
- NP-complete, 548, 619, 726
- NP-complete problems, 554–556
- NP-hard, 550–551, 726
- NPSPACE, 726
- NTIME(f(n)), 619, 726
- null transition, 503, 726
- numeric integration, 47–55, 726
- numeric quadrature, 47–55, 726
- numerical algorithms
- about, 23, 608–609
- exercises, 68–70
- finding greatest common divisor (GCD), 36–40
- finding zeros, 55–57
- Gaussian elimination, 57–62, 609, 721
- least square fits, 62–67, 723
- performing exponentiation, 40–41
- performing numerical integration, 47–55
- prime numbers, 42–47
- randomizing data, 23–36
- NumPy library (Python), 114
- O
- object references, 614
- observer, 589, 727
- occtrees, 337, 727
- odd-cycle problem, 558, 727
- Odell, Margaret King (developer of Soundex), 511
- O(N log N) algorithms
- O(N2) algorithms
- about, 168
Bubblesort
, 171–174, 197, 714
Inserrtionsort
in arrays, 18, 87–88, 168–169, 197, 610
Selectionsort
in arrays, 88–89, 170–171, 197, 610
- one-dimensional arrays
- about, 105, 106
- defined, 723
- finding items, 106–107
- finding median, 108–109
- finding minimum, maximum, and average, 107–108
- finding mode, 109–112
- inserting items, 112–113
- removing items, 113
- one-time pad cipher, 530–531, 619, 727
- open addressing
- about, 213–214
- defined, 612, 727
- double hashing, 219
- linear probing, 215–217, 724
- ordered hashing, 219–222, 612
- pseudorandom probing, 219, 729
- quadratic probing, 217–218, 729
- removing items, 214–215
- optimization problem, 376–377, 551–554, 619, 727
- order, 727
- ordered hashing, 219–222, 612
- ordered tree, 287, 289, 727
- out-degree, 404, 406, 727
- P
- P, 619, 727
- pairs, 316
- parallel algorithms, debugging, 620
- parallelism
- about, 562
- deadlock, 571–572, 717
- distributed computing, 565–567, 718
- multi-CPU processing, 567
- quantum computing, 572, 730
- race conditions, 567–571, 730
- systolic arrays, 562–565, 734
- types of, 620
- parent pointers, 310–311
- parenthesis matching, 618
- parse trees, building, 496
- partial ordering, 453, 727
- partition problem, 367, 556, 727
- partitioning, 611
- passing methods, 299
- paths
- about, 404
- all-pairs shortest, 431–436
- augmenting, 712
- defined, 406, 727
- Eulerian, 314–316, 485–488, 719
- finding, 425–436
- improving, 382–384
- label-correcting shortest, 430–431
- label-setting shortest, 426–429
- pattern matching
- about, 497
- building DFAs for regular expressions, 500–502
- deterministic finite automaton (DFA), 497–499
- nondeterministic finite automaton (NFA), 502–504
- P-boxes (permutation boxes), 531, 727
- perfect tree, 287, 289, 727
- performing
- exponentiation, 40–41
- numerical integration, 47–55
- permutation boxes (P-boxes), 531, 727
- permutations
- petaflop (pflop), 566, 728
- PGP (Pretty Good Privacy), 537
- phase king algorithm, 584–585, 728
- phi function, 535–536, 719
- Philips, Lawrence, 513
- phonetic algorithms, 511–514, 618, 728
PigeonholeSort
algorithm, 193–195, 197, 728
- plaintext, 520, 728
- planar, 728
- points, intersecting with, 329–330
- Polish notation, 302, 728
- polygon method, 268, 728
- polynomial least squares, 728
- polynomial least squares fit, 64–67
- polynomial run time, 15, 728
- polynomials, degree of, 65
pop
method, 136–137, 728
- popping objects, 136
- postorder traversal, 300–301, 728
pow
function (Python), 41
- practical considerations, 18–19
- precalculated values, 608
- prefix trees, 337–342, 614, 735
- preorder traversal, 297–299, 728
- Pretty Good Privacy (PGP), 537
- primality, testing for, 45–47
- primary clustering, 216, 728
- prime factors, finding, 42–44
- prime numbers
- defined, 728
- finding, 44–45
- working with, 42–47
- priority inversion, 571, 728
- priority queues, 151–152, 178, 610, 728
- private key, 534, 729
- PRNG (pseudorandom number generator), 24, 25, 26–29, 608, 729
- probabilistic algorithm, 47, 608, 729
- probability technique, 599
- probe sequence, 213, 729
- problem structure technique, 599
- procedures,
- programming puzzles, 621
- prohibitions, 443–446
- pseudoclassical mechanics, 396–397
- pseudocode
- about, –6
- Bron-Kerbosch algorithm, 476–477
- defined, 607, 729
- for self-organizing linked lists, 85–86
- pseudorandom number generator (PRNG), 24, 25, 26–29, 608, 729
- pseudorandom probing, 219, 729
- PSPACE, 729
- public key, 534, 729
- public key exponent, 535, 729
- public key modulus, 535, 729
- public-key encryption, 534–537, 619, 729
push
method, 136–137, 729
- pushdown stack. See stack
- pushing objects, 136
- puzzle problems, 621
- Python
append
method, 113, 136
- arrays in, 103
- automatic memory management and, 79
- dictionary in, 111
find
method, 493
insert
method, 113
- integers on, 82
itertools.combinations
method, 474
- NumPy library, 114
pop
method, 136, 728
pow
function, 41
- sorting tools in, 168
- Q
- quadratic probing, 217–218, 729
- quadrature, 47–55, 726
- quadtrees, 332–337, 730
- quantum bit, 572
- quantum computing, 572, 730
- qubit, 572
- queues
- R
- race conditions, 567–571, 730
- random searches, 381–382, 575
- random self-avoiding walk, 33–34, 608, 730
- random solution search, 730
- random values, generating, 23–29
- random walks
- randomization technique, 599
- randomizing
- Random.org (website), 24
random_trees
program, 25
RandomTrees
program, 25
- range minimum query (RMQ), 730
- range minimum query problem, 316
- ray tracing, 574
- reachable, 730
- reachable node, 404, 406
Rearrange
method, 85–86
- receiver, 730
- rectangle rule, 48–49, 730
- recursion
- about, 227–228, 612–613
- backtracking algorithms, 252–260
- basic algorithms, 228–238
- defined, 730
- exercises, 281–284
factorial
function, 228–230
- Fibonacci numbers, 230–232
- graphical algorithms, 238–252
- removal, 273–280
- rod-cutting problem, 232–235
- selections and permutations, 260–273
- Tower of Hanoi, 235–238
- recursive algorithm, 612
- recursive calls, 476
- recursive metrics, 612
- reduce, 730
- reductions, 548–550, 619
- regular expressions
- relatively prime, 730
- remaining node key, 339–340
- removing items, 113, 214–215
- reporting problem, 551–554, 619, 730
- residual capacity, 465, 730
- residual capacity network, 730
- resizing hash tables, 211
- resource hierarchy, 578–579, 731
Return
statement, , 10
- reverse Polish notation, 302, 731
ReverseList
method, 97
- Reversi game, 375
- reversing an array algorithm, 141
- Reynolds, Craig, 395
- right rotation, 351
- right-right case, 351
- rod-cutting problem, 232–235, 731
- root node, 286, 289, 731
- root split, 355, 731
- roots, 55, 731
- Rosetta@home, 566
- round-robin scheduling
- about, 267–268
- defined, 731
- even number of teams, 270
- implementation, 271–273
- odd number of teams, 268–270
- round-robin tournament, 267
- route ciphers, 525–526
- route inspection problem. See Chinese postman problem (CPP)
- routines,
- row/column transposition cipher, 521–523, 731
- row-major order, 105
- rows, finding, 122–123
- RSA algorithm, 534–537, 731
RtlMoveMemory
function, 18
- runtime, 163, 303
- runtime functions, 11–16, 608
- Russell, Robert C., 511
- S
- satisfiability problem (SAT), 391–392, 548, 556, 731
- S-boxes (substitution boxes), 531, 733
ScheduleRoundRobinOdd
method, 273
- scytale, 731
- searching
- about, 201–202, 611
- best-first, 442–443
- bidirectional, 442
- binary, 203–204, 713
- breadth-first search, 714
- brute-force, 575
- exercises, 208
- exhaustive, 106–107, 202–203, 377–379, 611, 719
- game trees, 368–375
- general decision trees, 375–392
- interpolation, 204–205, 722
- linear, 106–107, 202–203, 611, 724
- majority voting, 205–207
- random, 381–382, 575
- random solution, 730
- string, 504–508
- traversals and, 296
- secondary clustering, 218, 731
- security through obscurity, 519, 731
- seed, 24
- seed clique, 485
Select Case
statement, 278
- selections
- about, 260
- counting, 254–255
- defined, 613, 731
- with duplicates, 262–263
- with loops, 261–262
- without duplicates, 264
- self-avoiding walks, creating, 33–34
- self-organizing linked lists, 82–86, 731
- self-organizing list, 609
- self-similar fractal, 239, 613, 732
- sender, in cryptography, 520, 732
- sentinels, 74–75, 609, 732
- separation rule, 395
- set intersection operator, 477
set
method, 115
- Set P, 475–476
- Set R, 475–476
- Set X, 475–476
- SETI@home, 566
- setting values, 125–127
- “Seven Bridges of Königsberg” problem, 485
- shape points, 441–442
- Shor's algorithm, 572
- shortest path algorithms
- about, 441
- best-first search, 442–443
- bidirectional search, 442
- early stopping, 442
- prohibitions, 443–446
- shape points, 441–442
- turn penalties, 443–446
- shortest path tree, 732
shuffle
method, 29
- SI (swarm intelligence)
- about, 392–393
- ant colony optimization, 393–394
- bees algorithm, 394, 712
- defined, 733–734
- swarm simulation, 394–397, 734
- sibling nodes, 732
- siblings, 286, 289
SierpDown
method, 244–245
- Sierpiński, Wacław (mathematician), 243, 247
- Sierpiński curve, 243–246, 732
SierpLeft
method, 244–245
SierpRight
method, 244–245
SierpUp
method, 244–245
- sieve of Eratosthenes, 44–45, 732
- simple substitution cipher, 529–530
- Simpson's rule, 50, 732
- simulated annealing, 384–385, 732
- single recursion, 732
- singly linked list, 72–79
- skyline problem
- about, 247
- defined, 732
- divide-and-conquer approach, 249–252
- lists, 248–249
- snapshot, 588–589, 620, 732
- snapshot token, 732
- solutions to exercises
- algorithm basics, 623–626
- arrays, 638–648
- balanced trees, 670–675
- basic network algorithms, 678–681
- complexity theory, 692–696
- cryptography, 689–691
- decision trees, 675–677
- distributed algorithms, 697–701
- hash tables, 655–657
- interview puzzles, 701–709
- linked lists, 633–638
- network algorithms, 681–686
- numerical algorithms, 626–633
- queues, 648–650
- recursion, 658–663
- searching, 653–655
- sorting, 650–653
- stacks, 648–650
- string algorithms, 686–689
- trees, 663–669
- sorted chaining, 612
- sorted hill climbing, 386–387
- sorted linked lists, 81–82
- sorted trees
- sorting
- about, 167–168, 610–611
- exercises, 198–200
- with
insertionsort
algorithm, 87–88
- O(N log N) algorithms, 174–191
- O(N2) algorithms, 168–174
- with
selectionsort
algorithm, 88–89
- Sub O(N log N) algorithms, 192–197
- Soundex algorithm, 511–513, 732
- space-filling curves, 245–246, 732
- spanning trees
- sparse arrays
- about, 121–123
- defined, 610, 732
- deleting values, 127–129
- finding rows/columns, 122–123
- getting values, 124–125
- setting values, 125–127
- spatial trees, 614
- specialized queues, 151–152
- specialized tree algorithms
- about, 322
- animal game, 322–324
- building trees, 328–329
- expression evaluation, 324–326
- intersecting with intervals, 330–332
- intersecting with points, 329–330
- interval trees, 326–328
- quadtrees, 332–337
- tries, 337–342
- speed, of algorithms, 607
Sqrt N
function, 14
- stable sort, 733
- stable sorting algorithm, 191
- stack algorithms
- about, 141
- reversing an array, 141
- stack insertionsort, 145–146
- stack selectionsort, 146–147
- tower of Hanoi, 143–145, 235–238, 735
- train sorting, 142–143
Stack
class (C#), 136
- stack insertionsort algorithm, 145–146
- stack selectionsort algorithm, 146–147
- stacks
- about, 135–136, 230, 610
- array, 138–139
- defined, 610, 733
- double, 139–141, 610
- implementing
Quicksort
algorithm with, 185
- linked-list, 136–138
StartExhaustiveSearch
method, 378
- starvation, 571, 733
- state transition diagram, 498, 733
- statements
End While
,
If-Then-Else
,
Return
, , 10
Select Case
, 278
Step
,
- steering behaviors, 395
Step
statement,
- Stephens, Rod (author)
- contact information for,
- Interview Puzzles Dissected: Solving and Understanding Interview Puzzles, 604
- stride, 215, 733
- string algorithms
- about, 493, 618
- calculating edit distance, 508–511
- exercises, 515–517
- matching parentheses, 494–496
- pattern matching, 497–504
- phonetic algorithms, 511–514, 618, 728
- string searching, 504–508
string
class (C#), 493
- string searching, 504–508
- strongly connected, 406, 420, 733
- strongly connected components
- Sub O(N log N) algorithms
- subgraph isomorphism problem, 556, 733
- subprocedures,
- subroutines,
- subset sum problem, 388, 556, 733
- substitution boxes (S-boxes), 531, 733
- substitution ciphers
- about, 526
- Caesar substitution cipher, 526–527, 714
- defined, 733
- one-time pad cipher, 530–531, 619, 727
- simple substitution cipher, 529–530
- Vigenère cipher, 527–529, 736
- substitution-permutation network, 733
- substitution-permutation network cipher, 531–533
- substring matching, 618
- subtree, 287, 289, 733
- superposition, 572, 733
- swap method, 83–84, 733, 735
- swarm intelligence (SI)
- about, 392–393
- ant colony optimization, 393–394
- bees algorithm, 394, 712
- defined, 733–734
- swarm simulation, 394–397, 734
- swarm intelligence algorithms, 616
- swarm simulation, 394–397, 734
- symmetric traversal, 299–300, 722
- symmetrically threaded tree, 317, 734
- symmetric-key encryption, 534, 734
- synchronization, 620
- systolic arrays, 562–565, 734
- T
- tail recursion, 734
- tail recursion removal, 274–275, 613
- Takao Nishizeki (computer scientist), 481
- task parallelism, 567, 734
- techinterview (website), 603
- techniques
- adaptive, 599, 609
- for algorithms, 607
- branch and bound, 379–381, 714
- data structures, 599
- decision trees, 599
- probability, 599
- problem structure, 599
- randomization, 599
- 10 famous Microsoft interview puzzles (website), 603
- 10 Google interview puzzles (website), 603
- teraflop (tflop), 566, 734
- testing
- connectivity, 413–415
- for primality, 45–47
- tflop (teraflop), 566
- thread, 90, 317, 614, 734
- threaded linked list, 609
- threaded trees
- about, 317–318
- building, 318–320
- defined, 734
- using, 320–322
- 3CNF (Three-term conjunctive normal form), 549, 734
- 3-node, 354, 711
- 3-satisfiability problem (3SAT), 392, 549, 556
- three-coloring algorithm, 458–459
- three-cycle problem, 734
- three-partition problem, 556, 734
- three-satisfiability (3SAT) problem, 556, 734
- Three-term conjunctive normal form (3CNF), 549, 734
- Top 5 Microsoft interview questions (website), 603
- top-down B-trees, 363, 615, 734
- topological sorting, 451–455, 617, 734
- tortoise-and-hare algorithm, 98–100, 431, 437, 735
- totient function, 535–536, 719
- tower of Hanoi, 143–145, 235–238, 735
- train sorting algorithm, 142–143
- transitive closure, 436, 617, 735
- transitive closure problem, 437–438
- transitive reduction, 436, 438–441, 617, 735
- transitivity
- about, 436
- transitive closure problem, 437–438
- transitive reduction, 436, 438–441, 617, 735
- transpose links, 421, 735
- transpose method, 83–84, 733, 735
- transpose network, 421, 735
- transposition ciphers
- about, 521
- column transposition, 523–525
- defined, 618, 735
- route ciphers, 525–526
- row/column transposition, 521–523
- trapezoid rule, 49–50, 735
- traveling salesman problem (TSP), 16, 391, 393–394, 556, 735
- traversals
- about, 296–297, 409
- breadth-first, 301–302, 412–413, 714
- building mazes, 419–420
- connectivity testing, 413–415
- defined, 614, 616, 735
- depth-first, 297, 410–412, 717
- Euclidean minimum spanning tree (EMST), 418–419
- inorder, 299–300, 722
- minimal spanning trees, 417–418, 725
- postorder, 300–301, 728
- preorder, 297–299, 728
- run times, 303
- spanning trees, 416, 417–418, 617, 732
- uses for, 302
TraverseInorder
method, 300
TraversePostorder
method, 301
TraversePreorder
method, 299
TreeNode
class, 293–294, 310, 311, 312
- trees
- about, 285, 614
- AVL, 350–353, 615, 712
- balanced. See balanced trees
- binary, 12, 175–176, 286, 288–291, 713
- binomial, 152–154, 155–156, 713
- bottom-up B-trees, 363, 713
- B-trees, 359–362, 615, 712
- B+trees, 363–364, 712
- call, 190
- complete, 12, 175–176, 287, 288, 295–296, 715
- decision, 367–397, 398–401, 615–616, 717
- Euclidean spanning, 617
- exercises, 342–348
- full, 287, 289, 720
- game, 615–616
- general, 312–314
- height of, 153, 287, 289, 305
- interval, 326–328, 326–342, 722
- knowledge, 614
- lowest common ancestors, 309–316
- maximum leaf spanning, 724
- minimal spanning, 417–418, 725
- minimum degree spanning, 725
- ordered, 287, 289, 727
- parse, 496
- perfect, 287, 289, 727
- prefix, 337–342, 614, 735
- representations, 292–296
- shortest path, 732
- sorted, 12, 300, 303–309, 303–310, 309–310, 614, 732
- spanning, 416, 417–418, 617, 732
- spatial, 614
- specialized algorithms, 322–326
- symmetrically threaded, 317, 734
- terminology for, 285–289
- threaded, 317–322, 734
- top-down B-trees, 363, 615, 734
- traversal, 296–303
- 2-3, 354–358, 615, 711
- unordered, 287, 736
- treesort, 735
- trial division, 44
- triangles, finding, 480–482
- triangular arrays, 118–121, 735
- tries, 337–342, 614, 735
- Triple DES (3DES/TDES), 534, 735
- true random-number generators (TRNGs), 24, 608, 735
- TSP (traveling salesman problem), 16, 391, 393–394, 556, 735
- Turing, Alan (mathematician), 545
- Turing machine, 545–546, 736
- turn penalties, 443–446
- two dimensions, 114–115
- two generals problem, 580–581, 620, 736
- 2-3 trees
- about, 354
- adding values, 355–356
- defined, 615, 711
- deleting values, 356–358
2
N
function, 15–16
- 2-node, 354, 711
- two-coloring algorithm, 456–458
- two-dimensional arrays, 105
- V
- value
null
, 13
- values
- deleting, 127–129
- generating, 24–26
- getting, 124–125
- setting, 125–127
- vehicle routing, 736
- vehicle routing problem, 556
- vertex. See nodes
- vertex coloring, 556, 726
- vertex coloring problem, 555
- vertex cover, 736
- vertex cover problem, 556, 726
- Vigenère, Blaise de (diplomat), 527
- Vigenère cipher, 527–529, 736
- virtual backlink, 736
Visit
method, 422
- Visual Basic, automatic memory management and, 79
- visualizing functions, 16–17
- W
- waiter, 579
- Warnsdorff, H. C. von, 259
- weakly connected, 406, 736
- websites
- A2Z Interviews: puzzles, 604
- Advanced Encryption Standard (AES), 533
- Berkeley Open Infrastructure for Network Computing (BOINC), 566
- “Building a 270* Teraflops Deep Learning Box for Under $10,000,” 566
- Byzantine Empire, 581
- CareerCup, 604
- Cook-Levin theorem, 548
- CoolInterview puzzles, 604
- Data Encryption Standard (DES), 534
- Einstein@Home, 566
- Euclidean minimum spanning tree (EMST), 419
- Extensible Markup Language (XML), 295
- external sorting on tape drives, 191
- Facebook interview puzzles group, 603
- Great Internet Mersenne Prime Search (GIMPS), 566
- Haidong Wang's interview puzzles, 603
- How to Ace a Google Interview, 603
- IBM Q System One, 572
- Math Is Fun, 129
- Math Olympiads, 604
- “Matrix,” 129
- phonetic algorithms, 514
- Polish notation, 302
- Pretty Good Privacy (PGP), 537
- prime factoring, 44
- quantum computing, 572
- Random.org, 24
- reverse Polish notation, 302
- Reversi game, 375
- Rosetta@home, 566
- SETI@home, 566
- "Seven Bridges of Königsberg" problem, 485
- tape drives, 191
- techniterview, 603
- 10 famous Microsoft interview puzzles, 603
- 10 Google interview puzzles, 603
- Top 5 Microsoft interview questions, 603
- Turing machine, 546
- URLs, 480
- Why Brainteasers Don't Belong in Job Interview, 603
- weights, 404, 406, 736., See also costs
- wheel factorization, 44
While
loop, , 38, 74, 179, 188, 221, 275, 278, 321
- “Why Are Manhole Covers Round? A Laboratory Study of Reactions to Puzzle Interviews,” 596
- Why Brainteasers Don't Belong in Job Interview (website), 603
- work assignment problem, 467–468, 736
- X
- XML (Extensible Markup Language), 295
- Z
- zero sum subset problem, 551, 737
- zeros, finding, 55–57
- zero-time sort, 565, 737
..................Content has been hidden....................
You can't read the all page of ebook, please click
here login for view all page.