55101-mt----design And Analysis Of Algorithms

NR

Code No: 55101/MT M.Tech. – I Semester Supplementary Examinations, September, 2008 DESIGN AND ANALYSIS OF ALGORITHMS (Common to Computer Science & Engineering/ Computer Science) Time: 3hours

Max. Marks:60 Answer any FIVE questions All questions carry equal marks ---

1.a) b) c)

Explain the general method of divide and conquer. Write Merge sort algorithm using links. Estimate the time-complexity of the above algorithm.

2.a)

Write union and Find algorithms that use weighting rule and collapsing rule respectively for disjoint sets. Using the above representation for disjoint sets, write an algorithm for job sequencing with dead lines.

b) 3.a) b) 4.a) b) c)

5.a) b)

Write and explain Prim’s Algorithm to generate a minimum cost spanning tree. Estimate the time complexity of the above algorithm. Write a non recursive procedure for the post order traversal of a given binary tree. Define a B-tree of order m. Compare the performance of the following search trees for insertion, deletion and searching operations: i) AVL trees ii) B-trees. Write an algorithm for finding the minimum cost binary search tree. Using the above algorithm compute w(i,j), r(i,j) and c(i,j), 0≤i≤j≤4, for the identifier set (a1, a2, a3, a4)=(cout , float, if, while) with p (1) = 1 , p (2) = 1 , p (3) = 1 , p (4) = 1 , 20 5 10 20 q (0) = 1 , q (1) = 1 , q (2) 1 , q (3) = 1 , q (4) = 1 . 5 10 5 20 20 Using the r(i, j)’s construct the optimal binary search tree.

( ) ( )

( ) ( )

( ) ( ) ( ) ( ) ( )

Contd…2.,

Code No: 55101/MT 6.a) b) 7.a)

b) 8.

::2::

Write a backtracking algorithm to find all the Hamiltonian cycles of a graph. Determine the order of magnitude of the worst-case computing time for the backtracking procedure that finds all Hamiltonian cycles. Write a C++ program that overloads + and suitable relational operators (<, > etc) to perform the following operations on two strings: i) Concatenation ii) Comparison. Write a C++ program that demonstrates how exceptions are handled. Write a) b) c)

notes on the following: Amortized analysis Principle of optimality for Travelling Salesman Problem. Non-deterministic Algorithms.

x-x-x