Book description
This second edition of Design and Analysis of Algorithms continues to provide a comprehensive exposure to the subject with new inputs on contemporary topics in algorithm design and algorithm analysis. Spread over 21 chapters aptly complemented by five appendices, the book interprets core concepts with ease in logical succession to the student's benefit.
Table of contents
- Cover
- Title Page
- Brief Contents
- Contents
- Dedication
- Preface
- Preface to the First Edition
- Timeline of Algorithms
-
Part 1: Algorithm Design
- Chapter 1: Introduction
-
Chapter 2: Problem Solving with a Computer
- 2.1 Introduction
-
2.2 Solving a Problem with a Computer
- 2.2.1 Statement of the Problem or Problem Definition
- 2.2.2 Development of a Model
- 2.2.3 Design of the Algorithm
- 2.2.4 Checking the Correctness of the Algorithm
- 2.2.5 Implementation in Some Programming Language
- 2.2.6 Analyze and Study the Complexity of the Algorithm
- 2.2.7 Program Testing—Debugging and Profiling
- 2.2.8 Documentation Preparation
- 2.3 Some More Examples
- 2.4 Problem Solving in General
- Summary
- Key Terms
- Exercises
- Web Resources
- Chapter 3: Top-Down Design
- Chapter 4: Iterative Algorithm Design Issues
- Chapter 5: Computation Models and Design by Refinement
- Chapter 6: Proof Rules—Basics
- Chapter 7: Design by Proof Rules
- Chapter 8: Design Using Recursion
- Chapter 9: Abstract Algorithms 1—Divide-and-Conquer
-
Chapter 10: Abstract Algorithms 2—Greedy Methods
- 10.1 Introduction
- 10.2 Example—Knapsack Problem
- 10.3 Job Sequencing with Deadlines
-
10.4 Example—Minimum Spanning Trees
- 10.4.1 Prim’s Algorithm
- 10.4.2 Kruskal’s Algorithm
- 10.4.3 1st Version—Kruskal.c
- 10.4.4 Union-Find Data-structure
- 10.4.5 Tree-based Disjoint Sets and the Quick-Union Algorithm
- 10.4.6 Implementing Quick-Union with an Array
- 10.4.7 Complexity Analysis of Quick-Union
- 10.4.8 Using Union-Find in Kruskal Algorithm
- 10.4.9 Matroids
- 10.4.10 Correctness of Kruskal’s Algorithm
- 10.5 Example [Shortest Path]
- 10.6 Optimal Merge Patterns
- Summary
- Key Terms
- Exercises
- Web Resources
-
Chapter 11: Abstract Algorithms 3—Dynamic Programming
- 11.1 Introduction
- 11.2 Rod Cutting Problem
- 11.3 Example—Multistage Graphs
- 11.4 Example—Traveling Salesman (TS)
- 11.5 Example—Matrix Multiplication
- 11.6 Example—Longest Common Sub-sequence (LCS)
- 11.7 Example—Optimal Polygon Triangulation
- 11.8 Single Source Shortest Paths
- 11.9 Maximum Flow Problems
- 11.10 Conclusion
- Summary
- Key Terms
- Exercises
- Web Resources
-
Chapter 12: Abstract Algorithms 4—Backtracking, Branch and Bound
- 12.1 Combinatorial Search
- 12.2 Search and Traversal
- 12.3 The Backtracking Strategy
- 12.4 Backtracking Framework
- 12.5 Some Typical State Spaces
-
12.6 Branch-and-Bound Algorithms
- 12.6.1 Example: Shortest Path
- 12.6.2 Branch-and-Bound Based on Partial Solutions
- 12.6.3 Example: 16-Puzzle and 8-Puzzle
- 12.6.4 Example: Scale Balancing
- 12.6.5 From DFS to Branch-and-Bound
- 12.6.6 Example: 0/1 Knapsack Problem
- 12.6.7 Example: TSP
- 12.6.8 Example: Integer Linear Programming
- 12.6.9 Example: TSP—On Bounding Function
- 12.6.10 Example: Locating Warehouses
- 12.6.11 Limitations of Branch and Bound
- 12.6.12 Branch and Cut
- Summary
- Key Terms
- Exercises
- Web Resources
-
Chapter 13: Natural Algorithms—GA, SA, ANN, TS
- 13.1 Introduction
- 13.2 Evolutionary Algorithms and Evolutionary Computing
- 13.3 Genetic Algorithms
- 13.4 Simulated Annealing
-
13.5 Artificial Neural Networks (ANN)
- 13.5.1 Analogy to the Brain
- 13.5.2 How they Work?
- 13.5.3 Electronic Implementation of Artificial Neurons
- 13.5.4 Artificial Network Operations
- 13.5.5 Training an Artificial Neural Network
- 13.5.6 Feed-Forward Network
- 13.5.7 Hopfield Feedback Connected Neural Network
- 13.5.8 How Neural Networks differ from Traditional Computing and Expert Systems
- 13.5.9 Artificial Neural Network Applications
- 13.6 Tabu Search (TS)
- Summary
- Key Terms
- Web Resources
-
Part 2: Algorithm Analysis
-
Chapter 14: Efficiency of Algorithms
- 14.1 Polynomial-Time (P) and Non-polynomial-Time (NPT) Algorithms
- 14.2 Worst and Average Case Behaviour
- 14.3 Time Analysis of Algorithms
- 14.4 Efficiency of Recursion
-
14.5 Complexity
- 14.5.1 The Notion of Complexity
- 14.5.2 Profiling
- 14.5.3 Suppressing Multiplicative Constants
- 14.5.4 Counting Dominant Operations
- 14.5.5 Growth-Rate
- 14.5.6 Upper Bounds
- 14.5.7 Asymptotic Growth-Rate
- 14.5.8 The ‘O’ Notation
- 14.5.9 Discussion
- 14.5.10 Simplified Definition of ‘O’
- 14.5.11 ‘O’ Notation Rules
- 14.5.12 Analyzing Growth of Exotic Functions
- 14.5.13 Derivative Rule
- 14.5.14 Order-of-Magnitude Comparisons
- 14.5.15 Doubling Comparisons
- 14.5.16 Estimating Complexity Experimentally
- 14.5.17 Experimental Comparison of Sorting Procedures
- Summary
- Key Terms
- Exercises
- Web Resources
- Chapter 15: Examples of Complexity Calculation
- Chapter 16: Time-Space Trade-Off
-
Chapter 17: Tractable and Non-tractable Problems
- 17.1 Introduction
- 17.2 Upper and Lower Bounds
- 17.3 Efficiency and Tractability
- 17.4 NP-Completeness
- 17.5 Polynomial Time Reductions
- 17.6 Problem Classes P, NP, and Others
- 17.7 Bounded Halting is in NPC
- 17.8 Cook’s Theorem
- 17.9 Is P = NP?
- 17.10 Approximate Solutions to NPC Problems
- 17.11 Provably Intractable Problems
- 17.12 Even Harder Problems
- 17.13 Unreasonable Requirements of Memory
- 17.14 Complexity Classes and Intractability
- 17.15 Non-computability and Undecidability
- 17.16 Algorithmic Program Verification
- 17.17 Partially and Highly Undecidable Problems
- 17.18 The Four Levels of Algorithmic Behaviour
- Summary
- Key Terms
- Web Resources
- Chapter 18: Some NP and NP-Complete Problems
- Chapter 19: Randomized and Approximate Algorithms
-
Chapter 20: Formal Specifications—1 Model Oriented
- 20.1 Formal Specifications
-
20.2 Introduction to VDM
- 20.2.1 The Implicit Specification of Operations
- 20.2.2 Examples of Implicit Specifications
- 20.2.3 The Logical Condition
- 20.2.4 Reasoning with Pre- and Post-conditions
- 20.2.5 Introduction to VDM Data Types
- 20.2.6 The Primitive Types
- 20.2.7 The Set Type
- 20.2.8 Implicit Definition of Sets
- 20.2.9 Creating VDM State Models
- 20.2.10 Composites
- 20.3 A Systematic Approach to the Construction of VDM Specifications
- 20.4 The Sequence and Map Types
- Summary
- Key Terms
- Exercises
- Web Resources
- Chapter 21: Formal Specifications—2 Algebraic
-
Appendix A: Essential Mathematical Background
- A.1 What is Discrete Mathematics?
-
A.2 Formal Logic: A Language for Mathematics
- A.2.1 Assertions and Propositions
- A.2.2 Logical Connectives
- A.2.3 Tautologies, Contradictions, and Contingencies
- A.2.4 Proof Techniques
- A.2.5 Predicates
- A.2.6 Quantifiers
- A.2.7 Free and Bound Variables
- A.2.8 Implications and Equivalences
- A.2.9 Classification of Assertions in Predicate Logic
- A.2.10 Inference Rules in Predicate Logic
- A.3 Sets
- A.4 Asymptotic Notations
- A.5 Number Theory
- A.6 Formal Languages
- A.7 Proof by Induction
- A.8 Introduction to Combinatorics
- A.9 Random Variables
- A.10 Relations
- A.11 Graph Theory
- Exercises
- Appendix B: Overview of Essential Data Structures
- Appendix C: Solutions of Recurrence Relations
-
Appendix D: Additional Exercises with Solutions
-
D.1 Additional Exercises
- D.1.1 Chapter 4: Loop Design Issues
- D.1.2 Chapter 6: Proof Rule Basics
- D.1.3 Chapter 7: Design by Proof Rules
- D.1.4 Chapter 9: Divide and Conquer
- D.1.5 Chapter 10: Greedy Methods
- D.1.6 Chapter 11: Dynamic Programming
- D.1.7 Chapter 12: Backtracking and Branch-and-Bound
- D.1.8 Chapter 14: Efficiency of Algorithms
- D.1.9 Chapter 15: Complexity Calculation
- D.1.10 Chapter 17: Tractable and Non-tractable Problems
- D.1.11 Chapter 18: Some NP and NPC Problems
- D.1.12 Chapter 19: Approximate Solutions
- D.1.13 Appendix D: Solutions of Recurrence Relations
-
D.2 Hints and Solutions
- D.2.1 Chapter 4: Loop Design Issues
- D.2.2 Chapter 6: Proof Rules Basic
- D.2.3 Chapter 7: Design by Proof Rules
- D.2.4 Chapter 9: Divide and Conquer
- D.2.5 Chapter 10: Greedy Algorithms
- D.2.6 Chapter 11: Dynamic Programming
- D.2.7 Chapter 12: Backtracking and Branch-and-Bound
- D.2.8 Chapter 14: Efficiency of Algorithms
- D.2.9 Chapter 15: Complexity Calculations
- D.2.10 Chapter 17: Tractable and Non-tractable Problems
- D.2.11 Chapter 18: Some NP and NPC Problems
- D.2.12 Chapter 19: Approximate Solutions
- D.2.13 Appendix D: Solutions of Recurrence Relations
-
D.1 Additional Exercises
-
Appendix E: Examples of Algorithms
- E.1 Existence of a Triangle
- E.2 GCD—Recursive Implementation
- E.3 Knight’s Tour
- E.4 Tail Recursion—Factorial()
- E.5 Recursive Implementation of Fibonacci()
- E.6 Power Function
- E.7 Amicable Numbers
- E.8 Premature Exits
- E.9 Vertex Cover
- E.10 Context Free Language
- E.11 Optimum Places for Line Breaks
- E.12 Car Travel Problem
- E.13 Activity Selection Problem
- E.14 Scheduling with Deadlines, Profits and Duration
- E.15 Longest Up-sequence
- E.16 Unary Partition
- E.17 Upper Bound on Time Complexity
- E.18 van Emde Boas Tree Space Usage
- E.19 Empirical Study of Space Used by van Emde Boas Trees
- E.20 Reducing the Space in the van Emde Boas Structure
- E.21 Binary Trie
- E.22 X-fast_trie
- E.23 Y-fast_trie
- E.24 Numerical Algorithms—Correlation
- E.25 Numerical Algorithms—Convolution
- E.26 Numerical Algorithms—Discrete Fourier Transform
- E.27 Numerical Algorithms—Fast Fourier Transform
- E.28 Numerical Algorithms—Wavelet Transforms
- E.29 Numerical Algorithms—Digital Signal Processing
- E.30 Numerical Algorithms—Z Transform
-
Chapter 14: Efficiency of Algorithms
- Bibliography
- Copyright
- Back Cover
Product information
- Title: Design and Analysis of Algorithms, 2nd Edition by Pearson
- Author(s):
- Release date: May 2024
- Publisher(s): Pearson India
- ISBN: 9789332520158
You might also like
book
Design and Analysis of Algorithms
All aspects pertaining to algorithm design and algorithm analysis have been discussed over the chapters in …
book
Algorithms For Dummies, 2nd Edition
Your secret weapon to understanding—and using!—one of the most powerful influences in the world today From …
book
Algorithms For Dummies
Discover how algorithms shape and impact our digital world All data, big or small, starts with …
book
A Guide to Algorithm Design
Presenting a complementary perspective to standard books on algorithms, A Guide to Algorithm Design provides a …