Design & Analysis of algorithms

b. Write insertion sort algorithm and obtain its time complexity. Apply insertion sort on these elements: 25, 75, 40, 10, 20, 

c. Obtain the maximum speed up when P = 10 and for various value of f=(0.5, 0.1, 0.01).

b. Explain the different types of computational models.

a. What is a prefix computation problem? Give the algorithm for prefix computation which use

i)n-processor      ii) n/log n

c. Obtain the optimal solution for the given assignment problem as a matrix shown below using branch and bound method : 

b. With help of a state space tree solve the following instance of the knapsack problem by the branch and bound algorithm

N=4 weight (w₁, w₂, w₃, w₄) = (4,7,5,3) Profit (p₁, p₂, p₃,p₄) = (40, 42, 25, 12)

W = 10 capacity of knapsack 

a. What is a N-Queen's problem? Give the state space tree for solving 4 Queen problem for atleast one solution? 

c. Explain the P, NP and NP complete problems.

b. What is a decision tree? Obtain decision tree to find minimum of three numbers.

a. Explain the lower bound and trivial lower bound arguments

c. Write a algorithm to sort by counting method. Obtain its time copmplexity, sort by count for given data 25, 45, 10, 20, 50, 15. 

a. Define big oh, omega and theta notations for analyzing algorithm. Give at least one example for each.

a. Explain the concept of decrease and conquer method, indicating the three major variations of the same with examples. 

b. Write a algorithm for knapsack problem for dynamic programming and solve the following instance of the knapsack problem, n = 4, weights (w₁, w₂, w₃, w₄) = (2,1,3,2), profit (p₁,p₂,p₃, p₄) = (12, 10, 20, 15) Capacity W=5. 

a. Write Floyd's algorithm and solve the all pair shortest path problem for the graph shown below: 

c. Write a Kruskal algorithm to find minimum cost spanning tree and obtain spanning tree of the graph shown below:

 b. Explain the concepts of greedy technique for prim's algorithm. Obtain minimum cost spanning tree for the graph whose weight matrix is given below

a. Obtain the optimal solution for the job sequencing problem with deadline, where n = 4 profit(P₁, P₂, P₃, P₄.) =(100, 10, 15, 27) and dead lines (d₁, d₂ , d₃ , d₄) =(2, 1, 2, 1). 

b. Write a algorithm for Quick sort, and sort the following number's 10, 8, 5, 15, 25, 75, 12.Obtain its time complexity. 

a. Explain the concept of divide and conquer. Design an algorithm for merge sort and derive time complexity. 

c. Write the algorithm for sequential search, obtain the time complexity of this algorithm for successful and unsuccessful search in the worst case and best ease.

b. Write a algorithm for selection sort in ascending order. Show that its complexity is O(n²)and sort the following list 65, 50, 21, 43, 10, 15.