12/7/2020

B.Tech - Odd Sem : End Semester Exam

Academic Year:2020-2021
18CS2207A - Analysis & Design of Algorithms
Set No: 3
Time: Max.Marks: 100

S.NO Answer All Questions Choice Options Marks CO

a) Write an algorithm to find third largest element in the given list. b) Write an algorithm to determine if a number n is
"happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the
choice
1. number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or 10Marks CO1
Q-2
it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Return True if n is a happy number, and False if not.
2. How to sort the given list using quick sort 70, 25, 3, 5, 12, 34, 45, 30, 8 10Marks CO1
a) Calculate space and time complexity for the following algorithm Algorithm BubbleSort(A,n) { for i:=1 to n do { x:=A[i];
choice
3. j:=i; while j>0 and A[j-1]> x do: A[j]:=A[j-1]; j:=j-1; end while A[j]:=x; end for } b) Compare and contrast Big Oh, Theta 15Marks CO1
Q-4
and Omega notation.
Generally matrix multiplication is possible in O(n^3) Multiply the following matrices in less than O(n^3).Consider the
4. following matrices and Explain step by step procedure to find the multiplication. A=[1 1 1 1, 1 1 1 1, 1 1 1 1, 1 1 1 1] and 15Marks CO1
B=[1 0 0 0, 0 1 0 0, 0 0 1 0, 0 0 0 1]
Find the optimal solution for the fractional knapsack problem making use of greedy approach with algorithm in step wise
manner. The knapsack has capacity of holding 20 items.

choice
5. 10Marks CO2
Q-6

State the utility of Huffman Code. What is the Huffman Code for the following set of frequencies? a: 1 b:1 c:2 d:3 e:5 f:8
6. 10Marks CO2
g:13 h:21
(a) Define MST. Find MST by Prim’s algorithm State and justify time complexity of Prim’s Algorithm. (b)Dijkstra’s
Algorithm cannot be applied on ______________ Justify your answer.

choice
7. 15Marks CO2
Q-8

Construct minimum cost spanning tree using prims and kruskals algorithm for the following graph

8. 15Marks CO2

9. Solve the following 8-puzzle problem using LC Search. choice 10Marks CO3
Q-10
1/3
12/7/2020

10. Prove (3,1,4,2) provides an optimal solution for 4-queens problem and draw the state space tree? 10Marks CO3
choice
11. Apply backtracking to solve the knapsack problem when n=4,w={ 2, 3, 4, 5} ,p={ 3, 5, 6, 10} and m=8. 15Marks CO3
Q-12
12. Solve the following instance of Traveling Salesperson Problem using Branch and Bound method 15Marks CO3

2/3
12/7/2020

choice
13. Draw an example of a graph with 10 vertices and 15 edges that has a clique of size 6. 10Marks CO4
Q-14
14. Compare and contrast sequential and parallel machine with an example. 10Marks CO4
Analyze by applying the Rabin-karp algorithm for the following pattern and text. Pattern P = 5623 Text T = choice
15. 15Marks CO4
125645781278756281234562394 Q-16
16. List the sorted elements for the following numbers using PRAM merging 17,45,67,23,12,7,37,78,54,29,11,22,56,95,17,20 15Marks CO4
[object HTMLDivElement]

3/3