JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (February/March - 2022 - R18)

The Optimal Binary Search Tree (OBST) algorithm constructs a binary search tree with minimum search cost given a set of keys and their associated probabilities. Let P[i] be the probability of searching for key i and Q[i] be the probability of searching for a value between keys i and i+1.

1. Initialize a cost table C[1..n+1, 0..n] and a root table R[1..n, 1..n] to zero.
2. For i = 1 to n, set C[i, i-1] = Q[i-1] and W[i, i-1] = Q[i-1].
3. For length L = 1 to n:
4. For i = 1 to n-L+1:
5. Set j = i+L-1.
6. Calculate W[i, j] = W[i, j-1] + P[j] + Q[j].
7. Find k in range [i, j] that minimizes C[i, k-1] + C[k+1, j].
8. Set C[i, j] = W[i, j] + min(C[i, k-1] + C[k+1, j]) and R[i, j] = k.

The average case time complexity of Quick Sort is derived using the recurrence relation T(n) = (n-1) + (1/n) ∑ [T(i-1) + T(n-i)] for i=1 to n, where (n-1) is the partitioning cost.

1. The recurrence simplifies to T(n) = (n-1) + (2/n) ∑ T(i) for i=0 to n-1.
2. Multiplying by n gives nT(n) = n(n-1) + 2 ∑ T(i).
3. Subtracting the equation for (n-1): (n-1)T(n-1) = (n-1)(n-2) + 2 ∑ T(i).
4. This results in nT(n) - (n-1)T(n-1) = 2(n-1) + 2T(n-1).
5. Rearranging gives nT(n) = (n+1)T(n-1) + 2(n-1).
6. Dividing by n(n+1) yields T(n)/(n+1) = T(n-1)/n + 2(n-1)/(n(n+1)).
7. Summing this telescopic series results in T(n) ≈ 2n ln n, which is O(n log n).