Design And Analysis Of Algorithm.pdf 3e564q

Design and Analysis of Algorithms

Dr.P.Rizwan Ahmed Head of the Department Department of Computer Applications & Post Graduate Department of Information Technology Mazharul Uloom College, Ambur – 635 802 Tamil Nadu, INDIA.

Contents

Chapter -1 1.1 Introduction to Algorithm 1.1.1 What is an Algorithm? 1.1.2 Definition of Algorithm 1.2 Algorithms Properties 1.3 Algorithm Specification 1.4 Performance Analysis 1.5 Asymptotic Notations 1.6 Randomized Algorithm Review Questions

Algorithm and Analysis

Chapter 2 2.1 Introduction 2.2 General Method 2.3 Binary Search 2.4 Finding the minimum and maximum 2.5 Merge Sort 2.6 Quick Sort 2.7 Selection Sort 2.8 Strassen’s Matrix Multiplications Review Questions

Divide and Conquer

Chapter 3 3.1 Introduction 3.2 General Method 3.3 Knapsack Problem 3.4 Tree Vertex Splitting 3.5 Job Sequencing with Deadlines 3.6 Minimum Cost Spanning Trees 3.6.1 Kruskal's algorithm 3.6.2 Prim’s Algorithm 3.7 Optimal Merge Patterns 3.7.1 Huffman Codes 3.7.2 Huffman's Algorithm 3.8 Single Source Shortest Paths Review Questions

The Greedy Method

Chapter 4 4.1 Introduction 4.2 The General Method 4.3 Multistage Graph 4.4 0/1 – Knapsack 4.5 Reliability Design 4.6 All Pairs Shortest Path 4.7 The Traveling Salesperson problem Review Questions

Dynamic Programming

Chapter 5 Traversal, Searching and Backtracking 5.1 Introduction 5.2 Techniques for Binary Trees 5.3 Techniques for Graphs 5.4 Backtracking 5.4.1 The General Method 5.5 Terminology 5.6 8-Queens Problem 5.7 Sum of Subsets 5.8 Graph Coloring 5.9 Hamiltonian Cycles Review Questions Appendix - A : Model Question Papers