[Link].
/ CSE / R16 / EVEN / SEM-4 / CS402 / 2020-2021
DESIGN AND ANALYSIS OF ALGORITHMS
CS402
TIME ALLOTTED: 3 HOURS FULL MARKS: 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words as far as practicable
GROUP – A
(Multiple Choice Type Questions)
1. Answer any ten from the following, choosing the correct alternative of each question: 10×1=10
Marks CO No.
(i) Fractional knapsack problem is solved most efficiently by which of the 1 4
following algorithm?
a) Divide and conquer
b) Dynamic programming
c) Greedy algorithm
d) Backtracking
(ii) Kruskal’s algorithm is used to ______ 1 4
a) find minimum spanning tree
b) find single source shortest path
c) find all pair shortest path algorithm
d) traverse the graph
(iii) Consider the two matrices P and Q which are 10 x 20 and 20 x 30 1 5
matrices respectively. What is the number of multiplications required
to multiply the two matrices?
a) 10*20
b) 20*30
c) 10*30
d) 10*20*30
(iv) Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is 1 5
the length of the longest common subsequence?
a) 9
b) 8
c) 7
d) 6
Page 1 of 5
[Link]. / CSE / R16 / EVEN / SEM-4 / CS402 / 2020-2021
(v) Dijkstra’s Algorithm is used to solve _____________ problems. 1 4
a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting
(vi) Which algorithm is used to solve a maximum flow problem? 1 1
a) Prim’s algorithm
b) Kruskal’s algorithm
c) Dijkstra’s algorithm
d) Ford-Fulkerson algorithm
(vii) The worst-case time complexity of merge sort- 1 3
a) O (log n)
b) O (nlogn)
c) O (n)
d) O (n2)
(viii) The main objective of Ford-Fulkerson algorithm is to find out 1 3
a) Maximum flow of a network
b) traversal of a network
c) single source shortest path of a network
d) all pair shortest path of a network
(ix) Express the formula (n-1) * (n-5) in terms of big O notation 1 3
a) O (1)
b) O (log n)
c) O(n)
d) O(n2)
(x) The time taken by linear search algorithm to search a key in a sorted 1 3
array of n elements
a) O (log n)
b) O (n)
c) O (nlogn)
d) O (n2)
Page 2 of 5
[Link]. / CSE / R16 / EVEN / SEM-4 / CS402 / 2020-2021
(xi) What approach is being followed in Floyd Warshall Algorithm? 1 1
a) Greedy technique
b) Dynamic Programming
c) Linear Programming
d) Backtracking
(xii) For the following program, calculate Big O analysis of the running 1 5
time (in terms of n)
For (i=0; i<n; i++)
A[i] = c ++ ;
a) O(n-1)
b) O(n)
c) O(n2)
d) O(log n)
GROUP – B
(Short Answer Type Questions)
Answer any three from the following: 3×5=15
Marks CO No.
2. Solve the following recurrences: 5 5
(i) T (n) = 2T (n/2) + Ɵ (n)
(ii) T (n) = T (n/2) + Ɵ (1)
3. Derive the worst-case time complexity of merge sort. 5 3
4. Given items as {value, weight} pairs {{40,20}, {30,10}, {20,5}}. The 5 5
capacity of knapsack=20. Find the maximum value output assuming
items to be divisible.
5. Find the complexity of the function f(x)=8n3 +3n2 + 2 in Big-O and 5 3
little-O notation.
6. Write the pseudo code for Floyds warshall algorithm. 5 2
Page 3 of 5
[Link]. / CSE / R16 / EVEN / SEM-4 / CS402 / 2020-2021
GROUP – C
(Long Answer Type Questions)
Answer any three from the following: 3×15=45
Marks CO No.
7. (a) Consider the graph G = (V, E) given below--- 5 5
8 7
9
4 b c d
2 9
a 11 4 e
7
i 6 f
8 10
h
2
g
1
Find the minimum cost spanning tree by Prim’s algorithm.
(b) Find an optimal parenthesizing of a matrix chain product whose 7 2
sequence of dimensions are {10, 20, 10, 5} and find the number of
multiplications.
(c) which one is better between Binary Search and Linear Search, and 3 4
why?
8. (a) Derive the worst-case complexity of Dijkstra Algorithm. 5 3
(b) Explain Maxflow-mincut theorem. 5 1
(c) What do you mean by Amortized Analysis? 5 1,4
9. (a) Define NP-Complete and NP-Hard. 4 3
(b) What is the relationship among P-class, NP-Class, NP-Complete and 4 3
NP-Hard?
(c) 7 5
Find out the maximum profit.
Jobs J1 J2 J3 J4 J5
Profits 20 15 10 5 1
Deadlines 2 2 1 3 3
Page 4 of 5
[Link]. / CSE / R16 / EVEN / SEM-4 / CS402 / 2020-2021
10. (a) What do you mean by max heap and min heap? 4 1
(b) Write pseudo code for constructing Max heap. 5 4
(c) Derive the complexity of Heap sort algorithm. 6 3
11. (a) Define Augmenting path, sink and Residual network. 2+2+2 1
(b) State two graph traversal algorithms. 2 3
(c) Apply any one graph traversal algorithm on the above graph. 7 5
B F
C
A
H
D
E
G
Page 5 of 5
