Algorithm Design and Applications
by Michael T. Goodrich, Roberto Tamassia
1st Edition
Publisher: Wiley
Book Details
| Print ISBN | 9781118335918 |
| eText ISBN | 9781119028611 |
| Publisher | Wiley |
| Publishing Year | 2014 |
| Edition | 1st Edition |
| Language | English |
| Pages | 800 |
Algorithm Design and Applications, 1st Edition, is a computer science textbook by Michael T. Goodrich and Roberto Tamassia that integrates theoretical analysis with practical application. Published by Wiley, the work shows how foundational algorithmic concepts operate across technological and scientific domains.
The text addresses core data structures, sorting and selection, algorithmic paradigms such as the greedy method and dynamic programming, and computational intractability. It also explores graph algorithms, approximation methods, and specialized topics including computational geometry and cryptography.
Designed for core or advanced coursework, every chapter begins with a practical discussion demonstrating real-world applications in society, gaming, industry, science, engineering, or the internet.
Table of Contents
Chapter 1: AlgorithmAnalysis
- • 1.1 Analyzing Algorithms
- • 1.2 A Quick Mathematical Review
- • 1.3 A Case Study in Algorithm Analysis
- • 1.4 Amortization
- • 1.5 Exercises
Chapter 2: BasicDataStructures
- • 2.1 Stacks and Queues
- • 2.2 Lists
- • 2.3 Trees
- • 2.4 Exercises
Chapter 3: BinarySearchTrees
- • 3.1 Searches and Updates
- • 3.2 Range Queries
- • 3.3 Index-Based Searching
- • 3.4 Randomly-Constructed Search Trees
- • 3.5 Exercises
Chapter 4: BalancedBinarySearchTrees
- • 4.1 Ranks and Rotations
- • 4.2 AVL Trees
- • 4.3 Red-Black Trees
- • 4.4 Weak AVL Trees
- • 4.5 Splay Trees
- • 4.6 Exercises
Chapter 5: PriorityQueuesandHeaps
- • 5.1 Priority Queues
- • 5.2 PQ-Sort, Selection-Sort, and Insertion-Sort
- • 5.3 Heaps
- • 5.4 Heap-Sort
- • 5.5 Extending Priority Queues
- • 5.6 Exercises
Chapter 6: HashTables
- • 6.1 Maps
- • 6.2 Hash Functions
- • 6.3 Handling Collisions and Rehashing
- • 6.4 Cuckoo Hashing
- • 6.5 Universal Hashing
- • 6.6 Exercises
Chapter 7: Union-FindStructures
- • 7.1 Union-Find and its Applications
- • 7.2 A List-Based Implementation
- • 7.3 A Tree-Based Implementation
- • 7.4 Exercises
Chapter 8: Merge-SortandQuick-Sort
- • 8.1 Merge-Sort
- • 8.2 Quick-Sort
- • 8.3 A Lower Bound on Comparison-Based Sorting
- • 8.4 Exercises
Chapter 9: FastSortingandSelection
- • 9.1 Bucket Sort and Radix Sort
- • 9.2 Selection
- • 9.3 Weighted Medians
- • 9.4 Exercises
Chapter 10: The Greedy Method
- • 10.1 The Fractional Knapsack Problem
- • 10.2 Task Scheduling
- • 10.3 Text Compression and Huffman Coding
- • 10.4 Exercises
Chapter 11: Divide-and-Conquer
- • 11.1 Recurrences and the Master Theorem
- • 11.2 Integer Multiplication
- • 11.3 Matrix Multiplication
- • 11.4 The Maxima-Set Problem
- • 11.5 Exercises
Chapter 12: Dynamic Programming
- • 12.1 Matrix Chain-Products
- • 12.2 The General Technique
- • 12.3 Telescope Scheduling
- • 12.4 Game Strategies
- • 12.5 The Longest Common Subsequence Problem
- • 12.6 The 0-1 Knapsack Problem
- • 12.7 Exercises
Chapter 13: Graphs and Traversals
- • 13.1 Graph Terminology and Representations
- • 13.2 Depth-First Search
- • 13.3 Breadth-First Search
- • 13.4 Directed Graphs
- • 13.5 Biconnected Components
- • 13.6 Exercises
Chapter 14: Shortest Paths
- • 14.1 Single-Source Shortest Paths
- • 14.2 Dijkstra’s Algorithm
- • 14.3 The Bellman-Ford Algorithm
- • 14.4 Shortest Paths in Directed Acyclic Graphs
- • 14.5 All-Pairs Shortest Paths
- • 14.6 Exercises
Chapter 15: Minimum Spanning Trees
- • 15.1 Properties of Minimum Spanning Trees
- • 15.2 Kruskal’s Algorithm
- • 15.3 The Prim-Jarn´ýk Algorithm
- • 15.4 Bar°uvka’s Algorithm
- • 15.5 Exercises
Chapter 16: Network Flow and Matching
- • 16.1 Flows and Cuts
- • 16.2 Maximum Flow Algorithms
- • 16.3 Maximum Bipartite Matching
- • 16.4 Baseball Elimination
- • 16.5 Minimum-Cost Flow
- • 16.6 Exercises
Chapter 17: NP-Completeness
- • 17.1 P and NP
- • 17.2 NP-Completeness
- • 17.3 CNF-SAT and 3SAT
- • 17.4 VERTEX-COVER, CLIQUE, and SET-COVER
- • 17.5 SUBSET-SUM and KNAPSACK
- • 17.6 HAMILTONIAN-CYCLE and TSP
- • 17.7 Exercises
Chapter 18: Approximation Algorithms
- • 18.1 The Metric Traveling Salesperson Problem
- • 18.2 Approximations for Covering Problems
- • 18.3 Polynomial-Time Approximation Schemes
- • 18.4 Backtracking and Branch-and-Bound
- • 18.5 Exercises
Chapter 19: Randomized Algorithms
- • 19.1 Generating Random Permutations
- • 19.2 Stable Marriages and Coupon Collecting
- • 19.3 Minimum Cuts
- • 19.4 Finding Prime Numbers
- • 19.5 Chernoff Bounds
- • 19.6 Skip Lists
- • 19.7 Exercises
Chapter 20: B-Trees and External-Memory
- • 20.1 External Memory
- • 20.2 (2,4) Trees and B-Trees
- • 20.3 External-Memory Sorting
- • 20.4 Online Caching Algorithms
- • 20.5 Exercises
Chapter 21: Multi-Dimensional Searching
- • 21.1 Range Trees
- • 21.2 Priority Search Trees
- • 21.3 Quadtrees and k-D Trees
- • 21.4 Exercises
Chapter 22: Computational Geometry
- • 22.1 Operations on Geometric Objects
- • 22.2 Convex Hulls
- • 22.3 Segment Intersection
- • 22.4 Finding a Closest Pair of Points
- • 22.5 Exercises
Chapter 23: String Algorithms
- • 23.1 String Operations
- • 23.2 The Boyer-Moore Algorithm
- • 23.3 The Knuth-Morris-Pratt Algorithm
- • 23.4 Hash-Based Lexicon Matching
- • 23.5 Tries
- • 23.6 Exercises
Chapter 24: Cryptography
- • 24.1 Greatest Common Divisors (GCD)
- • 24.2 Modular Arithmetic
- • 24.3 Cryptographic Operations
- • 24.4 The RSA Cryptosystem
- • 24.5 The El Gamal Cryptosystem
- • 24.6 Exercises
Chapter 25: The Fast Fourier Transform
- • 25.1 Convolution
- • 25.2 Primitive Roots of Unity
- • 25.3 The Discrete Fourier Transform
- • 25.4 The Fast Fourier Transform Algorithm
- • 25.5 Exercises
Chapter 26: Linear Programming
- • 26.1 Formulating the Problem
- • 26.2 The Simplex Method
- • 26.3 Duality
- • 26.4 Applications of Linear Programming
- • 26.5 Exercises
Chapter A: UsefulMathematicalFacts
Customer Reviews
0.0
0 reviews
No reviews yet. Be the first to review this book!
Write a Review
Reviewed by GradeFocus Editorial Team
