(SEM V) THEORY EXAMINATION 2018-19 DESIGN & ANALYSIS OF ALGORITHMS

DESIGN AND ANALYSIS OF ALGORITHMS (RCS-502)

B.Tech (SEM-V) – AKTU
                                                                                                    Time: 3 Hours  Total Marks: 70

SECTION A

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

Q1 (a) Rank the following by growth rate:

n2k,  nlog⁡n,  log⁡(log⁡n),  log⁡n,  log⁡2(log⁡2n),  4,  3(2n),  n!n^2k,\; n\log n,\; \log(\log n),\; \log n,\; \log_2(\log_2 n),\; 4,\; 3(2^n),\; n!n2k,nlogn,log(logn),logn,log2​(log2​n),4,3(2n),n!

Growth rate in increasing order is:

4<log⁡(log⁡n)<log⁡2(log⁡2n)<log⁡n<nlog⁡n<n2k<3(2n)<n!4 < \log(\log n) < \log_2(\log_2 n) < \log n < n\log n < n^2k < 3(2^n) < n!4<log(logn)<log2​(log2​n)<logn<nlogn<n2k<3(2n)<n!

This ranking helps compare time complexities of algorithms.

**Q1 (b) Prove that if n≥1n \ge 1n≥1, then for any n-key B-Tree of height h and minimum degree t≥2t \ge 2t≥2,

h≤log⁡tn+12h \le \log_t \frac{n+1}{2}h≤logt​2n+1​.**

In a B-Tree of minimum degree ttt, the minimum number of keys increases exponentially with height.
At height hhh, the minimum number of keys is:

n≥2th−1n \ge 2t^h - 1n≥2th−1

Rearranging,

h≤log⁡tn+12h \le \log_t \frac{n+1}{2}h≤logt​2n+1​

Thus, the height of a B-Tree grows logarithmically with number of keys.

Q1 (c) Define principle of optimality. When and how is dynamic programming applicable?

The principle of optimality states that an optimal solution of a problem contains optimal solutions of its subproblems.
Dynamic programming is applicable when a problem has overlapping subproblems and optimal substructure. It is used by solving subproblems once and storing their results.

Q1 (d) What is the difference between divide-and-conquer and dynamic programming?

Divide-and-conquer solves independent subproblems recursively.
Dynamic programming solves overlapping subproblems and stores intermediate results to avoid recomputation, making it more efficient.

Q1 (e) Define amortized analysis.

Amortized analysis is a technique to analyze the average time per operation over a sequence of operations, even if some operations are costly. It gives a more realistic performance measure.

Q1 (f) What is greedy algorithm? Give one example.

A greedy algorithm makes the locally optimal choice at each step hoping to find the global optimum.
Example: Kruskal’s algorithm for minimum spanning tree.

Q1 (g) What is NP-Complete problem?

An NP-Complete problem is a problem that is both in NP and NP-Hard. If any NP-Complete problem can be solved in polynomial time, all NP problems can be solved in polynomial time.

SECTION B

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

Q2 (a) Explain quick sort algorithm and analyze its time complexity.

Quick sort is a divide-and-conquer sorting algorithm. It selects a pivot element and partitions the array such that elements smaller than pivot are on one side and larger on the other. The process is recursively applied.

Best and average time complexity is O(n log n).
Worst-case time complexity is O(n²) when the pivot selection is poor.

Q2 (b) Explain merge sort algorithm with example.

Merge sort divides the array into two halves, recursively sorts each half, and then merges them.
It guarantees O(n log n) time complexity in all cases and is stable, but requires additional memory.

Q2 (c) Explain Dijkstra’s algorithm. State its limitation.

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph.
It repeatedly selects the vertex with minimum distance and relaxes its edges.

Limitation: It does not work with negative edge weights.

Q2 (d) Write a note on backtracking and branch and bound techniques.

Backtracking systematically searches solution space and abandons paths that violate constraints.
Branch and bound improves backtracking by using bounds to prune branches that cannot yield optimal solutions.

SECTION C

(Attempt any one part from each question – 7 × 2 = 14 marks)

**Q3 (a) Given recurrence

T(n)=7T(n/3)+n2T(n) = 7T(n/3) + n^2T(n)=7T(n/3)+n2.
Another algorithm has
S(n)=aS(n/9)+n2S(n) = aS(n/9) + n^2S(n)=aS(n/9)+n2.
Find smallest value of ‘a’ such that A is asymptotically faster than B.**

Using Master Theorem:

For A:

nlog⁡37≈n1.77n^{\log_3 7} \approx n^{1.77}nlog3​7≈n1.77

For B:

nlog⁡9an^{\log_9 a}nlog9​a

For A to be faster than B:

log⁡9a>log⁡37⇒a>91.77\log_9 a > \log_3 7 \Rightarrow a > 9^{1.77}log9​a>log3​7⇒a>91.77

Thus, the smallest integer value of a satisfying this condition is the required answer.

Q3 (b) Sort the array using heap sort:

A = {23, 9, 18, 45, 5, 9, 1, 17, 6}

Heap sort builds a max-heap from the array and repeatedly extracts the maximum element to sort the array.
Final sorted array is:

{1,5,6,9,9,17,18,23,45}\{1, 5, 6, 9, 9, 17, 18, 23, 45\}{1,5,6,9,9,17,18,23,45} 

Q4 (a) Explain union of two binomial heaps. Also write algorithm and its complexity.

Union of two binomial heaps is done by merging root lists in increasing order of degree and then linking trees of same degree.
Time complexity of union operation is O(log n).

Q4 (b) Insert 6, 20, 11, 14, 9, 4, 12 in a Red-Black Tree and delete 12, 4, 9, 14 respectively.

Insertion and deletion in Red-Black Tree follow BST rules with additional color fixing and rotations to maintain properties.
After each insertion and deletion, recoloring and rotations ensure tree remains balanced with O(log n) height.