Algorithms: Design Techniques and Analysis, 2nd Edition
- Length: 725 pages
- Edition: 2
- Language: English
- Publisher: World Scientific Pub Co Inc
- Publication Date: 2021-12-02
- ISBN-10: 9811238642
- ISBN-13: 9789811238642
- Sales Rank: #11918321 (See Top 100 Books)
Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) the solution to the formulated problem. One can solve a problem on its own using ad hoc techniques or by following techniques that have produced efficient solutions to similar problems. This required the understanding of various algorithm design techniques, how and when to use them to formulate solutions, and the context appropriate for each of them.This book presents a design thinking approach to problem solving in computing — by first using algorithmic analysis to study the specifications of the problem, before mapping the problem on to data structures, then on to the situatable algorithms. Each technique or strategy is covered in its own chapter supported by numerous examples of problems and their algorithms. The new edition includes a comprehensive chapter on parallel algorithms, and many enhancements.
Contents Preface About the Author Acknowledgments Part 1 Basic Concepts and Introduction to Algorithms Chapter 1 Basic Concepts in Algorithmic Analysis 1.1 Introduction 1.2 Historical Background 1.3 Binary Search 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 1.5 Selection Sort 1.6 Insertion Sort 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of bottom-up merge sorting 1.8 Time Complexity 1.8.1 Order of growth 1.8.2 The O-notation 1.8.3 The Ω-notation 1.8.4 The Θ-notation 1.8.5 Examples 1.8.6 Complexity classes and the o-notation 1.9 Space Complexity 1.10 Optimal Algorithms 1.11 How to Estimate the Running Time of an Algorithm 1.11.1 Counting the number of iterationsc 1.11.2 Counting the frequency of basic operations 1.11.3 Using recurrence relations 1.12 Worst Case and Average Case Analysis 1.12.1 Worst case analysis 1.12.2 Average case analysis 1.13 Amortized Analysis 1.14 Input Size and Problem Instance 1.15 Divide-and-Conquer Recurrences 1.15.1 Expanding the recurrence 1.15.2 Substitution 1.15.3 Change of variables 1.16 Practice Problems 1.17 Exercises 1.18 Bibliographic Notes Chapter 2 Data Structures 2.1 Introduction 2.2 Linked Lists 2.2.1 Stacks and queues 2.3 Graphs 2.3.1 Representation of graphs 2.3.2 Planar graphs 2.4 Trees 2.5 Rooted Trees 2.5.1 Tree traversals 2.6 Binary Trees 2.6.1 Some quantitative aspects of binary trees 2.6.2 Binary search trees 2.7 Practice Problems 2.8 Exercises 2.9 Bibliographic Notes Chapter 3 Heaps and the Disjoint Sets Data Structures 3.1 Introduction 3.2 Heaps 3.2.1 Operations on heaps 3.2.1.1 Sift-up 3.2.1.2 Sift-down 3.2.1.3 Insert 3.2.1.4 Delete 3.2.1.5 Delete-max 3.2.2 Creating a heap 3.2.3 Heapsort 3.2.4 Min and max heaps 3.3 Disjoint Sets Data Structures 3.3.1 The union by rank heuristic 3.3.2 Path compression 3.3.3 The union-find algorithms 3.3.4 Analysis of the union-find algorithms 3.4 Practice Problems 3.5 Exercises 3.6 Bibliographic Notes Part 2 Techniques Based on Recursion Chapter 4 Induction 4.1 Introduction 4.2 Finding the Majority Element 4.3 Integer Exponentiation 4.4 Evaluating Polynomials (Horner’s Rule) 4.5 Radix Sort 4.6 Generating Subsets of a Set 4.6.1 The first algorithm 4.6.2 The second algorithm 4.6.3 Iterative algorithm 4.7 Generating Permutations 4.7.1 The first algorithm 4.7.2 The second algorithm 4.7.3 Iterative algorithm 4.8 Practice Problems 4.9 Exercises 4.10 Bibliographic Notes Chapter 5 Divide and Conquer 5.1 Introduction 5.2 Binary Search 5.2.1 Analysis of the recursive binary search algorithm 5.3 Mergesort 5.3.1 How the algorithm works 5.3.2 Analysis of the mergesort algorithm 5.4 The Divide-and-Conquer Paradigm 5.5 Selection: Finding the Median and the kth Smallest Element 5.5.1 Analysis of the selection algorithm 5.6 Quicksort 5.6.1 A partitioning algorithm 5.6.2 The sorting algorithm 5.6.3 Analysis of the quicksort algorithm 5.6.3.1 The worst case behavior 5.6.3.2 The average case behavior 5.6.4 Comparison of sorting algorithms 5.7 Quickselect 5.8 Multiselection 5.9 Multiplication of Large Integers 5.10 Matrix Multiplication 5.10.1 The traditional algorithm 5.10.2 Strassen’s algorithm 5.10.2.1 Time complexity 5.10.3 Comparison of the two algorithms 5.11 The Closest Pair Problem 5.11.1 Time complexity 5.12 A Dominance Problem 5.13 Practice Problems 5.14 Exercises 5.15 Bibliographic Notes Chapter 6 Dynamic Programming 6.1 Introduction 6.2 The Longest Common Subsequence Problem 6.2.1 The algorithm 6.3 Matrix Chain Multiplication 6.3.1 The dynamic programming algorithm 6.4 The Dynamic Programming Paradigm 6.5 The All-Pairs Shortest Path Problem 6.5.1 The algorithm 6.6 The Knapsack Problem 6.6.1 The algorithm 6.7 Practice Problems 6.8 Exercises 6.9 Bibliographic Notes Part 3 First-Cut Techniques Chapter 7 The Greedy Approach 7.1 Introduction 7.2 The Shortest Path Problem 7.2.1 Implementation of the shortest path algorithm 7.2.2 Correctness 7.2.3 Time complexity 7.2.4 Improving the time bound 7.3 Minimum Cost Spanning Trees (Kruskal’s Algorithm) 7.3.1 Implementation of Kruskal’s algorithm 7.3.2 Correctness 7.3.3 Time complexity 7.4 Minimum Cost Spanning Trees (Prim’s Algorithm) 7.4.1 Implementation of Prim’s algorithm 7.4.2 Correctness 7.4.3 Time complexity 7.4.4 Improving the time bound 7.5 File Compression 7.5.1 The algorithm 7.5.2 Time complexity 7.6 Practice Problems 7.7 Exercises 7.8 Bibliographic Notes Chapter 8 Graph Traversal 8.1 Introduction 8.2 Depth-First Search 8.2.1 The case of undirected graphs 8.2.2 The case of directed graphs 8.2.3 Time complexity of depth-first search 8.3 Applications of Depth-First Search 8.3.1 Graph acyclicity 8.3.2 Topological sorting 8.3.3 Finding articulation points in a graph 8.3.4 Strongly connected components 8.4 Breadth-First Search 8.4.1 Time complexity 8.5 Applications of Breadth-First Search 8.6 Practice Problems 8.7 Exercises 8.8 Bibliographic Notes Part 4 Complexity of Problems Chapter 9 NP-Complete Problems 9.1 Introduction 9.2 The Class P 9.3 The Class NP 9.4 NP-Complete Problems 9.4.1 The satisfiability problem 9.4.2 Proving NP-completeness 9.4.3 3-Satisfiability 9.4.4 Vertex cover, independent set and clique problems 9.4.5 More NP-complete problems 9.5 The Class co-NP 9.6 The Relationships between the Three Classes 9.7 Practice Problems 9.8 Exercises 9.9 Bibliographic Notes Chapter 10 Introduction to Computational Complexity 10.1 Introduction 10.2 Model of Computation: The Turing Machine 10.3 k-Tape Turing Machines and Time Complexity 10.4 Off-line Turing Machines and Space Complexity 10.5 Tape Compression and Linear Speed-up 10.6 Relationships between Complexity Classes 10.6.1 Space and time hierarchy theorems 10.6.2 Padding arguments 10.7 Reductions 10.8 Completeness 10.8.1 NLOGSPACE-complete problems 10.8.2 PSPACE-complete problems 10.8.3 P-complete problems 10.8.4 Some conclusions of completeness 10.9 The Polynomial Time Hierarchy 10.10 Practice Problems 10.11 Exercises 10.12 Bibliographic Notes Chapter 11 Lower Bounds 11.1 Introduction 11.2 Trivial Lower Bounds 11.3 The Decision Tree Model 11.3.1 The search problem 11.3.2 The sorting problem 11.3.3 Finding the maximum 11.3.4 Finding the largest and second largest elements 11.3.4.1 Lower bound 11.3.4.2 Optimal algorithm 11.4 The Algebraic Decision Tree Model 11.4.1 The element uniqueness problem 11.4.2 The set equality problem 11.4.3 The set inclusion problem 11.4.4 The set disjointness problem 11.5 Linear Time Reductions 11.5.1 The convex hull problem 11.5.2 The closest pair problem 11.5.3 The Euclidean minimum spanning tree problem 11.5.4 The diameter of a point set 11.6 Practice Problems 11.7 Exercises 11.8 Bibliographic Notes Part 5 Coping with Hardness Chapter 12 Backtracking 12.1 Introduction 12.2 The 3-Coloring Problem 12.2.1 The algorithm 12.3 The 8-Queens Problem 12.3.1 The algorithm 12.4 The General Backtracking Method 12.5 Branch and Bound 12.6 Practice Problems 12.7 Exercises 12.8 Bibliographic Notes Chapter 13 Randomized Algorithms 13.1 Introduction 13.2 Las Vegas and Monte Carlo Algorithms 13.3 Two Simple Examples 13.3.1 A Monte Carlo algorithm 13.3.2 A Las Vegas algorithm 13.4 Randomized Quicksort 13.4.1 Expected running time of randomized quicksort 13.5 Randomized Quickselect 13.5.1 Expected running time of randomized quickselect 13.5.2 The dice problem 13.5.3 Application of the dice problem: Quickselect 13.6 Occupancy Problems 13.6.1 Number of balls in each bin 13.6.2 Number of empty bins 13.6.3 Balls falling into the same bin 13.6.4 Filling all bins 13.7 Tail Bounds 13.7.1 Markov inequality 13.7.2 Chebyshev inequality 13.7.3 Chernoff bounds 13.7.3.1 Lower tail 13.7.3.2 Upper tail 13.8 Application of Chernoff Bounds: Multiselection 13.8.1 Analysis of the algorithm 13.9 Random Sampling 13.10 The Min-Cut Problem 13.11 Testing String Equality 13.12 Pattern Matching 13.13 Primality Testing 13.14 Practice Problems 13.15 Exercises 13.16 Bibliographic Notes Chapter 14 Approximation Algorithms 14.1 Introduction 14.2 Basic Definitions 14.3 Difference Bounds 14.3.1 Planar graph coloring 14.3.2 Hardness result: The knapsack problem 14.4 Relative Performance Bounds 14.4.1 The bin packing problem 14.4.2 The Euclidean traveling salesman problem 14.4.3 The vertex cover problem 14.4.4 Hardness result: The traveling salesman problem 14.5 Polynomial Approximation Schemes 14.5.1 The knapsack problem 14.6 Fully Polynomial Approximation Schemes 14.6.1 The subset-sum problem 14.7 Practice Problems 14.8 Exercises 14.9 Bibliographic Notes Part 6 Iterative Improvement for Domain-Specific Problems Chapter 15 Network Flow 15.1 Introduction 15.2 Preliminaries 15.3 The Ford–Fulkerson Method 15.4 Maximum Capacity Augmentation 15.5 Shortest Path Augmentation 15.6 Dinic’s Algorithm 15.7 The MPM Algorithm 15.8 Practice Problems 15.9 Exercises 15.10 Bibliographic Notes Chapter 16 Matching 16.1 Introduction 16.2 Preliminaries 16.3 The Network Flow Method for Bipartite Graphs 16.4 The Hungarian Tree Method for Bipartite Graphs 16.5 Maximum Matching in General Graphs 16.6 An O(n2.5) Algorithm for Bipartite Graphs 16.7 Practice Problems 16.8 Exercises 16.9 Bibliographic Notes Part 7 Techniques in Computational Geometry Chapter 17 Geometric Sweeping 17.1 Introduction 17.2 A Simple Example: Computing the Maximal Points of a Point Set 17.3 Geometric Preliminaries 17.4 Computing the Intersections of Line Segments 17.5 The Convex Hull Problem 17.6 Computing the Diameter of a Set of Points 17.7 Practice Problems 17.8 Exercises 17.9 Bibliographic Notes Chapter 18 Voronoi Diagrams 18.1 Introduction 18.2 Nearest-Point Voronoi Diagram 18.2.1 Delaunay triangulation 18.2.2 Construction of the Voronoi diagram 18.3 Applications of the Voronoi Diagram 18.3.1 Computing the convex hull 18.3.2 All nearest neighbors 18.3.3 The Euclidean minimum spanning tree 18.4 Farthest-Point Voronoi Diagram 18.4.1 Construction of the farthest-point Voronoi diagram 18.5 Applications of the Farthest-Point Voronoi Diagram 18.5.1 All farthest neighbors 18.5.2 Smallest enclosing circle 18.6 Practice Problems 18.7 Exercises 18.8 Bibliographic Notes Part 8 Techniques in Parallel Algorithms Chapter 19 Parallel Algorithms 19.1 Introduction 19.1.1 Classifications of parallel architectures 19.2 Shared-Memory Computers (PRAM) 19.2.1 The balanced tree method 19.2.2 Brent theorem 19.2.3 Parallel prefix 19.2.3.1 Array packing 19.2.3.2 Parallel quicksort 19.2.4 Parallel search 19.2.5 Pointer jumping 19.2.6 Merging by ranking 19.2.6.1 Computing ranks 19.2.6.2 Merging 19.2.6.3 Parallel bottom-up merge sorting 19.2.7 The zero-one principle 19.2.8 Odd–even merging 19.2.9 Bitonic merging and sorting 19.2.9.1 Bitonic sorting 19.2.10 Pipelined merge sort 19.2.10.1 The algorithm 19.2.10.2 Maintaining ranks 19.2.10.3 Analysis of the algorithm 19.2.11 Selection 19.2.12 Multiselection 19.2.13 Matrix multiplication 19.2.14 Transitive closure 19.2.15 Shortest paths 19.2.16 Computing the convex hull of a set of points 19.3 Interconnection-Network Computers 19.4 The Hypercube 19.4.1 The butterfly 19.4.2 Embeddings of the hypercube 19.4.2.1 Gray codes 19.4.2.2 Embedding of a linear array into the hypercube 19.4.2.3 Embedding of a mesh into the hypercube 19.4.2.4 Embedding of a binary tree into the hypercube 19.4.3 Broadcasting on the hypercube 19.4.4 Permutation routing in the hypercube 19.4.4.1 The greedy algorithm 19.4.4.2 The randomized algorithm 19.4.5 Permutation routing in the butterfly 19.4.6 Computing parallel prefix on the hypercube 19.4.7 Hyperquicksort 19.4.8 Selection on the hypercube 19.4.9 Multiselection on the hypercube 19.4.10 Computing parallel prefix on the butterfly 19.5 The Linear Array and the Mesh 19.5.1 Broadcasting in the linear array and the mesh 19.5.2 Computing parallel prefix on the mesh 19.5.3 Odd–even transposition sort 19.5.4 Shearsort 19.5.5 Odd–even merging and sorting on the mesh 19.5.6 Computing the convex hull of a set of points on the mesh 19.5.6.1 The first algorithm 19.5.6.2 The second algorithm 19.5.7 Three-dimensional mesh 19.5.7.1 Sorting on three-dimensional meshes 19.5.8 Fast Fourier transform 19.5.8.1 Implementation on the butterfly 19.5.8.2 Iterative FFT on the butterfly 19.5.8.3 The inverse Fourier transform 19.5.8.4 Applications of FFT 19.5.8.5 Product of polynomials 19.5.8.6 Computing the convolution of two vectors 19.6 Systolic Computation 19.6.1 An on-chip bubble sorter 19.7 Practice Problems 19.8 Exercises 19.9 Bibliographic Notes 19.10 Solutions Appendix A. Mathematical Preliminaries A.1 Sets, Relations and Functions A.1.1 Sets A.1.2 Relations A.1.2.1 Equivalence relations A.1.3 Functions A.2 Proof Methods A.2.1 Notation A.2.2 Direct proof A.2.3 Indirect proof A.2.4 Proof by contradiction A.2.5 Proof by counterexample A.2.6 Mathematical induction A.3 Logarithms A.4 Floor and Ceiling Functions A.5 Factorial and Binomial Coefficients A.5.1 Factorials A.5.2 Binomial coefficients A.6 The Pigeonhole Principle A.7 Summations A.7.1 Approximation of summations by integration A.8 Recurrence Relations A.8.1 Solution of linear homogeneous recurrences A.8.2 Solution of inhomogeneous recurrences A.9 Divide-and-Conquer Recurrences A.10 Exercises Appendix B. Introduction to Discrete Probability B.1 Definitions B.2 Conditional Probability and Independence B.2.1 Multiplication rule for conditional probability B.3 Random Variables and Expectation B.4 Discrete Probability Distributions B.4.1 Uniform distribution B.4.2 Bernoulli distribution B.4.3 Binomial distribution B.4.4 Geometric distribution B.4.5 Poisson distribution Bibliography Index
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.