Jawaharlal Nehru Technological University Hyderabad B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (February - 2022 - R16)

Strassen's algorithm is a divide-and-conquer approach to matrix multiplication that reduces the number of recursive multiplications from 8 to 7. Given two n x n matrices A and B, we divide them into four n/2 x n/2 submatrices. The product C = AB is computed by calculating seven intermediate products P1 through P7:

The resulting submatrices of C are then formed by linear combinations of these products. The recurrence relation for the time complexity is T(n) = 7T(n/2) + O(n²). Applying the Master Theorem where a=7, b=2, and f(n)=n², we compare n^log2(7) with n². Since log2(7) is approximately 2.81, which is greater than 2, the complexity is T(n) = O(n^log2(7)) ≈ O(n^2.81), which is more efficient than the standard O(n³) algorithm.

Quick sort uses a divide-and-conquer strategy by selecting a pivot element and partitioning the array such that elements smaller than the pivot are on the left and larger elements are on the right. Consider the array [25, 10, 5, 30, 15].

1. Select the last element 15 as the pivot.
2. Partitioning: Compare elements with 15. 10 and 5 are smaller, 25 and 30 are larger. Swap 25 with 10, then 30 with 15. The array becomes [10, 5, 15, 30, 25].
3. The pivot 15 is now in its correct sorted position.
4. Recursively apply the same logic to the left sub-array [10, 5] and the right sub-array [30, 25].
5. For [10, 5], pivot 5 results in [5, 10]. For [30, 25], pivot 25 results in [25, 30].
6. Combining the results, the final sorted array is [5, 10, 15, 25, 30].

The average time complexity is O(n log n), while the worst-case complexity is O(n²) when the pivot selection consistently results in unbalanced partitions.