Fundamentals of computer algorithms

1. INTRODUCTION
1.1 What is an algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Writing algorithms in SPARKS . . . . . . . . . . . . . . . . . . . . . . . . .. . . 4
1.3 Writing structured programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Analyzing algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
References and selected readings , . . . . . . . . . . . . . . . . . . . . . . . . . 40
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2. ELEMENTARY DATA STRUCTURES
2.1 Stacks and queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3 Heaps and heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.4 Sets and disjoint set union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.5 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.6 Hashing................................................ 82
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3. DIVIDE-AND-CONQUER
3 .1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.2 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.3 Finding the maximum and minimum. . . . . . . . . . . . . . . . . . . . . . . . 108
3.4 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.6 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
3. 7 Strassen's matrix multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
xi
xii Contents
4. THE GREEDY METHOD
4.1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.2 Optimal storage on tapes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.3 Knapsack problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.4 Job sequencing with deadlines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5 Optimal merge patterns................................... 169
4.6 Minimum spanning trees.................................. 174
4. 7 Single source shortest paths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5. DYNAMIC PROGRAMMING
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
The general method ..................................... .
Multistage graphs ....................................... .
All pairs shortest paths .................................. .
Optimal binary search trees ............................... .
0/1 knapsack .......................................... .
Reliability design ....................................... .
The traveling salesperson problem ......................... .
Flow shop scheduling .................. ·t" ............ .. References and selected readings.......... . .............. .
Exercises .............................................. .
6. BASIC SEARCH AND TRAVERSAL TECHNIQUES
198
203
208
211
219
228
231
234
238
240
6.1 The techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
6.2 Code optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
6.3 AND/OR graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
6.4 Game trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
6.5 Biconnected components and depth first search . . . . . . . . . . . . . . . 302
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
7. BACKTRACKING
7 .1 The general method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
7.2 The 8-queens problem.................................... 337
7.3 Sum of subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
7 .4 Graph coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
7. 5 Hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.6 Knapsack problem....................................... 350
Contents xiii
References and selected readings. . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
8. BRANCH-AND-BOUND
8.1 The method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
8.2 011 knapsack problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
8.3 Traveling salesperson.................................. . . . 403
8.4 Efficiency considerations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
9. ALGEBRAIC SIMPLIFICATION AND
TRANSFORMATIONS
9.1 The general method...................................... 422
9.2 Evaluation and interpolation..... . . . . . . . . . . . . . . . . . . . . . . . . . . 424
9.3 The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
9.4 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
9.5 Even faster evaluation and interpolation . . . . . . . . . . . . . . . . . . . . . 447
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
10. LOWER BOUND THEORY
10 .1 Comparison trees for sorting and searching. . . . . . . . . . . . . . . . . 461
10.2 Oracles and Adversary Arguments . . . . . . . . . . . . . . . . . . . . . . . . 469
10.3 Techniques for algebraic problems.... . . . . . . . . . . . . . . . . . . . . . 478
10.4 Some lower bounds on parallel computation . . . . . . . . . . . . . . . . . 488
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 494
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
11. NP-HARD AND NP-COMPLETE PROBLEMS
11.1 Basic concepts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
11.2 Cook's theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
11.3 NP-Hard graph problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
11.4 NP-Hard scheduling problems............................ 532
11.5 NP-Hard code generation problems.. . . . . . . . . . . . . . . . . . . . . . . 538
11.6 Some simplified NP-Hard problems. . . . . . . . . . . . . . . . . . . . . . . . 545
References and selected readings . . . . . . . . . . . . . . . . . . . . . . . . . . 548
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
xiv Contents
12. APPROXIMATION ALGORITHMS FOR NP-HARD
PROBLEMS
12.1 Introduction........................................... 559
12.2 Absolute approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
12.3 E-approximations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
12.4 Polynomial time approximation schemes................... 578
12.5 Fully polynomial time approximation schemes . . . . . . . . . . . . . . 585
12.6 Probabilistically good algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 596
References and selected readings. . . . . . . . . . . . . . . . . . . . . . . . . . 599
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
APPENDIX A. SPARKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
INDEX ..................................