Biju Patnaik University of Technology 2008-3rd Sem M.C.A Analysis & Design of Algorithm - Question Paper

Friday, 24 May 2013 07:40Web

Page 1 of 2

Tjhird Semester Examination - 2008 ANALYSIS AND DESIGN OF ALGORITHM Full Marks-70 Time: 3 Hours

Answer Question No. 1 which is compulsory and any five from the rest.

i

IWL

The figures in the right-hand margin indicate marks.

1. Answer the following questions ; 2 xlO

'-(ay What are the general characteristic of greedy algorithm ?

Construct a MAX-HEAP with the following elements {A, L, G_h O, R, I, T, H, M],

(c) Explain why instance characteristic Is an important consideration for algorithm complexity ?

What is the complexity of Prim's algorithm for finding a minimum spanning tree ? Explain,

How does the principle of optimality reduce rhe number of decision sequences in dynamic programming algorithms ?

_v(f) Using blg-O notation, state the average time and space complexity of binary search,

IWL

Jg) Solve the following recurrence relation : T(N)=4T(N -1 )+1 with T(1) = 1 and T(2)',=3

iffi) What do you mean by combinatorial problem? Can you find an optimal solution to this problems using dynamic programming ?

What do you mean by relaxation in the process of designing an approximation algorithm for NP-Hard problem ?

Define NP-Complete problem with example.

Ki)

2. (a)

(b) 3- M

What do you mean by complexity bf an algorithm ? Derive the asymptotic ttme complexity of a non recursive, binary search algorithm using divide and conquer approach. 5

Define approximation algorithms for a problem P. How do you characterize approximation algorithms ? 5

State an algorithm to find a minimum*cost path from source to shrink in a multistage graph, dsing backward approach using dynamic programming paradigm. 5

What is brtuie-force method ? Write a brute-force string matching algorithm. Analyze its complexity. 5

Define subset paradigm and ordering paradigm in the context of greedy approach. Write a greedy algorithm for solving the 0-1 knapsack problem. 5

Explain the Boyer-Moore algorithm for siring matching to match a pattern p in a given string T, 5

Write an recursive algorithm for quick sort to. Show that time complexity of, average case of quick sort is T (nj = 0(n log n); with instance characteristic n.

5

Discuss the working of FIFO BANCH AND BOUND algorithm, considering 4-queer problem, 5

Explain I he role of a criteria function in problem solving process with backtracking algorithm. Suggest the structure of a recursive backtracking algorithm, 5

(b) Write an algorithm to compute shortest path on a weighted, undirected, and connected graph, Comment on complexity of the algorithm, 5

7. Describe and justify KmsKal's algorithm

for finding the minimum spanning tree of an undirected graph. What is the time complexity of KruskaPs algorithm ? 5

(b) What are the four factors that decides the efficiency of the Backtracking Algorithm? Explain the role of rearrangement of search space in performance of Backtracking.

iWl

5

8. (a)' Arrange the following functions from the

lowest asymptotic order to the highest asymptotic order;

1Qn, log n, 2^na, 5n²* 2 log n, eⁿ - 2n³, 7 log n² 2.5

PCS 3001 5 P.T.O.

(b) Suppose you jnsert n numbers into an initially empty priorrty Queue (Imple-merged as a heap), what is the worsi-case running time ? 2.5

(c) Let G toe a weighted, undirected, connected graph with n vertices and el most 100 n edges, where all the edges have,the same weight. Given two vertices u and v in G_J( how fast can you, find a shortest path from'u to v ? 2.5

(d) What Is the solution of the recurrenc T(n)'= 16T(r\/4) + n, T(1)=1 (assuming n is a power of 4) ? 2.5

IWL