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

All aspects pertaining to algorithm design and algorithm analysis have been discussed over the chapters in this book-- Design and Analysis of Algorithms.

1. Cover
2. Title page
3. Brief Contents
4. Contents
5. Dedication
6. Preface
7. 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. Summary
7. Key Terms
8. Exercises
9. 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. Summary
7. Key Terms
8. Exercises
9. Web Resources
11. Chapter 11. Abstract Algorithms 3—Dynamic Programming
1. 11.1 Introduction
2. 11.2 Example—Multistage Graphs
3. 11.3 Example—Traveling Salesman (TS)
4. 11.4 Example—Matrix Multiplication
5. 11.5 Example—Longest Common Sub-sequence (LCS)
6. 11.6 Example—Optimal Polygon Triangulation
7. 11.7 Single Source Shortest Paths
8. 11.8 Maximum Flow Problems
9. 11.9 Conclusion
10. Summary
11. Key Terms
12. Exercises
13. Web Resources
12. Chapter 12. Abstract Algorithms 4—Backtracking
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. Summary
7. Key Terms
8. Exercises
9. 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
7. Summary
8. Key Terms
9. Web Resources
8. Part 2. Algorithm Analysis
1. Chapter 14. Efficiency of Algorithms
1. 14.1 Polynomial-Time and Non-Polynomial-Time 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 Dijkstra’s Shortest-Path Algorithm
6. 15.6 Splay Trees
7. Summary
8. Key Terms
9. Exercises
10. Web Resources
3. Chapter 16. Time-Space Trade-Off
1. 16.1 Introduction
2. 16.2 A Quick Review of Complexity
3. 16.3 Time-Space Trade-Off
4. 16.4 Time-Space Trade-Off in Algorithm Research
5. 16.5 Case Study—Perrin Numbers
6. Summary
7. Key Terms
8. Exercises
9. 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. Summary
6. Key Terms
7. Exercises
8. 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. Some Useful Mathematical Formulae
1. B.1 Definitions
2. B.2 Sums
3. B.3 Identities
4. B.4 Trees
5. B.5 Recurrences
6. B.6 Some Constants
7. B.7 General
8. B.8 Trigonometry
9. B.9 Number Theory
10. B.10 Graph Theory
11. B.11 Value Of π
12. B.12 Partial Fractions
13. B.13 Calculus
14. B.14 Series
11. Appendix C. Overview of Essential Data Structures
1. C.1 Introduction
2. C.2 Primitive Data Structures
3. C.3 Arrays and Lists
4. C.4 Stacks
5. C.5 Queues
6. C.6 Priority Queues
7. C.7 Trees
8. C.8 Binary Search Trees
9. C.9 Skip Lists
10. C.10 Hash Tables
11. C.11 Graphs
12. C.12 Linked List-Structure
12. Appendix D. Solutions of Recurrence Relations
1. D.1 Introduction
2. D.2 Preliminaries
3. D.3 Methods of Solution of Recurrence Relations
4. D.4 Algorithm Analysis by Recurrence Relations
5. D.5 Examples
13. Appendix E Additional Exercises with Solutions
1. E.1 Additional Exercises
2. E.2 Hints and Solutions
14. Bibliography
15. Notes