JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (October - 2020 - R16)

The Divide and Conquer paradigm is an algorithmic strategy that solves a problem by recursively breaking it down into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give the solution to the original problem.

The general method follows three steps:

1. Divide: Break the problem into smaller sub-problems that are instances of the same problem.
2. Conquer: Solve the sub-problems recursively. If the sub-problems are small enough, solve them as base cases.
3. Combine: Merge the solutions of the sub-problems to obtain the final solution for the original problem.

An example is Merge Sort. To sort an array of size n, it divides the array into two halves, recursively sorts each half, and then merges the two sorted halves into a single sorted array.

Strassen's algorithm improves matrix multiplication by reducing the number of recursive multiplications required. Given two n x n matrices A and B, we divide them into four n/2 x n/2 sub-matrices. The algorithm computes seven products P1 through P7:

The resulting sub-matrices of C are then calculated using additions and subtractions of these products:

The recurrence relation for the time complexity is:

Using the Master Theorem, where a = 7, b = 2, and f(n) = O(n²), we compare log base 2 of 7 (≈ 2.81) with 2. Since 2.81 > 2, the time complexity is O(n^log₂7), which is approximately O(n^2.81), making it more efficient than the standard O(n³) approach for large matrices.