B.TECH.

/ 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
 B.TECH. / 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
 B.TECH. / 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
 B.TECH. / 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
 B.TECH. / 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