Douglas R Stinson
Techniques for Designing and Analyzing Algorithms
Douglas R Stinson
Techniques for Designing and Analyzing Algorithms
- Gebundenes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
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.
Andere Kunden interessierten sich auch für
- Soft Computing Techniques in Engineering, Health, Mathematical and Social Sciences148,99 €
- Ronald GoldmanAn Integrated Introduction to Computer Graphics and Geometric Modeling148,99 €
- T. SridharDesigning Embedded Communications Software74,99 €
- Learning and Intelligent Optimization: Designing, Implementing and Analyzing Effective Heuristics37,99 €
- Leonardo Azevedo ScarduaApplied Evolutionary Algorithms for Engineers Using Python212,99 €
- Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics53,49 €
- Thomas JansenAnalyzing Evolutionary Algorithms37,99 €
-
-
-
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.
Produktdetails
- Produktdetails
- Verlag: Taylor & Francis Ltd (Sales)
- Seitenzahl: 444
- Erscheinungstermin: 6. August 2021
- Englisch
- Abmessung: 254mm x 178mm x 25mm
- Gewicht: 984g
- ISBN-13: 9780367228897
- ISBN-10: 0367228890
- Artikelnr.: 62234081
- Verlag: Taylor & Francis Ltd (Sales)
- Seitenzahl: 444
- Erscheinungstermin: 6. August 2021
- Englisch
- Abmessung: 254mm x 178mm x 25mm
- Gewicht: 984g
- ISBN-13: 9780367228897
- ISBN-10: 0367228890
- Artikelnr.: 62234081
Douglas R. Stinson obtained his PhD in Combinatorics and Optimization from the University of Waterloo in 1981. He held academic positions at the University of Manitoba and the University of Nebraska-Lincoln before returning to Waterloo in 1998. In 2019, Dr. Stinson retired from the David R. Cheriton School of Computer Science at the University of Waterloo and he now holds the title Professor Emeritus. His research interests include cryptography and computer security, combinatorics and coding theory, and applications of discrete mathematics in computer science. He was elected as a Fellow of the Royal Society of Canada in 2011. He has published almost 400 papers and several books, including Cryptography: Theory and Practice, Fourth Edition, also published by CRC Press.
1. Introduction and Mathematical Background. 1.1. Algorithms and Programs.
1.2. Definitions and Terminology. 1.3. Order Notation. 1.4. Mathematical
Formulae. 1.5. Probability Theory and Random Variables. 1.6. Notes and
References. Exercises. 2. Algorithm Analysis and Reductions. 2.1. Loop
Analysis Techniques. 2.2. Algorithms for the 3SUM Problem. 2.3. Reductions.
2.4. Exact Analysis. 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.3. Stacks and Queues. 3.4. Priority Queues and
Heaps. 3.6. Hash Tables. 3.7. Notes and References. Exercises. 4.
Divide-and-Conquer Algorithms. 4.1. Recurrence Relations. 4.2. The Master
Theorem. 4.3. Divide-and-Conquer Design Strategy. 4.4. Divide-and-Conquer
Recurrence Relations. 4.5. Binary Search. 4.6. Non-dominated Points. 4.7.
Stock Profits. 4.8. Closest Pair. 4.9. Multiprecision Multiplication. 4.10.
Modular Exponentiation. 4.11. Matrix Multiplication. 4.12. QuickSort. 4.13.
Selection and Median. 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.10. Stable Matching. 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.10. Notes and References.
Exercises. 7. Graph Algorithms. 7.1. Graphs. 7.2. Breadth-first Search.
7.3. Directed Graphs. 7.4. Depth-first Search. 7.5. Strongly Connected
Components. 7.6. Eulerian Circuits. 7.7. Minimum Spanning Trees. 7.8.
Single Source Shortest Paths. 7.9. All-Pairs Shortest Paths. 7.10. Notes
and References. Exercises. 8. Backtracking Algorithms. 8.1. Introduction.
8.2. Generating all Cliques. 8.3. Sudoku. 8.4. Pruning and Bounding
Functions. 8.5. 0-1 Knapsack Problem. 8.6. Traveling Salesperson Problem.
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.5. NP-completeness.
9.6. Proving Problems NP-complete. 9.7. NP-hard Problems. 9.8.
Approximation Algorithms. 9.9. Undecidability. 9.10. The Complexity Class
EXPTIME. 9.11. Notes and References. Exercises. Bibliography. Index.
1.2. Definitions and Terminology. 1.3. Order Notation. 1.4. Mathematical
Formulae. 1.5. Probability Theory and Random Variables. 1.6. Notes and
References. Exercises. 2. Algorithm Analysis and Reductions. 2.1. Loop
Analysis Techniques. 2.2. Algorithms for the 3SUM Problem. 2.3. Reductions.
2.4. Exact Analysis. 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.3. Stacks and Queues. 3.4. Priority Queues and
Heaps. 3.6. Hash Tables. 3.7. Notes and References. Exercises. 4.
Divide-and-Conquer Algorithms. 4.1. Recurrence Relations. 4.2. The Master
Theorem. 4.3. Divide-and-Conquer Design Strategy. 4.4. Divide-and-Conquer
Recurrence Relations. 4.5. Binary Search. 4.6. Non-dominated Points. 4.7.
Stock Profits. 4.8. Closest Pair. 4.9. Multiprecision Multiplication. 4.10.
Modular Exponentiation. 4.11. Matrix Multiplication. 4.12. QuickSort. 4.13.
Selection and Median. 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.10. Stable Matching. 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.10. Notes and References.
Exercises. 7. Graph Algorithms. 7.1. Graphs. 7.2. Breadth-first Search.
7.3. Directed Graphs. 7.4. Depth-first Search. 7.5. Strongly Connected
Components. 7.6. Eulerian Circuits. 7.7. Minimum Spanning Trees. 7.8.
Single Source Shortest Paths. 7.9. All-Pairs Shortest Paths. 7.10. Notes
and References. Exercises. 8. Backtracking Algorithms. 8.1. Introduction.
8.2. Generating all Cliques. 8.3. Sudoku. 8.4. Pruning and Bounding
Functions. 8.5. 0-1 Knapsack Problem. 8.6. Traveling Salesperson Problem.
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.5. NP-completeness.
9.6. Proving Problems NP-complete. 9.7. NP-hard Problems. 9.8.
Approximation Algorithms. 9.9. Undecidability. 9.10. The Complexity Class
EXPTIME. 9.11. Notes and References. Exercises. Bibliography. Index.
1. Introduction and Mathematical Background. 1.1. Algorithms and Programs.
1.2. Definitions and Terminology. 1.3. Order Notation. 1.4. Mathematical
Formulae. 1.5. Probability Theory and Random Variables. 1.6. Notes and
References. Exercises. 2. Algorithm Analysis and Reductions. 2.1. Loop
Analysis Techniques. 2.2. Algorithms for the 3SUM Problem. 2.3. Reductions.
2.4. Exact Analysis. 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.3. Stacks and Queues. 3.4. Priority Queues and
Heaps. 3.6. Hash Tables. 3.7. Notes and References. Exercises. 4.
Divide-and-Conquer Algorithms. 4.1. Recurrence Relations. 4.2. The Master
Theorem. 4.3. Divide-and-Conquer Design Strategy. 4.4. Divide-and-Conquer
Recurrence Relations. 4.5. Binary Search. 4.6. Non-dominated Points. 4.7.
Stock Profits. 4.8. Closest Pair. 4.9. Multiprecision Multiplication. 4.10.
Modular Exponentiation. 4.11. Matrix Multiplication. 4.12. QuickSort. 4.13.
Selection and Median. 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.10. Stable Matching. 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.10. Notes and References.
Exercises. 7. Graph Algorithms. 7.1. Graphs. 7.2. Breadth-first Search.
7.3. Directed Graphs. 7.4. Depth-first Search. 7.5. Strongly Connected
Components. 7.6. Eulerian Circuits. 7.7. Minimum Spanning Trees. 7.8.
Single Source Shortest Paths. 7.9. All-Pairs Shortest Paths. 7.10. Notes
and References. Exercises. 8. Backtracking Algorithms. 8.1. Introduction.
8.2. Generating all Cliques. 8.3. Sudoku. 8.4. Pruning and Bounding
Functions. 8.5. 0-1 Knapsack Problem. 8.6. Traveling Salesperson Problem.
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.5. NP-completeness.
9.6. Proving Problems NP-complete. 9.7. NP-hard Problems. 9.8.
Approximation Algorithms. 9.9. Undecidability. 9.10. The Complexity Class
EXPTIME. 9.11. Notes and References. Exercises. Bibliography. Index.
1.2. Definitions and Terminology. 1.3. Order Notation. 1.4. Mathematical
Formulae. 1.5. Probability Theory and Random Variables. 1.6. Notes and
References. Exercises. 2. Algorithm Analysis and Reductions. 2.1. Loop
Analysis Techniques. 2.2. Algorithms for the 3SUM Problem. 2.3. Reductions.
2.4. Exact Analysis. 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.3. Stacks and Queues. 3.4. Priority Queues and
Heaps. 3.6. Hash Tables. 3.7. Notes and References. Exercises. 4.
Divide-and-Conquer Algorithms. 4.1. Recurrence Relations. 4.2. The Master
Theorem. 4.3. Divide-and-Conquer Design Strategy. 4.4. Divide-and-Conquer
Recurrence Relations. 4.5. Binary Search. 4.6. Non-dominated Points. 4.7.
Stock Profits. 4.8. Closest Pair. 4.9. Multiprecision Multiplication. 4.10.
Modular Exponentiation. 4.11. Matrix Multiplication. 4.12. QuickSort. 4.13.
Selection and Median. 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.10. Stable Matching. 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.10. Notes and References.
Exercises. 7. Graph Algorithms. 7.1. Graphs. 7.2. Breadth-first Search.
7.3. Directed Graphs. 7.4. Depth-first Search. 7.5. Strongly Connected
Components. 7.6. Eulerian Circuits. 7.7. Minimum Spanning Trees. 7.8.
Single Source Shortest Paths. 7.9. All-Pairs Shortest Paths. 7.10. Notes
and References. Exercises. 8. Backtracking Algorithms. 8.1. Introduction.
8.2. Generating all Cliques. 8.3. Sudoku. 8.4. Pruning and Bounding
Functions. 8.5. 0-1 Knapsack Problem. 8.6. Traveling Salesperson Problem.
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.5. NP-completeness.
9.6. Proving Problems NP-complete. 9.7. NP-hard Problems. 9.8.
Approximation Algorithms. 9.9. Undecidability. 9.10. The Complexity Class
EXPTIME. 9.11. Notes and References. Exercises. Bibliography. Index.