Design and Analysis of Algorithms - Jun 2013

Computer Science Engg. (Semester 4)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) What is an algorithm? What are the properties of an algorithm? Explain with an example.(8 marks) 1 (b) Explain brute force method for algorithm design and analysis. Explain the brute force string matching algorithm with its efficiency.(8 marks) 1 (c) Express using asymptotic notation i) n! ii) 6×2ⁿ+n²(4 marks) 2 (a) Explain divide and conquer technique. Write the algorithm for binary search and find average case efficiency.(10 marks) 2 (b) What is stable algorithm? Is quick sort stable? Explain with example.(6 marks) 2 (c) Give an algorithm for merge sort.(4 marks) 3 (a) Explain the concept of greedy technique for Prim's algorithm. Obtain minimum cost spanning tree for the graph below Prim's algorithm.
  (9 marks) 3 (b) Solve the following single source shortest path problem assuming vertex 5 as the source.
  (9 marks) 3 (c) Define the following: i) Optimal solution; ii) Feasible solution(2 marks) 4 (a) Using Floyd's algorithm solve the all pair shortest problem for the graph whose weight matrix is given below: $$ \begin{bmatrix} 0 &\infty &3 &\infty \\2 &0 &\infty &\infty \\\infty &7 &0 &1 \\6 &\infty &\infty &0 \end{bmatrix} $$(7 marks) 4 (b) Using dynamic programming, solve the following knapsack instance.
N=4. M=5
(W₁, W₂, W₃, W₄)= (2, 1, 3, 2)
( P₁, P₂, P₃, P₄)=(12, 10, 20, 15).(5 marks) 4 (c) Outline an exhaustive search algorithm to solve traveling salesman problem.(8 marks) 5 (a) Write and explain DFS and BFS algorithm with example.(8 marks) 5 (b) Obtain topologies sorting for the given diagram using source removal method.
  (5 marks) 5 (c) Explain Horspool's string matching algorithm for a text that comprises letter and space (denoted by hyphen) i.e "JIM-SAW-ME-IN-BARBER-SHOP" with pattern "BARBER". Explain its working along with a neat table and algorithm to shift table.(7 marks) 6 (a) Define the following:
i) Class P
ii) Class NP
iii) NP complete problem
iv) NP hard problem(8 marks) 6 (b) Write the decision tree to sort the elements using selection sort and find the lower bound.(8 marks) 6 (c) What is numeric analysis?(2 marks) 6 (d) Brief overflow and underflow in numeric analysis algorithms.(2 marks) 7 (a) What is back tracking? Apply back tracking problem to solve the instance of the sum of subset problem: S={3,5,6,7} and d=15.(7 marks) 7 (b) With the help of a state space tree, solve the following instance of the knapsack problem by the branch and bound algorithm.