Adapter's Foreword

Preface

1 Introduction 1

1.1. What's the Book About? 1

1.2. A Brief Introduction to Recursion 3

Summary 7

Exercises 7

References 8

2 Algorithm Analysis 9

2.1. Mathematical Background 9

2.2. Model 12

2.3. What to Analyze 12

2.4. Running Time Calculations 14

2.4.1. A Simple Example 15

2.4.2. General Rules 15

2.4.3. Solutions for the Maximum Subsequence Sum Problem 18

2.4.4. Logarithms in the Running Time 22

2.4.5. Checking Your Analysis 27

2.4.6. A Grain of Salt 27

Summary 28

Exercises 29

References 33

3 Lists, Stacks, and Queues 35

3.1. Abstract Data Types (ADTs) 35

3.2. The List AnT 36

3.2.1. Simple Array Implementation of Lists 37

3.2.2. Linked Lists 37

3.2.3. Programming Details 38

3.2.4. Common Errors 43

3.2.5. Doubly Linked Lists 45

3.2.6. Circularly Linked Lists 46

3.2.7. Examples 46

3.2.8. Cursor Implementation of Linked Lists 50

3.3. The Stack ADT 56

3.3.1. Stack Model 56

3.3.2. Implementation of Stacks 57

3.3.3. Applications 65

3.4. The Queue AnT 73

3.4.1. Queue Model 73

3.4.2. Array Implementation of Queues 73

3.4.3. Applications of Queues 78

Summary 79

Exercises 79

4 Trees 83

4.1. Preliminaries 83

4.1.1. Terminology 83

4.1.2. Tree Traversals with an Application 84

4.2. Binary Trees 85

4.2.1. Implementation 86

4.2.2. Expression Trees 87

4.2.3. Tree Traversals 90

4.3. The Search Tree ADT Binary Search Trees 97

4.3.1. MakeEmpty 97

4.3.2. Find 97

4.3.3. FindMin and FindMax 99

4.3.4. Insert 100

4.3.5. Delete 101

4.3.6. Average-Case Analysis103

4.4. AVL Trees 106

4.4.1. Single Rotation 108

4.4.2. Double Rotation 111

4.5. Splay Trees 119

4.5.1. A Simple Idea (That Does Not Work) 12 0

4.5.2. Splaying 12 2

4.6. B-Trees 128

Summary 133

Exercises 134

References 141

5 Priority Queues (Heaps) 145

5.1. Model 145

5.2. Simple Implementations 146

5.3. Binary Heap 147

5.3.1. Structure Property 147

5.3.2. Heap Order Property 148

5.3.3. Basic Heap Operations 150

5.3.4. Other Heap Operations 154

5.4. Applications of Priority Queues 157

5.4.1. The Selection Problem 157

5.4.2. Event Simulation 159

5.5. d-Heaps 160

5.6. Leftist Heaps 161

5.6.1. Leftist Heap Property 161

5.6.2. Leftist Heap Operations 162

5.7. Skew Heaps 168

5.8. Binomial Queues 170

5.8.1. Binomial Queue Structure 170

5.8.2. Binomial Queue Operations 172

5.8.3. Implementation of Binomial Queues 173

Summary 180

Exercises 180

References 184

6 Sorting 187

6.1. Preliminaries 187

6.2. Insertion Sort 188

6.2.1. The Algorithm 188

6.2.2. Analysis of Insertion Sort 189

6.3. A Lower Bound for Simple Sorting Algorithms 189

6.4. Shellsort 190

6.4.1. Worst-Case Analysis of Shellsort 192

6.5. Heapsort 194

6.5.1. Analysis of Heapsort 196

6.6. Mergesort 198

6.6.1. Analysis of Mergesort 200

6.7. Quicksort 203

6.7.1. Picking the Pivot 204

6.7.2. Partitioning Strategy 205

6.7.3. Small Arrays 20 8

6.7.4. Actual Quicksort Routines 208

6.7.5. Analysis of Quicksort 209

6.7.6. A Linear-Expected-Time Algorithm for Selection 213

6.8. Sorting Large Structures 215

6.9. A General Lower Bound for Sorting 216

6.9.1. Decision Trees 217

6.10. Bucket Sort and Radix Sort 219

6.11. External Sorting 222

6.11.1. Why We Need New Algorithms 222

6.11.2. Model for External Sorting 222

6.11.3. The Simple Algorithm 222

6.11.4. Multiway Merge 224

6.11.5. Polyphase Merge 225

6.11.6. Replacement Selection 226

Summary 227

Exercises 229

7 Hashing 235

7.1. General Idea 235

7.2. Hash Function 237

7.3. Separate Chaining 239

7.4. Open Addressing 244

7.4.1. Linear Probing 244

7.4.2. Quadratic Probing 247

7.4.3. Double Hashing 251

7.5. Rehashing 252

7.6. Extendible Hashing 255

Summary 258

Exercises 259

References 262

8 The Disjoint Set AnT 265

8.1. Equivalence Relations 265

8.2. The Dynamic Equivalence Problem 266

8.3. Basic Data Structure 267

8.4. Smart Union Algorithms 271

8.5. Path Compression 273

8.6. Worst Case for Union-by-Rank and Path Compression 275

8.6.1. Analysis of the Union/Find Algorithm 275

8.7. An Application 281

Summary 281

Exercises 282

References 283

9 Graph Algorithms 285

9.1. Definitions 285

9.1.1. Representation of Graphs 286

9.2. Topological Sort 288

9.3. Shortest-Path Algorithms 292

9.3.1. Unweighted Shortest Paths 293

9.3.2. Dijkstra's Algorithm 297

9.3.3. Graphs with Negative Edge Costs 306

9.3.4. Acyclic Graphs 307

9.3.5. All-Pairs Shortest Path 310

9.4. Network Flow Problems 310

9.4.1. A Simple Maximum-Flow Algorithm 311

9.5. Minimum Spanning Tree 315

9.5.1. Prim's Algorithm 316

9.5.2. Kruskal's Algorithm 318

9.6. Applications of Depth-First Search 3:21

9.6.1. Undirected Graphs 322

9.6.2. Biconnectivity 324

9.6.3. Euler Circuits 328

9.6.4. Directed Graphs 331

9.6.5. Finding Strong Components 333

9.7. Introduction to NP-Completeness 334

9.7.2. The Class NP 336

9.7.3. NP-Complete Problems 337

Summary 339

Exercises 339

References 345

10 Algorithm Design Techniques 349

10.1. Greedy Algorithms 349

10.1.1. A Simple Scheduling Problem 350

10.1.2. Huffman Codes 353

10.1.3. Approximate Bin Packing 359

10.2. Divide and Conquer 367

10.2.1. Running Time of Divide and Conquer Algorithms 368

10.2.2. Closest-Points Problem 370

10.2.3. The Selection Problem 375

10.2.4. Theoretical Improvements for Arithmetic Problems 378

10.3. Dynamic Programming 382

10.3.1. Using a Table Instead of Recursion 382

10.3.2. Ordering Matrix Multiplications 385

10.3.3. Optimal Binary Search Tree 389

10.3.4. All-Pairs Shortest Path 392

10.4. Randomized Algorithms 394

10.4.1. Random Number Generators 396

10.4.2. Skip Lists 399

10.4.3. Primality Testing 401

10.5. Backtracking Algorithms 403

10.5.1. The Turnpike Reconstruction Problem 405

10.5.2. Games 407

Summary 415

Exercises 417

References 424

11 Amortized Analysis 429

11.1. An Unrelated Puzzle 430

11.2. Binomial Queues 430

11.3. Skew Heaps 435

11.4. Fibonacci Heaps 437

11.4.1. Cutting Nodes in Leftist Heaps 430

11.4.2. Lazy Merging for Binomial Queues 441

11.4.3. The Fibonacci Heap Operations 444

11.4.4. Proof of the Time Bound 445

11.5. Splay Trees 447

Summary 451

Exercises 452

References 453

12 Advanced Data Structures and Implementation 455

12.1. Top-Down Splay Trees 455

12.2. Red Black Trees 459

12.2.1. Bottom-Up Insertion 464

12.2.2. Top-Down Red Black Trees 465

12.2.3. Top-Down Deletion 467

12.3. Deterministic Skip Lists 471

12.4. &A-Trees 478

12.5. Treaps 484

12.6. k-d Trees 487

12.7. Pairing Heaps 490

Summary 496

Exercises 497

References 499