# Algorithm Design and Applications

ISBN: 978-1-119-02861-1

Oct 2014

804 pages

Select type: E-Book

\$64.00

## Description

Introducing a NEW addition to our growing library of computer science titles, Algorithm Design and Applications, by Michael T. Goodrich & Roberto Tamassia! Algorithms is a course required for all computer science majors, with a strong focus on theoretical topics. Students enter the course after gaining hands-on experience with computers, and are expected to learn how algorithms can be applied to a variety of contexts. This new book integrates application with theory.

Goodrich & Tamassia believe that the best way to teach algorithmic topics is to present them in a context that is motivated from applications to uses in society, computer games, computing industry, science, engineering, and the internet. The text teaches students about designing and using algorithms, illustrating connections between topics being taught and their potential applications, increasing engagement.

## Related Resources

### Instructor

Request an Evaluation Copy for this title

View Instructor Companion Site

Contact your Rep for all inquiries

Preface xi

1 AlgorithmAnalysis 1

1.1 Analyzing Algorithms 3

1.2 A Quick Mathematical Review 19

1.3 A Case Study in Algorithm Analysis 29

1.4 Amortization 34

1.5 Exercises 42

Part I: Data Structures

2 BasicDataStructures 51

2.1 Stacks and Queues 53

2.2 Lists 60

2.3 Trees 68

2.4 Exercises 84

3 BinarySearchTrees 89

3.2 Range Queries 101

3.3 Index-Based Searching 104

3.4 Randomly-Constructed Search Trees 107

3.5 Exercises 110

4 BalancedBinarySearchTrees 115

4.1 Ranks and Rotations 117

4.2 AVL Trees 120

4.3 Red-Black Trees 126

4.4 Weak AVL Trees 130

4.5 Splay Trees 139

4.6 Exercises 149

5 PriorityQueuesandHeaps 155

5.1 Priority Queues 157

5.2 PQ-Sort, Selection-Sort, and Insertion-Sort 158

5.3 Heaps 163

5.4 Heap-Sort 174

5.5 Extending Priority Queues 179

5.6 Exercises 182

6 HashTables 187

6.1 Maps 189

6.2 Hash Functions 192

6.3 Handling Collisions and Rehashing 198

6.4 Cuckoo Hashing 206

6.5 Universal Hashing 212

6.6 Exercises 215

7 Union-FindStructures 219

7.1 Union-Find and its Applications 221

7.2 A List-Based Implementation 225

7.3 A Tree-Based Implementation 228

7.4 Exercises 236

Part II: Sorting and Selection

8 Merge-SortandQuick-Sort 241

8.1 Merge-Sort 243

8.2 Quick-Sort 250

8.3 A Lower Bound on Comparison-Based Sorting 257

8.4 Exercises 259

9 FastSortingandSelection 265

9.1 Bucket Sort and Radix Sort 267

9.2 Selection 270

9.3 Weighted Medians 276

9.4 Exercises 279

Part III: Fundamental Techniques

10 The Greedy Method 283

10.1 The Fractional Knapsack Problem 286

10.3 Text Compression and Huffman Coding 292

10.4 Exercises 298

11 Divide-and-Conquer 303

11.1 Recurrences and the Master Theorem 305

11.2 Integer Multiplication 313

11.3 Matrix Multiplication 315

11.4 The Maxima-Set Problem 317

11.5 Exercises 319

12 Dynamic Programming 323

12.1 Matrix Chain-Products 325

12.2 The General Technique 329

12.3 Telescope Scheduling 331

12.4 Game Strategies 334

12.5 The Longest Common Subsequence Problem 339

12.6 The 0-1 Knapsack Problem 343

12.7 Exercises 346

Part IV: Graph Algorithms

13 Graphs and Traversals 353

13.1 Graph Terminology and Representations 355

13.2 Depth-First Search 365

13.4 Directed Graphs 373

13.5 Biconnected Components 386

13.6 Exercises 392

14 Shortest Paths 397

14.1 Single-Source Shortest Paths 399

14.2 Dijkstra’s Algorithm 400

14.3 The Bellman-Ford Algorithm 407

14.4 Shortest Paths in Directed Acyclic Graphs 410

14.5 All-Pairs Shortest Paths 412

14.6 Exercises 418

15 Minimum Spanning Trees 423

15.1 Properties of Minimum Spanning Trees 425

15.2 Kruskal’s Algorithm 428

15.3 The Prim-Jarn´ýk Algorithm 433

15.4 Bar°uvka’s Algorithm 436

15.5 Exercises 439

16 Network Flow and Matching 443

16.1 Flows and Cuts 445

16.2 Maximum Flow Algorithms 452

16.3 Maximum Bipartite Matching 458

16.4 Baseball Elimination 460

16.5 Minimum-Cost Flow 462

16.6 Exercises 469

Part V: Computational Intractability

17 NP-Completeness 473

17.1 P and NP 476

17.2 NP-Completeness 483

17.3 CNF-SAT and 3SAT 489

17.4 VERTEX-COVER, CLIQUE, and SET-COVER 492

17.5 SUBSET-SUM and KNAPSACK 496

17.6 HAMILTONIAN-CYCLE and TSP 499

17.7 Exercises 502

18 Approximation Algorithms 507

18.1 The Metric Traveling Salesperson Problem 511

18.2 Approximations for Covering Problems 515

18.3 Polynomial-Time Approximation Schemes 518

18.4 Backtracking and Branch-and-Bound 521

18.5 Exercises 525

19 Randomized Algorithms 529

19.1 Generating Random Permutations 531

19.2 Stable Marriages and Coupon Collecting 534

19.3 Minimum Cuts 539

19.4 Finding Prime Numbers 546

19.5 Chernoff Bounds 551

19.6 Skip Lists 557

19.7 Exercises 563

20 B-Trees and External-Memory 569

20.1 External Memory 571

20.2 (2,4) Trees and B-Trees 574

20.3 External-Memory Sorting 590

20.4 Online Caching Algorithms 593

20.5 Exercises 600

21 Multi-Dimensional Searching 603

21.1 Range Trees 605

21.2 Priority Search Trees 609

21.3 Quadtrees and k-D Trees 614

21.4 Exercises 618

22 Computational Geometry 623

22.1 Operations on Geometric Objects 625

22.2 Convex Hulls 630

22.3 Segment Intersection 638

22.4 Finding a Closest Pair of Points 642

22.5 Exercises 646

23 String Algorithms 651

23.1 String Operations 653

23.2 The Boyer-Moore Algorithm 656

23.3 The Knuth-Morris-Pratt Algorithm 660

23.4 Hash-Based Lexicon Matching 664

23.5 Tries 669

23.6 Exercises 680

24 Cryptography 685

24.1 Greatest Common Divisors (GCD) 687

24.2 Modular Arithmetic 691

24.3 Cryptographic Operations 699

24.4 The RSA Cryptosystem 703

24.5 The El Gamal Cryptosystem 706

24.6 Exercises 708

25 The Fast Fourier Transform 711

25.1 Convolution 713

25.2 Primitive Roots of Unity 715

25.3 The Discrete Fourier Transform 717

25.4 The Fast Fourier Transform Algorithm 721

25.5 Exercises 727

26 Linear Programming 731

26.1 Formulating the Problem 734

26.2 The Simplex Method 739

26.3 Duality 746

26.4 Applications of Linear Programming 750

26.5 Exercises 753

A UsefulMathematicalFacts 761

Bibliography 765

Index 774

• Extensive collection of topics provide coverage of both classic and emerging algorithmic methods such as:
• mathematics for asymptotic analysis, including amortization and randomization,
• general algorithm design techniques, including the greedy method, divide and-conquer, and dynamic programming,
• data structures, including lists, trees, heaps, search trees, B-trees, hash tables, skip lists, union-find structures, and multi-dimensional trees,
• algorithmic frameworks, such as NP-completeness, approximation algorithms, and external-memory algorithms, and
• fundamental algorithms, including sorting, graph algorithms, computational geometry, numerical algorithms, cryptography, Fast Fourier Transform (FFT), and linear programming.
• Each chapter is relatively independent of other chapters, providing instructors and readers with greater flexibility with respect to which chapters to explore
• Emphasizing practical applications, each chapter is written to begin with a brief discussion of an application that motivates the topic of the chapter, highlighting real-world uses and how the topic of the chapter could be used in practice
• Included are detailed pseudo-code descriptions and complete mathematical analysis
• The chapters are designed so that they can be covered in 1-3 lectures, depending on the depth of the coverage
• The text can be used for a core algorithms course, classically known as CS7, as well as upper-division/graduate data structures or algorithms, or a two-course sequence of the two topics
• Contains over 800 exercises which are divided between the following categories:
• Reinforcement exercises, which test comprehension of chapter topics
• Creativity exercises, which test creative utilization of techniques from the chapter
• Application exercises, which test uses of the topics of the chapter for real-world or contrived applications
• The exercises are distributed so that roughly 35% are reinforcement exercises, 40% are creativity exercises, and 25% are application exercises.