Analysis and Design of Algorithms: A Beginner's Approach
ISBN: 9788126554775
480 pages
eBook also available for institutional users
For more information write to us at: acadmktg@wiley.com
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.
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