define strassen's matrix multiplication with example

Strassen's Matrix Multiplication:-

   Let A and B be the two matrices each of the order n x n. We want to output the project matrix P = A * B. The method is applying the divide and conquers technique. For computational facility, we assume that n = 2k for some positive integer k. If necessary we append a necessary number of rows or columns to both A and B all of zero elements. We split each matrix into four matrices, each of size n/2 x n/2.Then the product A * B can be computed recursively.


   For the multiplication of two 2 x 2 matrices, his method uses only 7 multiplication and 18 additions or subtractions. Now we explain this method. We first compute the seven n/2 X n/2 matrices p,
    Q, R, S, T, U, and V as follows.

  P = (A11 + A22)(B11 + B22)
  Q = (A21 + A22) B11
  R = A11 (B12 -B22)
  S = A22 (B21-B11)
  T = (A11 + A12) B22
  U = (A21 -A11)(B11 + B12)
  V = (A12-A22)(B21 + B22)

we compute the elements of P=A * B matrix as

A11 =  P + S -T + V
A12 =  R + T
A21 =   Q + S
A22 =  P + R - Q + U

The  Convex-Hull problem:

            Let X be a set of points in a plane. The convex hull of X, denoted by CH(X), is the smallest convex polygon p for which each point of X is either a vertex of p or inside p. It is evident that all the extreme points of p are also points of X. There may or may not point inside p. Now the problem is to compute the convex hull CH(X) of a set X of n points. Two algorithms are available for solving this problem. The first algorithm, called the Gram's scan algorithm runs in O(n log n) time. The second one, called Jarvis's march runs in O(n * h), where h is the number of vertices of the convex hull.

The Greedy method:-

   The greedy method is a powerful technique used in the design of an algorithm. Almost all problems that come under this category have n inputs. A subset of the given set of inputs that satisfies some given constraints is to be obtained. Such a subset is called a feasible solution. Now the problem is to find a feasible solution that maximizes or minimizes a given objective function. Such a function is called an optimal solution.