Download Safari Books Online apps: Apple iOS | Android

Entire Site

Safari Books Online

    Free Trial

    Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

    Start ReadingShare
    Design and Analysis of Algorithms

    • Design and Analysis of Algorithms

    • By: Parag H. Dave; Himanshu B. Dave

    • Publisher: Pearson Education India

    • Pub. Date:

    • Print ISBN-10: 81-775-8595-9

    • Print ISBN-13: 978-81-775-8595-7

    • Pages in Print Edition: 832

    • Subscriber Rating: 5 out of 5 rating5 [2 Ratings]

    ebooken
    Subscriber Reviews • Browse Similar Topics

    Overview

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

    Subscriber Reviews

    Average Rating: 5 out of 5 rating Based on 2 Ratings

    No Subscribers have provided a review for this book.

    Table of Contents

     Index

    View Sample

    Copyright

    View Sample

    Preface

    View Sample

    Timeline of algorithms

    View Sample

    Part 1: Algorithm Design

    View Sample
    Chapter 1. Introduction
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 1.1. Basic Concerns

    View Sample

    Section 1.2. Relationship between Algorithms and Other Aspects of Software

    View Sample

    Section 1.3. The Evolution of Algorithm

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 2. Problem Solving with a Computer
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 2.1. Introduction

    View Sample

    Section 2.2. Solving a Problem with a Computer

    View Sample

    Section 2.3. Some More Examples

    View Sample

    Section 2.4. Problem Solving in General

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 3. Top-Down Design
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 3.1. Introduction

    View Sample

    Section 3.2. Structured Programming

    View Sample

    Section 3.3. Control Constructs

    View Sample

    Section 3.4. Procedures and Functions

    View Sample

    Section 3.5. Recursion

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 4. Iterative Algorithm Design Issues
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 4.1. Introduction

    View Sample

    Section 4.2. Use of Loops

    View Sample

    Section 4.3. Efficiency of Algorithms

    View Sample

    Section 4.4. Estimating and Specifying Execution Times

    View Sample

    Section 4.5. Order Notation

    View Sample

    Section 4.6. Algorithm Strategies

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 5. Computation Models and Design by Refinement
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 5.1. Introduction

    View Sample

    Section 5.2. Functional Model

    View Sample

    Section 5.3. Imperative Model

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 6. Proof Rules—Basics
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 6.1. Introduction

    View Sample

    Section 6.2. Computer Model for Program Execution

    View Sample

    Section 6.3. Assertions at Input and Output of Blocks

    View Sample

    Section 6.4. Proof Rules

    View Sample

    Section 6.5. Correct Termination of Algorithms

    View Sample

    Section 6.6. Proof Rules for More Advanced Constructs

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 7. Design by Proof Rules
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 7.1. A Fresh Look at Proof Rules

    View Sample

    Section 7.2. Designing Correct Programs

    View Sample

    Section 7.3. Design of a Loop

    View Sample

    Section 7.4. A Simple Design Procedure for Loops based on Proof-Rules

    View Sample

    Section 7.5. Example: Selection Sort

    View Sample

    Section 7.6. Example: Partition ()

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 8. Design Using Recursion
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 8.1. Introduction

    View Sample

    Section 8.2. Execution Trace

    View Sample

    Section 8.3. Another Look at Iteration and Recursion

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 9. Abstract Algorithms-1-Divide-and-Conquer
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 9.1. Introduction

    View Sample

    Section 9.2. A Multiplication Algorithm

    View Sample

    Section 9.3. Application to Graphics Algorithms

    View Sample

    Section 9.4. Where D&C Fails

    View Sample

    Section 9.5. Timing Analysis

    View Sample

    Summary

    View Sample

    Typical Results

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 10. Abstract Algorithms 2—Greedy Methods
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 10.1. Introduction

    View Sample

    Section 10.2. Example—Knapsack Problem

    View Sample

    Section 10.3. Job Sequencing with Deadlines

    View Sample

    Section 10.4. Example—Minimum Spanning Trees

    View Sample

    Section 10.5. Example [Shortest Path]

    View Sample

    Summary

    View Sample

    Typical Results

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 11. Abstract Algorithms 3—Dynamic Programming
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 11.1. Introduction

    View Sample

    Section 11.2. Example—Multistage Graphs

    View Sample

    Section 11.3. Example—Traveling Salesman (TS)

    View Sample

    Section 11.4. Example—Matrix Multiplication

    View Sample

    Section 11.5. Example—Longest Common Sub-Sequence (LCS)

    View Sample

    Section 11.6. Example—Optimal Polygon Triangulation

    View Sample

    Section 11.7. Single Source Shortest Paths

    View Sample

    Section 11.8. Maximum Flow Problems

    View Sample

    Section 11.9. Conclusion

    View Sample

    Typical Results

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 12. Abstract Algorithms 4—Backtracking
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 12.1. Combinatorial Search

    View Sample

    Section 12.2. Search and Traversal

    View Sample

    Section 12.3. The Backtracking Strategy

    View Sample

    Section 12.4. Backtracking Framework

    View Sample

    Section 12.5. Some Typical State Spaces

    View Sample

    Typical Results for Programs

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 13. Natural Algorithms—GA, SA, ANN, TS
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 13.1. Introduction

    View Sample

    Section 13.2. Evolutionary Algorithms and Evolutionary Computing

    View Sample

    Section 13.3. Genetic Algorithms

    View Sample

    Section 13.4. Simulated Annealing

    View Sample

    Section 13.5. Artificial Neural Networks (ANN)

    View Sample

    Section 13.6. Tabu Search (TS)

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Web Resources

    View Sample

    Part 2: Algorithm Analysis

    View Sample
    Chapter 14. Efficiency of Algorithms
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 14.1. Polynomial-Time(P) and Non-Polynomial-Time (NPT) Algorithms

    View Sample

    Section 14.2. Worst and Average Case Behaviour

    View Sample

    Section 14.3. Time Analysis of Algorithms

    View Sample

    Section 14.4. Efficiency of Recursion

    View Sample

    Section 14.5. Complexity

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 15. Examples of Complexity Calculation
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 15.1. Examples from the Sorting World

    View Sample

    Section 15.2. Summary of Complexity and Characteristics of Sorting Algorithms

    View Sample

    Section 15.3. Complexity of Set Operations and Mappings

    View Sample

    Section 15.4. Amortized Analysis

    View Sample

    Section 15.5. Dijkstra’s Shortest-Path Algorithm

    View Sample

    Section 15.6. Splay Trees

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 16. Time-Space Trade-off
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 16.1. Introduction

    View Sample

    Section 16.2. A Quick Review of Complexity

    View Sample

    Section 16.3. Time-Space Trade-Off

    View Sample

    Section 16.4. Time-Space Trade-Off in Algorithm Research

    View Sample

    Section 16.5. Case Study—Perrin Numbers

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 17. Tractable and Non-tractable Problems
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 17.1. Introduction

    View Sample

    Section 17.2. Upper and Lower Bounds

    View Sample

    Section 17.3. Efficiency and Tractability

    View Sample

    Section 17.4. NP-Completeness

    View Sample

    Section 17.5. Polynomial Time Reductions

    View Sample

    Section 17.6. Problem Classes P, NP, and Others

    View Sample

    Section 17.7. Bounded Halting is in NPC

    View Sample

    Section 17.8. Cook’s Theorem

    View Sample

    Section 17.9. Is P = NP?

    View Sample

    Section 17.10. Approximate Solutions to NPC Problems

    View Sample

    Section 17.11. Provably Intractable Problems

    View Sample

    Section 17.12. Even Harder Problems

    View Sample

    Section 17.13. Unreasonable Requirements of Memory

    View Sample

    Section 17.14. Complexity Classes and Intractability

    View Sample

    Section 17.15. Non-Computability and Undecidability

    View Sample

    Section 17.16. Algorithmic Program Verification

    View Sample

    Section 17.17. Partially and Highly Undecidable Problems

    View Sample

    Section 17.18. The Four Levels of Algorithmic Behaviour

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Web Resources

    View Sample
    Chapter 18. Some NP and NP-Complete Problems
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 18.1. Introduction

    View Sample

    Section 18.2. Turing Machine (TM)

    View Sample

    Section 18.3. Reductions

    View Sample

    Section 18.4. Reductions for Some Known Problems

    View Sample

    Section 18.5. Certificates and Verification

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 19. Randomized and Approximate Algorithms
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 19.1. Introduction

    View Sample

    Section 19.2. Randomized Algorithms

    View Sample

    Section 19.3. Randomized Complexity Classes

    View Sample

    Section 19.4. Approximate Algorithms

    View Sample

    Annexure-I: Is Randomness Always Bad?—Randomness as a Resource

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 20. Formal Specifications—1 Model Oriented
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 20.1. Formal Specifications

    View Sample

    Section 20.2. Introduction to VDM

    View Sample

    Section 20.3. A Systematic Approach to the Construction of VDM Specifications

    View Sample

    Section 20.4. The Sequence and Map Types

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Chapter 21. Formal Specifications—2 Algebraic
    View Sample

    Objectives

    View Sample

    Chapter Outline

    View Sample

    Section 21.1. Introduction

    View Sample

    Section 21.2. Algebraic Specification of an Unbounded Stack

    View Sample

    Summary

    View Sample

    Key Terms

    View Sample

    Exercises

    View Sample

    Web Resources

    View Sample
    Appendix A. Essential Mathematical Background
    View Sample

    Section A.1. What is Discrete Mathematics?

    View Sample

    Section A.2. Formal Logic: A Language for Mathematics

    View Sample

    Section A.3. Sets

    View Sample

    Section A.4. Asymptotic Notations

    View Sample

    Section A.5. Number Theory

    View Sample

    Section A.6. Formal Languages

    View Sample

    Section A.7. Proof by Induction

    View Sample

    Section A.8. Introduction to Combinatorics

    View Sample

    Section A.9. Random Variables

    View Sample

    Section A.10. Relations

    View Sample

    Section A.11. Graph Theory

    View Sample

    Exercises

    View Sample
    Appendix B. Some Useful Mathematical Formulae
    View Sample

    Section B.1. Definitions

    View Sample

    Section B.2. Sums

    View Sample

    Section B.3. Identities

    View Sample

    Section B.4. Trees

    View Sample

    Section B.5. Recurrences

    View Sample

    Section B.6. Some Constants

    View Sample

    Section B.7. General

    View Sample

    Section B.8. Trigonometry

    View Sample

    Section B.9. Number Theory

    View Sample

    Section B.10. Graph Theory

    View Sample

    Section B.11. Value of π

    View Sample

    Section B.12. Partial Fractions

    View Sample

    Section B.13. Calculus

    View Sample

    Section B.14. Series

    View Sample
    Appendix C. Overview of Essential Data Structures
    View Sample

    Section C.1. Introduction

    View Sample

    Section C.2. Primitive Data Structures

    View Sample

    Section C.3. Arrays and Lists

    View Sample

    Section C.4. Stacks

    View Sample

    Section C.5. Queues

    View Sample

    Section C.6. Priority Queues

    View Sample

    Section C.7. Trees

    View Sample

    Section C.8. Binary Search Trees

    View Sample

    Section C.9. Skip Lists

    View Sample

    Section C.10. Hash Tables

    View Sample

    Section C.11. Graphs

    View Sample

    Section C.12. Linked List-Structure

    View Sample
    Appendix D. Solutions of Recurrence Relations
    View Sample

    Section D.1. Introduction

    View Sample

    Section D.2. Preliminaries

    View Sample

    Section D.3. Methods of Solution of Recurrence Relations

    View Sample

    Section D.4. Algorithm Analysis by Recurrence Relations

    View Sample

    Section D.5. Examples

    View Sample

    Exercises

    View Sample
    Appendix E. Additional Exercises with Solutions
    View Sample

    Section E.1. Additional Exercises

    View Sample

    Section E.2. Hints and Solutions

    View Sample

    Bibliography

    View Sample

    Index