BTech/ M.

Tech (Integrated) DEGREE EXAMINATION, MAY 2024

Fourth Semester

21CSC204J- DESIGN AND ANALYSIS OF ALGORITHMS

(For the candidates admited from the academic year 2022-2023 onwards)
Note:
() Part - A should be answered in OMR sheet within first 40 minutes and OMR sheet
should be handed
over to hall invigilator at the end of 40 minute.
(i) Part - B and Part -C should be answered in answer booklet.

Time: 3 Hours Max. Marks: 75

PART A (20 x 1= 20Marks) Marks BL CO PO

Answer ALL Questions

1. of the algorithm is the function defined by the minimum number of 1 11
steps taken on any instance of size n.
(A) Worst-case complexity (B) Best-case complexity
(C) Average-case complexity (D) Average-best case complexity
2. Compute the time complexity for the following code: 3 1 2

sum = 0;
for (i =0; i<n; itt)
for (j = 0;j<n; jt)
sum +:
(A) O(n) (B) O(n log n)
(C) O (og n) (D) O(n²)
3. Which of the following is linear asymptotic notations?
(A) O(1) (B) O(log n)
(C) O
(n) (D) O(n log n)

4. The master theorem

(A) Assumes the subproblems are (B) Can be used if the subproblems
unequal sizes are of equal sizes
(C) Cannot be used for divide and (D) Cannot be used for asymptotic
conquer algorithms complexity analysis
5. Merge sort uses which of the following technique to implement sorting? 1 2 2
(A) Back tracking (B) Greedy algorithm
(C) Divide and conquer (D) Dynamic partitioning
6. What is the recurence relation used in Strassen's matrix multiplication? I1 2 2

(A) 77u 2) +0u²) (B) 8Tn 2)+0n-)

(C) 7Tn/2) +0(n²) (D) 8T(n/2) +0(12)
13 2 2
7. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1,-2, -l, 5, -4}
(A) 3 (B) 5
(C) 8 (D) 6
Page 1 of 4 16MA4-21CSC204J
 1 2 1
8. The time taken to find the n' points that lie in a convex hull is
(A) O(n) (B) O(n log n)
(C) O(n) (D) O(log n)
3 3 3
9. Using Huffman coding, compute the codeword for character 'a' in the given
tree.

(A) 010 (B) 100

(C) 011 (D) 101
2 3 2
10. Which of the following is false in the case of a spanning tree of a graph G?
(A) It is tree that spans G (B) It can be either cyclic or acyclic
(C) It is a subgraph of G (D) It includes every vertex of G
1 2 3 2
11. Which of the following can be solved using dynamic programming?
(A) Merge sort (B) Binary search
(C) Longest common subsequence (D) Quick sort
3 3 2
12. Consider the matrices P, Q and R which are 10x20, 20x30 and 30x40
matrices respectively. What is the minimum number of multiplications
required to multiple the three matrices?
(A) 12000 (B) 18000
(C) 24000 (D) 32000
1 2 4 2
13. What happens when a backtracking algorithm reaches a complete solution?
(A) It backtracks to the root (B) It continues searching for the
other possible solutions
(C) It traverses from a different (D) Recursively traverses through
route the same route

14. Travelling salesman problem is an example of 1 1 4I

(A) Divide and conquer (B) Recursive approach
(C) Dynamic algorithm (D) Greedy algorithm
15. A person wants to visit some places. He starts from a vertex and then wants 1 4 4 1
to visit every place connected to this vertex and so on. What algorithm the
should use?
(A) Breadth first search (B) Depth first search
(C) Prim's algorithm (D) Kruskal's algorithm

16. In what time can the Hamiltonian path problem can be solved using dynamic 1 4I
programming?
(A) O(N) (B) O(N)
(C) 0(N? 2N) (D) 0(N log N)

17. What is the purpose of usingrandomized quick sort over standard quick sort? 2

(A) To avoid worst case time (B) To avoid worst case space
complexity complexity
(C) To improve average case time (D) To improve accuracy of output
complexity
Page 2 of 4 16MA4-21CSC204J
 18. Pick the correct basic principle in Rabin Karp algorithm. 1 1 5 2
(A) Sorting (B) Augmenting
(C) Dynamic programming (D) Hashing
19. is the class of decision problems that can be solved by non
deterministic polynomial algorithm.
(A) NP (B) P
(C) NP-hard (D) NP-Complete
20. Under what condition any set A will be a subset of B? 1
(A) If all elements of set B are also (B) If all elements of set A are also
present in set A present in set B
(C) If A contains more elements (D) IfB contains more elements than
than B A

PART -B (5 x 8 =40 Marks) Marks BI CO PO

Answer ALL Questions

21. a. Solve the following recurrence relation and compute the time complexity 3 3

() T(n)=2T(n|2)+cn 4
(ii) T(n) =2T(n-1)+c

(OR)
3 1 2
b. Write the algorithm of insertion sort and trace the algorithm for the array 8

elements listed below.

arr []={21, 7, 12, 10, 6, 16, 24}
4 2 2
22. a. Apply mastered theorem and find the time complexity for the following
(i) T(n)=3T(2|2) +n2 2

(i) T(n)=4T(n|2) +n2 2

(ii) T(n)=16T(n|4)+n 2

(iv) T(n) =2" T(n|2) +n5 2

(OR)
b. Illustrate quick sort algorithm for the example given below and explain the 8 4 2 3
time comnplexity for best case, average case and worst case.
a []= {56, 26, 93, 17, 77, 31, 44, 55, 20}
23. a. Write the greedy fractional knapsack algorithm and solve the following 8 33 2
problem using knapsack algorithm,
Number of items :5
Sack capacity : 100
Value 20 30 66 40 60
|Weight 10 20 30 4050
(OR) 3 3 2
b. Construct the longest common subsequence table for the sequence
X={A, B, C, B, D, A, B} and Y= {B, D, C, A, B, A}

24. a. Write the algorithm for N-queen's problem and illustrate the same with
8 2 4 1

appropriate example for 4x4 board.

(OR)
16MA4-21CSC204J
Page 3 of4
 3 4 2
b. Obtain the transitive closure for the following digraph using Floyd-Warshall
algorithm.

8 1 5 1
25. a. Discuss the following terms with suitable example
(i) P (i) NP (ii) NP-complete (iv) NP-Hard problems
(OR) 8 4 5 2
b. What is Hamiltonian cycle? Explain the algorithm to find the Hamiltonian
cycle in a given connected graph.

PART C(1x15= 15 Marks) Marks BL CO PO

Answer ANY ONE Question

15 33 3
26. Considerthe following cityscape challenge. Imaginea miniature archipelago
of seven islands (lets name them A thro G). The local government want to
build bridges between there islands to ensure connectivity. However, the
cost of bridge construction varies based on the distance and the terrain
between each pair of islands. Apply minimum spanning tree (Prim's
IKruskal's) algorithms and devicea optimal solution for the problem.
|Island connections Cost
A-B 7
A-D 5
B-C
B-D 9
B-E
C-E
D-E 15
D-F 6
E-F 8
E-G 9
F-G 1]
1s 3 4 3
27. A fruit seller visited a street in a city. He started selling various fruits to
people who live there. A buyer bought 1 kg of apple and 2 kgs of oranges
for rupees 90 and 70 respectively. The buyer gave 200 rupees to the fruit
seller. And he is waiting for the seller to give the remaining amount to him.
Seller is having the following denomination of coins with him. Device a
subset sum algorithm to help the fruit seller to reader the exact change to the
buyer.
Denomination of coins Count of coins
7

5
10

Page 4 of 4 16MA4-21CSC204J