Roll No. Total No.
of Pages : 03
Total No. of Questions : 09
MCA (Sem–2)
DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code : PGCA-1920
M.Code : 79616
Date of Examination : 21-11-2023
Time : 3 Hrs. Max. Marks : 70
INSTRUCTIONS TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying T WO marks
each.
2. SECTION - B & C. have FOUR questions each.
3. Attempt any FIVE questions from SECTION B & C carrying T EN marks each.
4. Select atleast T WO questions from SECT ION - B & C.
SECTION-A
1) Answer briefly :
a. Define Recursion.
b. Explain divide and conquer method.
c. State Heap sort with example.
d. What is lower bound on sorting?
e. How does the time complexity of splitting/dividing an array vary with size of the
array?
f. Given an array arr = {15, 16, 27, 38, 59} and key = 38; How many iterations are done
until the element is found? Show the steps.
g. An array containing the elements 6,5,4,3,2,1 needs to be sorted. Out of merge sort and
quick sort, which one is the best sorting algorithm in this case? Why?
h. In what manner is a state-space tree for a Branch and Bound algorithm constructed?
i. What happens when the backtracking algorithm reaches a complete solution?
j. Write the complexity of of the recurrence relation T(n)=T( )+l.
1 | M-79616 (S6)- 359
SECTION-B
2. What are algorithms? What do you mean by polynomial time complexity and logarithmic
complexity? Which one is higher? What is the smallest value of n such that an algorithm
whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the
same machine?
3. a. f(n)=3nvn g(n)=2vnlog n prove that f(n)=O(g(n)).
b. Analyze the running time of the following recursive pseudo-code as a function of n.
Void function(int n){
if (n<2) return;
else counter = 0;
for I = l to 8 do
function(n/2);
3
for I = l to n do
counter = counter +1;
}
4. Explain two real life scenario of dynamic programming. How can the optimal solution to
the 0-1 knapsack problem be found with Dynamic Programming? Explain in brief
characteristics of dynamic algorithms. Explain how to find Longest Common Subsequence
of two strings using Dynamic Programming Method?
5. Explain partial 0/1 Knapsack problem. A thief enters a house for robbing it. He can carry a
maximal weight of 60 kg into his bag. There are 5 items in the house with the following
weights and values. Which items should thief take if he can even take the fraction of any
item with him?
Item Weight Value/Profit
1 5 30
2 10 40
3 15 45
4 22 77
5 25 90
2 | M-79616 (S6)- 359
SECTION-C
6. Write the algorithm of quick sort. Find worst case complexity of it using iterative method.
7. Write Dijkstra's algorithm. Output the sequence of vertices identified by the Dijkstra's
algorithm for single source shortest path when the algorithm is started at node s for the
given weighted directed graph.
8. a. What are NP, P and NP-complete problems?
b. State the difference between internal sorting and external sorting.
9. Which algorithmic approach traverses the state space tree only in DFS manner? Why?
Justify your answer with the help of an example.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
3 | M-79616 (S6)- 359
