Analysis and Design of Algorithms: A Beginner's Approach

Description

The book is designed to serve as a textbook for one semester course of the undergraduate students of Computer Science & Engineering and Information Technology as well as postgraduate students of Computer Applications of Rajiv Gandhi Proudyogiki Vishwavidyalaya. This highly structured and well-organized text provides the design techniques of algorithms in a simple and straightforward manner. It describes the complete development of various algorithms along with their self-explanatory pseudocodes supported by worked-out examples in order to have better understanding of algorithms.

About the Author

Rajesh K. Shukla is the Dean (R&D) and Head of the Department of Computer Science and Engineering at Sagar Institute of Research and Technology

Table of Contents

1 Introduction to Algorithms

1.1 Definition of Algorithms

1.2 Properties of Algorithms

1.3 Expressing Algorithms

1.4 Flowchart

1.5 Algorithm Design Techniques

1.6 Performance Analysis of Algorithms

1.7 Types of Algorithm’s Analysis

1.8 Order of Growth

1.9 Asymptotic Notations

1.10 Recursion

1.11 Recurrences Relation

1.12 Substitution Method

1.13 Iterative Method

1.14 Recursion Tree

1.15 Master Theorem

1.16 Changing Variable

1.17 Heap Sort

2 Divide and Conquer

2.1 Introduction to Divide and Conquer Technique

2.2 Binary Search

2.3 Merge Sort

2.4 Quick Sort

2.5 Strassen’s Matrix Multiplication

3 Greedy Algorithms

3.1 Introduction to Greedy Technique

3.2 Greedy Method

3.3 Optimal Merge Patterns

3.4 Huffman Coding

3.5 Knapsack Problem

3.6 Activity Selection Problem

3.7 Job Sequencing with Deadline

3.8 Minimum Spanning Tree

3.9 Single-Source Shortest Path Algorithm

4 Dynamic Programming

4.1 Introduction

4.2 Characteristics of Dynamic Programming

4.3 Component of Dynamic Programming

4.4 Comparison of Divide-and-Conquer and Dynamic Programming Techniques

4.5 Comparison of Dynamic Programming and Greedy Technique

4.6 Applications of Dynamic Programming

5 Backtracking

5.1 Backtracking Concept

5.2 N-Queens Problem

5.3 Four-Queens Problem

5.4 Eight-Queens Problem

5.5 Hamiltonian Cycle

5.6 Sum of Subsets Problem

5.7 Graph Coloring Problem

6 Branch and Bound

6.1 Introduction

6.2 Travelling Salesperson Problem

6.4 15-Puzzle Problem

6.5 Comparisons between Backtracking and Branch and Bound

7 Tree

7.1 Introduction

7.2 Binary Tree

7.3 Tree Traversal Techniques

7.4 Reconstruction of a Tree

7.5 Binary Search Tree

7.6 Balanced Tree

8 Graph

8.1 Introduction

8.2 Basic Terminologies of Graph

8.3 Types of Graph

8.4 Representations of Graphs

8.5 Graph Traversal Techniques

8.6 Directed Acyclic Graph

9 NP Completeness

9.1 Introduction

9.2 The Complexity Class P

9.3 The Complextity Class NP

9.4 Polynomial-Time Reduction

9.5 The Complextity Class NP-Complete

Summary

Key Terms

Multiple-Choice Questions

Review Questions

Answers

Index