09A51903 Design & Analysis of Algorithms B.Tech Question Paper : sphoorthyengg.com

Name of the College : Sphoorthy Engineering College
University : JNTUH
Department : Electronics And Computer Engineering
Subject Code/Name : 09A51903/DESIGN AND ANALYSIS OF ALGORITHMS
Year : December 2011
Degree : B.Tech
Year/Sem : III/I
Website : http://www.sphoorthyengg.ac.in/#/home
Document Type : Model Question Paper

Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/sphoorthyengg.com/4803-09A51903-DESIGNANDANALYSISOFALGORITHMS.pdf

Sphoorthy Design & Analysis of Algorithms Question Paper

III B.Tech I Semester Examinations,December 2011
Time: 3 hours
Max Marks: 75

Related : Sphoorthy Engineering College R05312203 OOPS Through JAVA B.Tech Question Paper : www.pdfquestion.in/4758.html

Answer any FIVE Questions :
All Questions carry equal marks :
1. (a) What is Dynamic Programming? Explain with suitable illustration.

(b) You are given a list of words, W1,W2,W3,…, Wn and their corresponding probabilities of occurrence p1,p2,p3,…,pn. The problem is to arrange these words in a binary search tree in a way that minimizes the expected total access time. Suggest a good algorithm to implement it. Also prove the complexity of the algorithm derived by you. [7+8]

2. (a) Explain set representation using trees and develop algorithms for UNION and FIND using weighing and collapsing rules.
(b) Define Articulation point. Illustrate with an example. [7+8]

3. (a) Draw the portion of state space tree generated by LCBB for the knapsack instances
n = 4; (P1; P2;P3 ; P4) = (10; 10; 12; 18); (w1w2;w3;w4) = (2;4; 6; 9 ) and M = 15
(b) Explain Least cost Search. [15]

4. (a) Let w = f6; 15; 20; 10; 11; 18; 29g and m=35. Find all possible subsets of w that sum to m. Draw the portion of the state space tree that is generated.
(b) Differentiate between Live node and E-node. [7+8]

5. The Fibonacci numbers are defined as f0 = 0 and f1=1 and fi= fi-1 + fi??2 for i >1. Write both recursive and iterative algorithm to compute fi. Also find their time complexities using step count method? [15]

6. (a) Let F(I) be the value of the solution generated on problem instance I by Greedy Knapsack when the objects are input in non decreasing order of the Wi(weights). Let E(I) be the value of an optimal solution for this instance. How large can the ratio E(I)/F(I) get?

(b) Find an Greedy optimal placement for 13 programs on three tapes T0,T1 and T2 where the programs are of lengths 12,5,8,32,7,5,18,26,4,3,11,10 and 6.[7+8]

7. (a) Compute 2101*1130 by applying Divide and Conquer method.
(b) Applying Divide and Conquer strategy, write a recursive algorithm for fifinding the maximum and the minimum elements from a list. [7+8]
8. (a) Show that Clique optimization problem reduces to the clique decision problem.

Set 2

1. Construct an optimal binary search tree for the following data: n=4, (a1,a2,a3,a4)= ( do, if, int, while), p(1:4)= ( 3,3,1,1) and q(0:4)= ( 2,3,1,1,1). [15]

2. (a) Explain Hamiltonian cycle.
(b) Write an algorithm to generate next color in m-coloring problem. [7+8]

3. Explain the P, NP, NP-Hard and NP- complete classes with suitable examples.[15]
4. Write a Weighted union algorithm. Trace the above algorithm. [15]
5. Write the LCBB algorithm for the 0/1 Knapsack problem. Also analyze its complexity. [15]

6. (a) Define:
i. Big oh notation
ii. Theta notation.
(b) Find Big oh notation and theta notation for the following functions:
i. 100n + 6
ii. 10 logn + 4. [7+8]

7. Explain the problem of Single Source Shortest Path Problem and write its algorithm using Greedy approach. Prove that it works with a numerical example. [15]

8. Devise a \binary” search algorithm that splits the set not into two sets of almost equal sizes but into two sets, one of which is twice the size of the other. How does this algorithm compare with binary search? [15]

Set 3

1. (a) Explain forward and backward approach of problem solving in Dynamic pro- gramming?
(b) Find an optimal solution to the 0/1 knapsack instance, given n=3, weights and projects as (w1,w2,w3)=(2,3,4) , p1,p2,p3)= (1,2,5) and knapsack capacity =6 generate the sets Si using dynamic programming. [7+8]

2. Write an algorithm to sort the elements using Mergesort. Trace the time complexity of the algorithm for the following elements. 310,285,179,652,351,423,861,254,450,520 [15]
3. (a) What makes a problem to fall into class NP?
(b) Explain the differences between decision and optimization problems. [7+8]

4. What is the value returned by each of the following functions? Express your answer as functions of n. Also, state the worst-case running times in big-O notation
(a) Function mystery(n)
i. r:=0;
ii. for i:=1 to n-1 do
iii. for j:=i+1 to n do
iv. for k:=1 to j do
v. r:=r+1;
vi. return(r).

(b) Function pensy(n)
i. r:=0;for i:=1 to n-1 do
ii. for j:=1 to i do
iii. for k:=j to i+j do
iv. r:=r+1;
v. return (r) [7+8]

5. (a) Find at least two instances of the n-Queens problem that have no solutions.
(b) Use the Backtracking algorithm for the m-Coloring problem to nd all possible colorings of the graph as shown in figure 1 using the three colors red, green and white. Show the actions step by step. [7+8]