(SEM V) THEORY EXAMINATION 2023-24 DESIGN AND ANALYSIS OF ALGORITHM

Total Marks: 100

Time: 3 hours

Structure:

Section A: 10 short answer questions (all compulsory) – 2 marks each

Section B: Any 3 questions – 10 marks each

Q3–Q7: Each has two alternatives (a or b) – attempt one part from each

SECTION A – Very Short Questions (2 × 10 = 20)

Attempt all:

a. What do you mean by algorithm? Write the characteristics of an algorithm.

b. Show that the equation is correct:

10n2+9=O(n2)10n^2 + 9 = O(n^2)10n2+9=O(n2)

c. Write a short note on Fibonacci Heap.

d. Explain Binary Search Tree.

e. Define fractional Knapsack problem.

f. Write the names of spanning tree algorithms with their time complexities.

g. Define the term “Graph Coloring”.

h. What do you mean by Activity Selection problem?

i. What do you mean by Boyer–Moore Algorithm?

j. Write a short note on Fast Fourier Transform (FFT).

SECTION B – Short/Medium Questions (Attempt any 3) (10 × 3 = 30)

a. Counting Sort
Sort the array using counting sort:

A={2,5,3,0,2,3,0,3}A = \{2, 5, 3, 0, 2, 3, 0, 3\}A={2,5,3,0,2,3,0,3}

b. Binomial Tree
Prove all four properties of a Binomial Tree.

c. Depth First Search (DFS)

Describe DFS with its algorithm.

Explain how DFS can be used to solve a problem (e.g., topological sort, connectivity).

d. Floyd–Warshall Algorithm
Apply Floyd–Warshall algorithm to construct all-pairs shortest paths for the weighted directed graph given in the figure on page 1 (a 5-vertex graph labeled a–e with positive and negative edge weights like 3, 2, −4, 1, 6, etc.). 

KCS503-DESIGN-AND-ANALYSIS-OF-A…

e. Short notes:

Randomized Algorithm

Approximation Algorithm

Question 3 – Sorting (Attempt any 1 part) (10 marks)

a. What is a stable sorting algorithm?

Which sorting algorithms you have studied are stable and which are unstable?

Give names with explanation.

b. Write the algorithm of Merge Sort and prove its worst-case time complexity.

Question 4 – Balanced Trees & B-Trees (Attempt any 1 part) (10 marks)

a. Red-Black Tree Insertion
Insert the following elements using the properties of RB tree:

61,58,51,32,39,2961, 58, 51, 32, 39, 2961,58,51,32,39,29

b. B-Tree
Explain B-Tree and its properties. Also write B-Tree deletion cases with example.

Question 5 – Dynamic Programming & Backtracking (Attempt any 1 part) (10 marks)

a. Determine a Longest Common Subsequence (LCS) of

X={A,B,C,B,D,A,B}X = \{A, B, C, B, D, A, B\}X={A,B,C,B,D,A,B} Y={B,D,C,A,B,A}Y = \{B, D, C, A, B, A\}Y={B,D,C,A,B,A}

b. Explain Backtracking. For the set

S={1,3,4,5},X=8S = \{1, 3, 4, 5\}, \quad X = 8S={1,3,4,5},X=8

solve the Subset Sum problem using a backtracking approach.

Question 6 – Graph Algorithms & Branch & Bound (Attempt any 1 part) (10 marks)

a. Write an algorithm for Dijkstra’s algorithm and implement it by taking any example graph (single-source shortest path with non-negative weights).

b. Apply Branch and Bound to solve the Travelling Salesman Problem (TSP) for the graph with the following cost matrix (shown as a 5×5 table on page 2, diagonal entries = ∞): 

KCS503-DESIGN-AND-ANALYSIS-OF-A…

[∞1713221813∞1624191518∞1628191315∞2128241918∞]\begin{bmatrix} \infty & 17 & 13 & 22 & 18 \\ 13 & \infty & 16 & 24 & 19 \\ 15 & 18 & \infty & 16 & 28 \\ 19 & 13 & 15 & \infty & 21 \\ 28 & 24 & 19 & 18 & \infty \end{bmatrix}​∞13151928​17∞181324​1316∞1519​222416∞18​18192821∞​​ 

Question 7 – Complexity Classes & String Matching (Attempt any 1 part) (10 marks)

a. Explain P, NP, NP-Hard and NP-Complete classes with suitable examples.

b. Explain the KMP matcher and also implement it by an algorithm for:

Pattern P=a,a,b,a,b,b,aP = a, a, b, a, b, b, aP=a,a,b,a,b,b,a

Text T=b,a,b,a,a,b,a,b,b,aT = b, a, b, a, a, b, a, b, b, aT=b,a,b,a,a,b,a,b,b,a