A Textbook of Data Structures and Algorithms, Volume 3

Preface xi

Acknowledgments xvii

Chapter 13. Hash Tables 1

13.1. Introduction 1

13.2. Hash table structure 2

13.3. Hash functions 4

13.4. Linear open addressing 5

13.5. Chaining 13

13.6. Applications 18

13.7. Illustrative problems 23

Chapter 14. File Organizations 33

14.1. Introduction 33

14.2. Files 34

14.3. Keys 36

14.4. Basic file operations 38

14.5. Heap or pile organization 38

14.6. Sequential file organization 39

14.7. Indexed sequential file organization 41

14.8. Direct file organization 48

14.9. Illustrative problems 50

Chapter 15. k-d Trees and Treaps 61

15.1. Introduction 61

15.2. k-d trees: structure and operations 61

15.3. Treaps: structure and operations 76

15.4. Illustrative problems 83

Chapter 16. Searching 93

16.1. Introduction 93

16.2. Linear search 94

16.3. Transpose sequential search 96

16.4. Interpolation search 98

16.5. Binary search 100

16.6. Fibonacci search 104

16.7. Skip list search 108

16.8. Other search techniques 116

16.9. Illustrative problems 118

Chapter 17. Internal Sorting 131

17.1. Introduction 131

17.2. Bubble sort 132

17.3. Insertion sort 135

17.4. Selection sort 138

17.5. Merge sort 140

17.6. Shell sort 147

17.7. Quick sort 153

17.8. Heap sort 159

17.9. Radix sort 167

17.10. Counting sort 171

17.11. Bucket sort 175

17.12. Illustrative problems 179

Chapter 18. External Sorting 197

18.1. Introduction 197

18.2. External storage devices 198

18.3. Sorting with tapes: balanced merge 202

18.4. Sorting with disks: balanced merge 206

18.5. Polyphase merge sort 212

18.6. Cascade merge sort 214

18.7. Illustrative problems 216

Chapter 19. Divide and Conquer 229

19.1. Introduction 229

19.2. Principle and abstraction 229

19.3. Finding maximum and minimum 231

19.4. Merge sort 233

19.5. Matrix multiplication 234

19.6. Illustrative problems 239

Chapter 20. Greedy Method 245

20.1. Introduction 245

20.2. Abstraction 245

20.3. Knapsack problem 246

20.4. Minimum cost spanning tree algorithms 249

20.5. Dijkstra's algorithm 251

20.6. Illustrative problems 251

Chapter 21. Dynamic Programming 261

21.1. Introduction 261

21.2. 0/1 knapsack problem 263

21.3. Traveling salesperson problem 266

21.4. All-pairs shortest path problem 269

21.5. Optimal binary search trees 272

21.6. Illustrative problems 280

Chapter 22. P and NP Class of Problems 287

22.1. Introduction 287

22.2. Deterministic and nondeterministic algorithms 289

22.3. Satisfiability problem 292

22.4. NP-complete and NP-hard problems 297

22.5. Examples of NP-hard and NP-complete problems 300

22.6. Cook's theorem 302

22.7. The unsolved problem P (?/=) NP problem 303

22.8. Illustrative problems 304

References 311

Index 313

Summaries of other volumes 317