(SEM V) THEORY EXAMINATION 2019-20 DESIGN AND ANALYSIS OF ALGORITHM

DESIGN AND ANALYSIS OF ALGORITHMS (RCS-502)

B.Tech (SEM-V) – AKTU

SECTION A

(Attempt all questions – 2 × 7 = 14 marks)

Q1 (a) How do you compare the performance of various algorithms?

The performance of algorithms is compared using time complexity and space complexity. Time complexity measures how execution time grows with input size, while space complexity measures memory usage. Asymptotic notations like Big-O, Omega, and Theta are used to analyze performance independent of hardware.

Q1 (b) Arrange the given functions in ascending order of growth rate.

Given:
f₁(n) = n²
f₂(n) = √2ⁿ
f₃(n) = n + 10
f₄(n) = 10n
f₅(n) = 100n
f₆(n) = n² log n

Ascending order of growth rate is:
n + 10 < 10n < 100n < n² < n² log n < √2ⁿ

Q1 (c) What is the advantage of binary search over linear search? Also state limitations.

Binary search is faster than linear search because it reduces the search space by half at each step, giving time complexity O(log n). However, it requires sorted data and is not suitable for linked lists or unsorted collections.

Q1 (d) What are greedy algorithms? Explain their characteristics.

Greedy algorithms make locally optimal choices at each step to reach a global solution. They are simple, efficient, and easy to implement but do not always guarantee optimal solutions for all problems.

Q1 (e) Explain applications of FFT.

FFT is used in signal processing, image processing, convolution, polynomial multiplication, and fast computation of discrete Fourier transforms.

Q1 (f) Define feasible and optimal solution.

A feasible solution satisfies all problem constraints.
An optimal solution is the best among all feasible solutions according to the objective function.

Q1 (g) What do you mean by polynomial time reduction?

Polynomial time reduction is a method of transforming one problem into another in polynomial time. It is used to compare computational complexity and prove NP-completeness.

SECTION B

(Attempt any three – 7 × 3 = 21 marks)

Q2 (a) (i) Solve the recurrence: T(n) = 2T(n/2) + n² + 2n + 1

Using Master Theorem:
a = 2, b = 2, f(n) = n²

Since f(n) = Ω(n¹⁺ε), Case 3 applies.
Therefore, T(n) = Θ(n²).

Q2 (a) (ii) Prove that worst-case running time of any comparison sort is Ω(n log n).

Any comparison sort requires distinguishing between n! permutations.
Using decision tree model, height ≥ log₂(n!).
By Stirling’s approximation, log(n!) ≈ n log n.
Hence, worst-case time is Ω(n log n).

Q2 (b) Explain Merge Sort algorithm and analyze its time complexity.

Merge sort uses divide-and-conquer strategy. The array is divided into halves, sorted recursively, and merged.
Its time complexity in all cases is O(n log n).

Q2 (c) Explain Quick Sort algorithm and its time complexity.

Quick sort selects a pivot, partitions elements, and recursively sorts subarrays.
Best and average case complexity is O(n log n), while worst case is O(n²).

SECTION C

(Attempt any two – one from each unit, 7 × 2 = 14 marks)

Q4 (a) Using minimum degree t = 3, insert given keys into B-Tree and find number of split operations.

Keys:
10, 25, 20, 35, 30, 55, 40, 45, 50, 55, 60, 75, 70, 65, 80, 85, 90

For minimum degree t = 3, maximum keys per node = 5.
During insertion, nodes split whenever keys exceed limit.
Total number of split operations = 5 (as per insertion process).

Q5 (a) Solve 0/1 Knapsack problem using Dynamic Programming.

Given:
Profit P = {11, 21, 31, 33}
Weight W = {2, 11, 22, 15}
Capacity C = 40

Using DP table construction, the maximum profit obtained is 65 by selecting items with profits 21 and 33 and 11.