Fundamentals of Data Structures by Ellis Horowitz

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

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

6. BASIC SEARCH AND TRAVERSAL TECHNIQUES
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

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

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 …………………………………………….. 622