Algorithm Design and Applications

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. 

Table of Contents:
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.1 Searches and Updates 91 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.2 Task Scheduling 289 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.3 Breadth-First Search 370 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 Part VI: Additional Topics 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

About the Author :
Michael T. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, Bioinformatics, and geometric computing. He has pioneered and led research on efficient solutions to a number of fundamental problems, including sorting, convex hull construction, linear programming, privacy-preserving data access, network traceback, and data authentication.