Design And Analysis Of Algorithm

By Bhupendra Mandloi

Design and Analysis of Algorithm is advanced course of Data-Structure ,This is the big set of Algorithms.For a Single problem many algorithms are posible,among all algorithms some will be better performer.so in this course we can write or find better algoritms.

• Language: English
• Publisher: Bhupendra Mandloi
• Release date: Jul 23, 2018
• ISBN: 9781386097952

Book preview

CONTENTS

Chapters  ______________________  __     

Chapter 1: Introduction to algorithm   

1.1 Introduction   

1.2 Data Structure

1.3 Types of Data Structure

1.3.1 Array

1.3.2 Link list

1.3.3 Types of link list

1.3.3.1 Single link list

1.3.3.2 Double link list

1.3.3.3 Circular link list

1.3.3.4 Tree

1.3.3.5 Graph

1.4 Types of data

1.5 Need of array

1.6 Model of computation

1.6.1 Finite state machine

1.6.1.1 Deterministic finite automata

1.6.1.2 Nondeterministic finite automata

1.6.2 Push-down automata

1.6.3 Turing machine

1.7 Stack implementation method

1.8 Algorithm

1.9 Types of complexity

1.9.1 Time complexity

1.9.1.1 Big oh notation

1.9.1.2 Big omega notation

1.9.1.3 Big theta notation

1.9.1.4 Little oh notation

1.9.1.5 Little omega notation

1.9.2 Space complexity

Exercise 

Chapter 2: Divide and conquer

2.1 Introduction 

2.2 Strategy of divide and conquer

2.3 Divide and conquer algorithm

2.4 Divide and conquer explanation

2.5 Time complexity of DAndC algorithm

2.6 Binary search algorithm

2.7 Merge sort algorithm

2.8 Quick sort algorithm

2.9 Strassen’s matrix multiplication

Chapter 3: Graph searching and Traversal

3.1 Graph traversing

3.2 Adjacency matrix

3.3 Adjacency list

3.4 Depth first search algorithm

3.5 Breadth first search algorithm

Exercise 

Chapter 4: Greedy Method

4.1 Introduction

4.2 Greedy algorithm

4.3 Knapsack problem

4.4 Optimal storage on tapes

4.5 Job sequencing problem with deadline

4.6 Spanning tree

4.7 Minimum spanning tree

4.8 Prims algorithm

4.9 Kruskals algorithm

4.10 Single source shortest path algorithm

4.11 Huffman code

Chapter 5: Branch and bound

5.1 LC searching bounding

5.1.1 FIFO branch and bound search

5.1.2 LIFO branch and bound search

5.2  0/1 knapsack problem

5.3 Four queen problem

5.4 Eight queen problem

5.5  15 puzzle problem using least cost search

5.6  15 puzzle problem using branch and bound

5.7 Travelling salesperson problem

Exercise

Chapter 6: Dynamic programming

6.1 Introduction

6.2 Dynamic programming technique

6.3 All pair shortest path

6.4 Matrix chain multiplication

6.5 Travelling salesperson problem

6.6 Longest common sequence

Chapter 7: Back tracking

7.1 Introduction

7.2 Knapsack problem

7.3 N-queens problem

Exercise

Chapter 8: Computational Complexity

8.1 Complexity measures

8.2 P,NP,NP-C and NP-H problems

8.3 String processing

8.4 Hamiltonian cycle problem

8.5 String matching algorithms

8.6 Set algorithm

8.7 Combinatorial algorithm

Exercise

Chapter 1  INTRODUCTION TO ALGORITHM

––––––––

1.1  INTRODUCTION

Computer science make life easy to easiest day by day, in computer science a single problem can be solved by many methods or a single problem have many solutions. Many times it is difficult to select approach among lot of methods to solve a problem. In this chapter we will discuss about algorithms and its complexity.

1.2  DATASTRUCTURE

Data Structure is a logical or mathematical model of organized data. Here model means a well define structure where data will be stored for many purposes and organized data means particular data, for example in attendance sheet of class 1st contains only name of class 1st students not contains other students name of same organization. In real life every person use data structure even he/she know or don’t’ know about data structure.

Examples:-

Everybody keep wallet (keeping money inside).

Here money is data and wallet is a structure to keep money

CD box.

Here CD’s are data and box is structure to hold CD’s.

Bangle box.

Here bangles are data and bangle box is structure to hold bangles.

School/college library.

Books are data and tracks are structure to keep books inside.

Class room.

Here tables, chairs are data and class room is structure to keep data inside etc.

We can say structure is like home of data or model, where data can be stored and provide maximum benefits or easiness to end users.

Purpose behind data store:-only one reason behind the story is that, for future use or use when needed.

Benefits:-

Fast access.

Easily new elements insertion.

Easily existing elements deletion.

Easily search an element.

Easily merging etc.

1.3  TYPES OF DATA STRUCTURE

According to the arrangement of data into primary memory (RAM), data structure is categorized into two categories.

Linear data structure:-

Array

Link list

Stack

Queue

Non-Linear data structure:-

Tree

Graph

1.3.1  ARRAY

Array is a variable which is different from normal variables; array has removed the problem of normal variables that is holding multiple values at a time. So finally array is a special type of variable which can hold (store) multiple values into a single variable at a time, so array is a great concept in programming. Some ease with arrays is array occupied memory in sequential manners, so accessing of array elements are comparatively easy. Array is also known as index variable or subscripted variable so array elements stored on the basis of index, every element having separate index. Due to index based, array is best suitable for searching elements into array, it takes constant time for searching particular element at any index. Array having some great features as well as some problems with array those are given below.

1.3.2 LINK LIST

Link list is a dynamic data structure in which elements can be inserted or deleted at any position.

1.3.3 TYPES OF LINK LIST

Link list is categorized into three categories.

Single link list

Double link list

Circular link list

1.3.3.1 Single link list

Single link list is a linear collection of nodes where each node divide into two part first part contains information of node and