Jawaharlal Nehru Technological University Hyderabad 2007 M.C.A Computer Aplications DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

1.a) explain various types of time complexities for analyzing an algorithm.
b) Write a procedure which obtains the mode and frequency of an unsorted array. Analyze its computing time. Is your method better than sorting.
2. Let u and v be 2 n bit numbers where for simplicity n is a power of 2. A divide and conquer strategy splits the numbers into 2 equal parts, computing the product as
uv = (a 2n/2+b) (c 2n/2+d) = ac 2n+(ad+bc)2n/2+bd
The multiplications ac, ad, bc and bd are performed recursively using the above method.
(a) Determine the computing time of the above method.
(b) What is the computing time if ad+bc is calculated as (a+b) (c+d)-ac-bd?
3.a) Draw the optimal 3-way merge tree for (3,7,8,9,15,16,18,20,23,25,28).
b) By considering the complete graph with n vertices show that the number of spanning trees in an n vertex graph can be greater than 2n-1-2.
4. describe travelling sales person issue. Write an algorithm for TSP using Dynamic programming technique. explain its time complexity.
5. The diameter of a tree is the maximum distance ranging from any 2 vertices. Let d be the diameter of a minimum diameter spanning tree for an undirected graph G. Let r be the radius of minimum radius spanning tree for G.
(a) Show that 2r-1=d=2r.
(b) Write an algorithm to obtain a minimum diameter spanning tree for G.
6. provided an n×n chess board, a knight is placed on an arbitrary square with coordinates (x,y). The issue is to determine n2-1 knight moves show that every square of the board is visited once if such a sequence of moves exists. Write an algorithm to solve this issue.
7. Write a LC branch and bound algorithm for knapsack issue using fixed triple size formulation and the dynamic state space tree.
8. Write short notes on:
(a) Non-deterministic algorithm (b) Union and obtain principle
(c) Cook’s theorem

Earning:   Approval pending.