(SEM V) THEORY EXAMINATION 2022-23 DESIGN & ANALYSIS OF ALGORITHM

Course: B.Tech (Semester V)                                                     Subject Code: KCS-503

Subject Name: Design & Analysis of Algorithm                      Time: 3 Hours

Total Marks: 100

Note: Attempt all sections. If data is missing, assume suitably. 

 Section A – Short Answer Questions (2 × 10 = 20 Marks)

Answer all briefly:

Basic steps in the development of an algorithm.

Compare best and worst time complexity of Quick Sort.     Discuss Skip List and its operations.

Properties of Binomial Trees.                                                 Applications of the Graph Coloring Problem.

Define the Principle of Optimality.              Differentiate between Backtracking and Branch and Bound.

Explain the backtracking problem-solving approach.

Define NP, NP-Hard, NP-Complete problems with examples.

Explain Randomized Algorithms. 

Section B – Descriptive Questions (10 × 3 = 30 Marks)

Attempt any three:

Explain Merge Sort algorithm and sort the sequence {23, 11, 5, 15, 68, 31, 4, 17}.

Difference between Binomial Heap and Fibonacci Heap.

Prove that distinct edge weights in a connected graph yield a unique Minimum Spanning Tree (MST). Explain Kruskal’s Algorithm.

Discuss the Longest Common Subsequence (LCS) algorithm with time complexity.

Apply Naïve String Matching on pattern P = aab and text T = acaabc. 

Section C – Long Answer Questions (10 × 5 = 50 Marks)

Q3

(a) Solve recurrence relations:

T(n)=T(n−1)+n4T(n) = T(n-1) + n^4T(n)=T(n−1)+n4

T(n)=T(n/4)+T(n/2)+n2T(n) = T(n/4) + T(n/2) + n^2T(n)=T(n/4)+T(n/2)+n2
or
(b) Explain Counting Sort Algorithm and apply it to array {0,1,3,0,3,2,4,5,2,4,6,2,2,3}.

Q4

(a) Insertion cases in a Red-Black Tree for {15,13,12,16,19,23,5,8} and show that height ≤ 2log(n+1).
or
(b) Write algorithm for Union of Two Binomial Heaps and its time complexity.

Q5

(a) Explain Greedy Algorithm. Write pseudocode to prove Fractional Knapsack problem satisfies the greedy-choice property.
or
(b) Define Single Source Shortest Path and write Dijkstra’s Algorithm.

Q6

(a) Solve Subset Sum Problem using recursive Backtracking for
w=5,7,10,12,15,18,20w = {5,7,10,12,15,18,20}w=5,7,10,12,15,18,20, m=35m = 35m=35. Draw the State Space Tree.
or
(b) Explain N-Queen Problem, and solve 4-Queen Problem using backtracking.

Q7

(a) Explain String Matching Algorithm and Rabin-Karp Method with examples.
or
(b) Define Approximation Algorithm. Discuss the Set Cover Problem using it.