## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 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.

1. Cover
2. Title Page
3. Brief Contents
4. Contents
5. Dedication
6. Preface
7. Preface to the First Edition
8. Timeline of Algorithms
9. Part 1: Algorithm Design
1. Chapter 1: Introduction
2. Chapter 2: Problem Solving with a Computer
1. 2.1 Introduction
2. 2.2 Solving a Problem with a Computer
3. 2.3 Some More Examples
4. 2.4 Problem Solving in General
5. Summary
6. Key Terms
7. Exercises
8. Web Resources
3. Chapter 3: Top-Down Design
1. 3.1 Introduction
2. 3.2 Structured Programming
3. 3.3 Control Constructs
4. 3.4 Procedures and Functions
5. 3.5 Recursion
6. Summary
7. Key Terms
8. Exercises
9. Web Resources
4. Chapter 4: Iterative Algorithm Design Issues
1. 4.1 Introduction
2. 4.2 Use of Loops
3. 4.3 Efficiency of Algorithms
4. 4.4 Estimating and Specifying Execution Times
5. 4.5 Order Notation
6. 4.6 Algorithm Strategies
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
5. Chapter 5: Computation Models and Design by Refinement
1. 5.1 Introduction
2. 5.2 Functional Model
3. 5.3 Imperative Model
4. Summary
5. Key Terms
6. Exercises
7. Web Resources
6. Chapter 6: Proof Rules—Basics
1. 6.1 Introduction
2. 6.2 Computer Model for Program Execution
3. 6.3 Assertions at Input and Output of Blocks
4. 6.4 Proof Rules
5. 6.5 Correct Termination of Algorithms
6. 6.6 Proof Rules for More Advanced Constructs
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
7. Chapter 7: Design by Proof Rules
1. 7.1 A Fresh Look at Proof Rules
2. 7.2 Designing Correct Programs
3. 7.3 Design of a Loop
4. 7.4 A Simple Design Procedure for Loops Based on Proof-rules
5. 7.5 Example: Selection Sort
6. 7.6 Example: Partition()
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
8. Chapter 8: Design Using Recursion
1. 8.1 Introduction
2. 8.2 Execution Trace
3. 8.3 Another Look at Iteration and Recursion
4. Summary
5. Key Terms
6. Exercises
7. Web Resources
9. Chapter 9: Abstract Algorithms 1—Divide-and-Conquer
1. 9.1 Introduction
2. 9.2 A Multiplication Algorithm
3. 9.3 Application to Graphics Algorithms
4. 9.4 Where D&C Fails
5. 9.5 Timing Analysis
6. 9.6 Decrease-and-Conquer
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
10. Chapter 10: Abstract Algorithms 2—Greedy Methods
1. 10.1 Introduction
2. 10.2 Example—Knapsack Problem
3. 10.3 Job Sequencing with Deadlines
4. 10.4 Example—Minimum Spanning Trees
5. 10.5 Example [Shortest Path]
6. 10.6 Optimal Merge Patterns
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
11. Chapter 11: Abstract Algorithms 3—Dynamic Programming
1. 11.1 Introduction
2. 11.2 Rod Cutting Problem
3. 11.3 Example—Multistage Graphs
4. 11.4 Example—Traveling Salesman (TS)
5. 11.5 Example—Matrix Multiplication
6. 11.6 Example—Longest Common Sub-sequence (LCS)
7. 11.7 Example—Optimal Polygon Triangulation
8. 11.8 Single Source Shortest Paths
9. 11.9 Maximum Flow Problems
10. 11.10 Conclusion
11. Summary
12. Key Terms
13. Exercises
14. Web Resources
12. Chapter 12: Abstract Algorithms 4—Backtracking, Branch and Bound
1. 12.1 Combinatorial Search
2. 12.2 Search and Traversal
3. 12.3 The Backtracking Strategy
4. 12.4 Backtracking Framework
5. 12.5 Some Typical State Spaces
6. 12.6 Branch-and-Bound Algorithms
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
13. Chapter 13: Natural Algorithms—GA, SA, ANN, TS
1. 13.1 Introduction
2. 13.2 Evolutionary Algorithms and Evolutionary Computing
3. 13.3 Genetic Algorithms
4. 13.4 Simulated Annealing
5. 13.5 Artificial Neural Networks (ANN)
6. 13.6 Tabu Search (TS)
7. Summary
8. Key Terms
9. Web Resources
10. Part 2: Algorithm Analysis
1. Chapter 14: Efficiency of Algorithms
1. 14.1 Polynomial-Time (P) and Non-polynomial-Time (NPT) Algorithms
2. 14.2 Worst and Average Case Behaviour
3. 14.3 Time Analysis of Algorithms
4. 14.4 Efficiency of Recursion
5. 14.5 Complexity
6. Summary
7. Key Terms
8. Exercises
9. Web Resources
2. Chapter 15: Examples of Complexity Calculation
1. 15.1 Examples from the Sorting World
2. 15.2 Summary of Complexity and Characteristics of Sorting Algorithms
3. 15.3 Complexity of Set Operations and Mappings
4. 15.4 Amortized Analysis
5. 15.5 Dĳkstra’s Shortest-path Algorithm
6. 15.6 Splay Trees
7. 15.7 Van Emde Boas Trees
8. Summary
9. Key Terms
10. Exercises
11. Web Resources
1. 16.1 Introduction
2. 16.2 A Quick Review of Complexity
4. 16.4 Pattern Matching and String Processing
5. 16.5 Time-Space Trade-Off in Algorithm Research
6. 16.6 Case Study—Perrin Numbers
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
4. Chapter 17: Tractable and Non-tractable Problems
1. 17.1 Introduction
2. 17.2 Upper and Lower Bounds
3. 17.3 Efficiency and Tractability
4. 17.4 NP-Completeness
5. 17.5 Polynomial Time Reductions
6. 17.6 Problem Classes P, NP, and Others
7. 17.7 Bounded Halting is in NPC
8. 17.8 Cook’s Theorem
9. 17.9 Is P = NP?
10. 17.10 Approximate Solutions to NPC Problems
11. 17.11 Provably Intractable Problems
12. 17.12 Even Harder Problems
13. 17.13 Unreasonable Requirements of Memory
14. 17.14 Complexity Classes and Intractability
15. 17.15 Non-computability and Undecidability
16. 17.16 Algorithmic Program Verification
17. 17.17 Partially and Highly Undecidable Problems
18. 17.18 The Four Levels of Algorithmic Behaviour
19. Summary
20. Key Terms
21. Web Resources
5. Chapter 18: Some NP and NP-Complete Problems
1. 18.1 Introduction
2. 18.2 Turing Machine (TM)
3. 18.3 Reductions
4. 18.4 Reductions for Some Known Problems
5. 18.5 Certificates and Verification
6. Summary
7. Key Terms
8. Exercises
9. Web Resources
6. Chapter 19: Randomized and Approximate Algorithms
1. 19.1 Introduction
2. 19.2 Randomized Algorithms
3. 19.3 Randomized Complexity Classes
4. 19.4 Approximate Algorithms
5. 19.5 Case Study: An Implementation of Sudoku-solver Using Randomized Algorithm
6. Annexure-I
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
7. Chapter 20: Formal Specifications—1 Model Oriented
1. 20.1 Formal Specifications
2. 20.2 Introduction to VDM
3. 20.3 A Systematic Approach to the Construction of VDM Specifications
4. 20.4 The Sequence and Map Types
5. Summary
6. Key Terms
7. Exercises
8. Web Resources
8. Chapter 21: Formal Specifications—2 Algebraic
1. 21.1 Introduction
2. 21.2 Algebraic Specification of an Unbounded Stack
3. Summary
4. Key Terms
5. Exercises
6. Web Resources
9. Appendix A: Essential Mathematical Background
1. A.1 What is Discrete Mathematics?
2. A.2 Formal Logic: A Language for Mathematics
3. A.3 Sets
4. A.4 Asymptotic Notations
5. A.5 Number Theory
6. A.6 Formal Languages
7. A.7 Proof by Induction
8. A.8 Introduction to Combinatorics
9. A.9 Random Variables
10. A.10 Relations
11. A.11 Graph Theory
12. Exercises
10. Appendix B: Overview of Essential Data Structures
1. B.1 Introduction
2. B.2 Primitive Data Structures
3. B.3 Arrays and Lists
4. B.4 Stacks
5. B.5 Queues
6. B.6 Priority Queues
7. B.7 Trees
8. B.8 Binary Search Trees
9. B.9 Skip Lists
10. B.10 Hash Tables
11. B.11 Graphs
13. B.13 Augmenting Data Structures
11. Appendix C: Solutions of Recurrence Relations
1. C.1 Introduction
2. C.2 Preliminaries
3. C.3 Methods of Solution of Recurrence Relations
4. C.4 Algorithm Analysis by Recurrence Relations
5. C.5 Examples
6. Exercises
12. Appendix D: Additional Exercises with Solutions
2. D.2 Hints and Solutions
13. Appendix E: Examples of Algorithms
1. E.1 Existence of a Triangle
2. E.2 GCD—Recursive Implementation
3. E.3 Knight’s Tour
4. E.4 Tail Recursion—Factorial()
5. E.5 Recursive Implementation of Fibonacci()
6. E.6 Power Function
7. E.7 Amicable Numbers
8. E.8 Premature Exits
9. E.9 Vertex Cover
10. E.10 Context Free Language
11. E.11 Optimum Places for Line Breaks
12. E.12 Car Travel Problem
13. E.13 Activity Selection Problem
14. E.14 Scheduling with Deadlines, Profits and Duration
15. E.15 Longest Up-sequence
16. E.16 Unary Partition
17. E.17 Upper Bound on Time Complexity
18. E.18 van Emde Boas Tree Space Usage
19. E.19 Empirical Study of Space Used by van Emde Boas Trees
20. E.20 Reducing the Space in the van Emde Boas Structure
21. E.21 Binary Trie
22. E.22 X-fast_trie
23. E.23 Y-fast_trie
24. E.24 Numerical Algorithms—Correlation
25. E.25 Numerical Algorithms—Convolution
26. E.26 Numerical Algorithms—Discrete Fourier Transform
27. E.27 Numerical Algorithms—Fast Fourier Transform
28. E.28 Numerical Algorithms—Wavelet Transforms
29. E.29 Numerical Algorithms—Digital Signal Processing
30. E.30 Numerical Algorithms—Z Transform
11. Bibliography