Algorithm Design

I Fundamental Tools 1

1 Algorithm Analysis 3

1.1 Methodologies for Analyzing Algorithms  5

1.2 Asymptotic Notation 13

1.3 A Quick Mathematical Review  21

1.4 Case Studies in Algorithm Analysis  31

1.5 Amortization  34

1.6 Experimentation  42

1.7 Exercises  47

2 Basic Data Structures 55

2.1 Stack sand Queues  57

2.2 Vectors, Lists, and Sequences  65

2.3 Trees  75

2.4 Priority Queues and Heaps  94

2.5 Dictionaries and Hash Tables  114

2.6 Java Example: Heap  128

2.7 Exercises  131

3 Search Trees and Skip Lists 139

3.1 Ordered Dictionaries and Binary Search Trees  141

3.2 AVL Trees  152

3.3 Bounded-Depth Search Trees  159

3.4 Splay Trees  185

3.5 Sk i p Lists  195

3.6 Java Example: AVL and Red-Black Trees  202

3.7 Exercises  212

4 Sorting, Sets, and Selection 217

4.1 Merge-Sort  219

4.2 The Set Abstract Data Type  225

4.3 Quick -Sort  235

4.4 A Lower Bound on Comparison-Based Sorting  239

4.5 Buck et-Sort and Radix-Sort  241

4.6 Comparison of Sorting Algorithms  244

4.7 Selection  245

4.8 Java Example: In-Place Quick -Sort  248

4.9 Exercises  251

5 Fundamental Techniques 257

5.1 The GreedyMethod  259

5.2 Divide-and-Conquer  263

5.3 Dynamic Programming  274

5.4 Exercises  282

II Graph Algorithms 285

6 Graphs 287

6.1 The Graph Abstract Data Type  289

6.2 Data Structures for Graphs  296

6.3 Graph Traversal  303

6.4 Directed Graphs  316

6.5 Java Example: Depth-First Search  329

6.6 Exercises  335

7 Weighted Graphs 339

7.1 Single-Source Shortest Paths  341

7.2 All-Pairs Shortest Paths  354

7.3 Minimum Spanning Trees  360

7.4 Java Example: Dijk stra¢s Algorithm  373

7.5 Exercises  376

8 Network Flow and Matching 381

8.1 Flows and Cuts  383

8.2 Maximum Flow  387

8.3 Maximum BipartiteMatching  396

8.4 Minimum-Cost Flow  398

8.5 Java Example: Minimum-Cost Flow  405

8.6 Exercises  412

III Internet Algorithmics 415

9 Text Processing 417

9.1 Strings and PatternMatching Algorithms  419

9.2 Tries  429

9.3 Text Compression  440

9.4 Text Similarity Testing  443

9.5 Exercises  447

10 Number Theory and Cryptography 451

10.1 Fundamental Algorithms Involving Numbers  453

10.2 Cryptographic Computations  471

10.3 Information Security Algorithms and Protocols  481

10.4 The Fast Fourier Transform  488

10.5 Java Example: FFT  500

10.6 Exercises  508

11 Network Algorithms 511

11.1 ComplexityMeasures and Models  513

11.2 Fundamental Distributed Algorithms  517

11.3 Broadcast and Unicast Routing  530

11.4 Multicast Routing  535

11.5 Exercises  541

IV Additional Topics 545

12 Computational Geometry 547

12.1 Range Trees  549

12.2 Priority Search Trees  556

12.3 Quadtrees and k-D Trees  561

12.4 The Plane Sweep Technique  565

12.5 Convex Hulls  572

12.6 Java Example: Convex Hull  583

12.7 Exercises  587

13 NP-Completeness 591

13.1 P and NP  593

13.2 NP-Completeness  599

13.3 Important NP-Complete Problems  603

13.4 Approximation Algorithms  618

13.5 Back track i ng and Branch-and-Bound  627

13.6 Exercises  638

14 Algorithmic Frameworks 643

14.1 External-Memory Algorithms  645

14.2 Parallel Algorithms  657

14.3 Online Algorithms  667

14.4 Exercises  680

A Useful Mathematical Facts 685

Bibliography 689

Index 698