Design and Analysis of Algorithms.

Format:

Book

Author/Creator:

Dave, Parag H.

Language:

English

Subjects (All):

Algorithms.

Algorithms--History.

Physical Description:

1 online resource (834 pages)

Edition:

[First edition].

Place of Publication:

: Pearson India, 1900.

Summary:

Design and Analysis of Algorithms is the outcome of teaching, research and consultancy done by the authors over more than two decades. All aspects pertaining to algorithm design and algorithm analysis have been discussed over the chapters.

Contents:

Cover

Design and Analysis of Algorithms

Copyright

Preface

Brief Contents

Contents

Timeline of Algorithms

Algorithm Design

Introduction

Objectives

Basic Concerns

Relationship Between Algorithms and other Aspects of Software

The Evolution of Algorithm

Summary

Key Terms

Exercises

Web Resources

Problem Solving with a Computer

Solving a Problem with a Computer

Statement of the Problem or Problem Definition

Development of a Model

Design of the Algorithm

Checking the Correctness of the Algorithm

Implementation in Some Programming Language

Analyze and Study the Complexity of the Algorithm

Program Testing-Debugging and Profiling

Documentation preparation

Some More Examples

Finding the square root of a number

Smallest divisor of an integer number

Generation of prime numbers

Generation of pseudo-random numbers

Problem Solving in General

The STAIR steps for solving problems

Problem solving as applied to numerical algorithms

Reduction to known problems

Strategy if we are stuck

Top-Down Design

Structured Programming

Control Constructs

If-Then-Else

For-Do

Case

Repeat-Until

While-Do

Goto and ExitLoop

Procedures and Functions

Recursion

Order of Execution of Statements in a Recursive Function

Iterative Algorithm Design Issues

Introductio

Use of Loops

Efficiency of Algorithms

Removing Redundant Computations Outside Loops

Referencing of Array Elements

Inefficiency Due to Late Termination

Early Detection of Desired Output Conditions

Estimating and Specifying Execution Times.

Justification for the Use of Problem Size as a Measure

Computational Cost as a Function of Problem Size for a range of Computational complexities

Order Notation

Big-Oh notation

Theta notation

Omega Notation

Small-oh Notation

ω Notation

Measuring the Execution Times

Other Trade-offs

Algorithm Strategies

Computation Models and Design by Refinement

Functional Model

Features of Functional Model

Recursive Processes

Analysis of Correctness and Efficiency

More Examples of Recursive Algorithms

Scope Rules

Tail-Recursion and Iterative Processes

Correctness of an Iterative Process

More Examples of Iterative Processes

Imperative Model

The Primitives for the Imperative Model

Specifications and Prototyping

Examples of Step-wise Refinement

Proof Rules-Basics

Computer Model for Program Execution

Assertions at Input and Output of Blocks

Symbolic Execution

Proof Rules

Compound Statements

Conditional Statements

Case Statements

Repetitive Statements

Repeat-Until Statement

Example: The Division Algorithm

Correct Termination of Algorithms

Proof Rules for more Advanced Constructs

For Loops

GoTo and ExitLoop

Program Transformation

Functions and Procedures

Recursive Functions

Design by Proof Rules

A Fresh Look at Proof Rules

Referring to Previous Values of Variables

Designing Correct Programs

The Interface Specification

Applying the Rules to Deduce the Program Statement Types

Design Example

Design of a Loop

Loop Termination.

A Simple Design Procedure for Loops Based on Proof-Rules

Example 1: Linear Search

Example 2: Linear Search without Assurance

Example 3: Searching a 2-D Array

Example: Selection Sort

Example: Partition

Design Using Recursion

Execution Trace

Regular Expressions

An Interesting Recursive Function

Another Look at Iteration and Recursion

Abstract Algorithms-1-Divide-and-Conquer

A Multiplication Algorithm

Analysis of the Multiplication Algorithm

Application to Graphics Algorithms

Introduction to Triangulation

Convex Hulls

Where D & C Fails

Characteristics of Problems for which D & C is Unsuitable

Timing Analysis

Abstract Algorithms 2-Greedy Methods

Example-Knapsack Problem

Job Sequencing with Deadlines

Example-Minimum Spanning Trees

Prim's Algorithm

Kruskal's Algorithm

1st Version-Kruskal.c

Union-Find Data-Structure

Tree-Based Disjoint sets and the Quick-Union Algorithm

Implementing Quick-Union with an Array

Complexity Analysis of Quick-Union

Using Union-find in Kruskal Algorithm

Matroids

Correctness of Kruskal's Algorithm

Example [Shortest Path]

Dijkstra's Shortest Path Algorithm

Abstract Algorithms 3-Dynamic Programming

Example-Multistage Graphs

Example-Traveling Salesman

Example-Matrix Multiplication

Brute Force Solution-Try all Possible Parenthesisations

Dynamic Programming

Example-Longest Common Sub-sequence

Brute Force Method

Example-Optimal Polygon Triangulation.

Problem

Single Source Shortest Paths

Shortest Paths Problem

Shortest Paths Tree

All-Pairs Shortest Paths

Maximum Flow Problems

Flow Networks

Maximum-Flow Problem

Analysis of Ford-Fulkerson Algorithm

Conclusion

Abstract Algorithms 4-Backtracking

Combinatorial Search

Search and Traversal

Breadth First Search

Depth First Search

The Backtracking Strategy

Example 1: 8-Queens Problem

Backtracking Framework

Efficiency of Backtracking

Example 2: M-Colouring Problem

Example 3: Hamiltonian Circuits

Some Typical State Spaces

Constructing all Subsets

Constructing all Permutations

Constructing all Paths in a Graph

Bandwidth Minimization

Covering Chess Boards

Convex Hull

Natural Algorithms-GA, SA, ANN, TS

Evolutionary Algorithms and Evolutionary Computing

Genetic Algorithms

An example problem

Observations

Simulated Annealing

Sample implementation

Artificial Neural Networks

Analogy to the Brain

How they Work?

Electronic Implementation of Artificial Neurons

Artificial Network Operations

Training an Artificial Neural Network

Feed-Forward Network

Hopfield Feedback Connected Neural Network

How Neural Networks Differ from Traditional Computing and Expert Systems

Artificial neural network applications

Tabu Search

Application Domain

The Reactive Tabu Search

Algorithm Analysis

Polynomial-Time and Non-Polynomial-Time Algorithms

Worst and Average Case Behaviour

Probabilistic Average Case Analysis

Time Analysis of Algorithms

More Timing Analysis.

Efficiency of Recursion

Complexity

The Notion of Complexity

Profiling

Suppressing Multiplicative Constants

Counting Dominant Operations

Growth-Rate

Upper Bounds

Asymptotic Growth-Rate

The 'O' Notation

Discussion

Simplified Definition of 'O'

'O' Notation Rules

Analyzing Growth of Exotic Functions

Derivative Rule

Order-of-Magnitude Comparisons

Doubling Comparisons

Estimating Complexity Experimentally

Experimental comparison of sorting procedures

Examples of Complexity Calculation

Examples from the Sorting World

Bucket Sort

Radix Sort

Simple Insertion Sort

Quick Sort

Heap sort-using a Tree to Sort

Merge Sort

Summary of Complexity and Characteristics of Sorting Algorithms

Complexity of Set Operations and Mappings

Sets Implementation Using an Unordered Array

Binary Search Principle

Binary Search Trees

Bit Vectors

Analysis Of Hashing

The Trie Principle

Sets vs. Bags and Mappings

Amortized Analysis

Potential Functions

Example-Binary, Binomial And Fibonacci Heaps

Binomial Heap

Fibonacci Heap

Dijkstra's Shortest-Path Algorithm

Analysis

Splay Trees

Basics Of Splay Trees

Splay Operation

Amortized Timing Analysis

Time-Space Trade-off

An Example Of Time-Space Trade-Off

A Quick Review of Complexity

Time-Space Trade-Off

Some Simple Examples

Time-Space Trade-Off in Algorithm Research

Case Study-Perrin Numbers

Perrin Numbers

First Try-Straight-Forward Implementation

Second Try-Dynamic Programming

Third Try-Reduction And Divide & Conquer

The Final Results

Tractable and Non-tractable Problems.

Objectives.

Notes:

Description based on publisher supplied metadata and other sources.

ISBN:

1-282-68129-X

9786612681295

81-317-4056-0

OCLC:

1027147630