Design and analysis of algorithms can be a difficult subject for students due to its sometimes-abstract nature and its use of a wide variety of mathematical tools. Here the author, an experienced and successful textbook writer, makes the subject as straightforward as possible in an up-to-date textbook incorporating various new developments appropriate for an introductory course.
This text presents the main techniques of algorithm design, namely, divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and backtracking. Graph algorithms are studied in detail, and a careful treatment of the theory of NP-completeness is presented.
In addition, the text includes useful introductory material on mathematical background including order notation, algorithm analysis and reductions, and basic data structures. This will serve as a useful review and reference for students who have covered this material in a previous course.
Features:
After reading and understanding the material in this book, students will be able to apply the basic design principles to various real-world problems that they may encounter in their future professional careers.
Here is a summary of the material covered in the book:
• Chapter 1 presents various mathematical topics, such as order notation, relevant mathematical formulae, probability theory and random variables.
• Chapter 2 examines various algorithm analysis techniques, including loop analysis. We also introduce reductions, which are revisited again in Chapter 9. Finally, we provide some examples of exact analysis in this chapter.
• Chapter 3 discusses various basic concepts in data structures, including stacks, queues, priority queues, binary search trees and hash tables.
• Chapter 4 treats divide-and-conquer algorithms. This chapter also contains a fairly detailed discussion of recurrence relations.
• Chapter 5 is a presentation of various greedy algorithms.
• Chapter 6 covers dynamic programming and memoization.
• Chapter 7 describes various graph algorithms, including breadth-first and depth-first search, minimum spanning trees and shortest path algorithms.
• The topic of Chapter 8 is backtracking algorithms, including pruning techniques and branch-and-bound. This is a topic that is not often found in textbooks on the design and analysis of algorithms.
• Chapter 9 presents the basic theory of NP-completeness, including the complexity classes P and NP, and NP-hard problems. Approximation algorithms are introduced and we also give a brief treatment of undecidability.
There are many textbooks on algorithms that contain more than 1000 pages of material. I have deliberately written a shorter book in which I have attempted to treat the essential concepts of the subject, by choosing a representative sample of useful algorithms to illustrate the most important design techniques. I have been careful to provide detailed pseudocode descriptions of the algorithms along with illustrative algorithms. Proofs of correctness of algorithms are also included when it is appropriate to do so. Finally, I have tried to present all the material in the book with a suitable amount of mathematical rigor.
Author(s): Douglas R. Stinson
Publisher: CRC Press
Year: 2023
Language: English
Pages: 445
Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
Preface
1. Introduction and Mathematical Background
1.1. Algorithms and Programs
1.1.1. Analysis of Algorithms
1.1.2. Design of Algorithms
1.2. Definitions and Terminology
1.2.1. Problems
1.2.2. Running Time and Complexity
1.3. Order Notation
1.3.1. Techniques for Order Notation
1.3.2. Relationships between Order Notations
1.3.3. Algebra of Order Notations
1.3.4. Common Growth Rates
1.4. Mathematical Formulae
1.4.1. Sequences
1.4.2. Logarithm Formulae
1.4.3. Miscellaneous Formulae
1.4.4. Equivalence Relations
1.5. Probability Theory and Random Variables
1.6. Notes and References
Exercises
2. Algorithm Analysis and Reductions
2.1. Loop Analysis Techniques
2.1.1. Elementary Operations
2.1.2. Examples of Loop Analysis
2.2. Algorithms for the 3SUM Problem
2.2.1. An Obvious Algorithm
2.2.2. An Improvement
2.2.3. A Further Improvement
2.3. Reductions
2.3.1. The Target 3SUM Problem
2.3.2. Complexity of a Reduction
2.3.3. Many-one Reductions
2.3.4. The Three Array 3SUM Problem
2.4. Exact Analysis
2.4.1. Maximum
2.4.2. Maximum and Minimum
2.4.3. Insertion Sort
2.5. Notes and References
Exercises
3. Data Structures
3.1. Abstract Data Types and Data Structures
3.2. Arrays, Linked Lists and Sets
3.2.1. Sets and Bit Strings
3.3. Stacks and Queues
3.3.1. Stacks
3.3.2. Resizing and Amortized Analysis
3.3.3. Queues
3.4. Priority Queues and Heaps
3.4.1. Heaps
3.4.2. Insertion into a Heap
3.4.3. Deleting the Minimum Element from a Heap
3.4.4. Constructing a Heap
3.4.5. HeapSort
3.5. Binary Search Trees
3.6. Hash Tables
3.6.1. Chaining
3.6.2. Open Addressing
3.7. Notes and References
Exercises
4. Divide-and-Conquer Algorithms
4.1. Recurrence Relations
4.1.1. Guess-and-check Method
4.1.2. Linear Recurrence Relations
4.1.3. Recursion Tree Method
4.2. The Master Theorem
4.2.1. Another Proof of the Master Theorem
4.2.2. A General Version
4.3. Divide-and-Conquer Design Strategy
4.3.1. Merge Sort
4.4. Divide-and-Conquer Recurrence Relations
4.4.1. Sloppy and Exact Recurrence Relations
4.4.2. The Exact Recurrence for MergeSort
4.5. Binary Search
4.6. Non-dominated Points
4.7. Stock Profits
4.8. Closest Pair
4.8.1. An Improved Algorithm
4.9. Multiprecision Multiplication
4.9.1. The Karatsuba Multiplication Algorithm
4.10. Modular Exponentiation
4.11. Matrix Multiplication
4.11.1. Strassen Matrix Multiplication
4.12. QuickSort
4.12.1. Complexity Analysis
4.13. Selection and Median
4.13.1. QuickSelect
4.13.2. A Linear-time Selection Algorithm
4.14. Notes and References
Exercises
5. Greedy Algorithms
5.1. Optimization Problems
5.2. Greedy Design Strategy
5.3. Interval Selection
5.4. Interval Coloring
5.5. Wireless Access Points
5.6. A House Construction Problem
5.7. Knapsack
5.8. Coin Changing
5.9. Multiprocessor Scheduling
5.9.1. Relative Error of the Greedy Algorithm
5.10. Stable Matching
5.10.1. Correctness
5.10.2. Complexity
5.10.3. Uniqueness
5.11. Notes and References
Exercises
6. Dynamic Programming Algorithms
6.1. Fibonacci Numbers
6.2. Design Strategy
6.3. Treasure Hunt
6.4. 0-1 Knapsack
6.5. Rod Cutting
6.6. Coin Changing
6.7. Longest Common Subsequence
6.8. Minimum Length Triangulation
6.9. Memoization
6.9.1. Fibonacci Numbers
6.9.2. 0-1 Knapsack
6.9.3. Comparison
6.10. Notes and References
Exercises
7. Graph Algorithms
7.1. Graphs
7.1.1. Definitions
7.1.2. Data Structures for Graphs
7.2. Breadth-first Search
7.2.1. Shortest Paths
7.2.2. Bipartite Graphs
7.3. Directed Graphs
7.4. Depth-first Search
7.4.1. Topological Ordering
7.5. Strongly Connected Components
7.5.1. Connectivity and Strong Connectivity
7.5.2. Sharir’s Algorithm
7.6. Eulerian Circuits
7.7. Minimum Spanning Trees
7.7.1. Kruskal’s Algorithm
7.7.2. Prim’s Algorithm
7.7.3. A General Algorithm
7.8. Single Source Shortest Paths
7.8.1. Dijkstra’s Algorithm
7.8.2. Shortest Paths in Directed Acyclic Graphs
7.8.3. Bellman-Ford Algorithm
7.9. All-Pairs Shortest Paths
7.9.1. A Dynamic Programming Approach
7.9.2. Successive Doubling
7.9.3. Floyd-Warshall Algorithm
7.10. Notes and References
Exercises
8. Backtracking Algorithms
8.1. Introduction
8.1.1. Permutations
8.1.2. The n-queens Problem
8.2. Generating All Cliques
8.3. Sudoku
8.4. Pruning and Bounding Functions
8.4.1. Bounding Functions
8.4.2. The Max Clique Problem
8.5. 0-1 Knapsack Problem
8.5.1. Bounding Function
8.6. Traveling Salesperson Problem
8.6.1. Bounding Function
8.7. Branch-and-bound
8.8. Notes and References
Exercises
9. Intractability and Undecidability
9.1. Decision Problems and the Complexity Class P
9.2. Polynomial-time Turing Reductions
9.3. The Complexity Class NP
9.4. Polynomial Transformations
9.4.1. Clique P Vertex-Cover
9.4.2. Properties of Polynomial Transformations
9.5. NP-completeness
9.5.1. Satisfiability and the Cook-Levin Theorem
9.6. Proving Problems NP-complete
9.6.1. More Satisfiability Problems
9.6.2. 3-CNF-Satisfiability
9.6.3. Clique
9.6.4. Vertex Cover
9.6.5. 0-1 Knapsack-Dec
9.6.6. Partition
9.6.7. Multiprocessor Scheduling-Dec
9.6.8. Hamiltonian Cycle
9.6.9. TSP-Dec
9.6.10. Summary of Polynomial Transformations
9.7. NP-hard Problems
9.8. Approximation Algorithms
9.8.1. Vertex Cover
9.8.2. Metric TSP
9.8.3. Maximum Satisfiability
9.9. Undecidability
9.10. The Complexity Class EXPTIME
9.11. Notes and References
Exercises
Bibliography
Index
