We are given a sequence (chain) (M1, M2, M3…Mn) of n matrices to be multiplied and we need to find the most efficient way to multiply these matrices together.
Strassen’s Algorithm for Matrix multiplication is a recursive algorithm for multiplying n x n matrices. Strassen’s algorithm is based on a familiar design technique – Divide & Conquer.
The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking numbers in the range as composite by marking the multiples of each prime as non-prime.
The number of possible partition of a set of n elements is B(n) known as Bell number. As we know, this problem is NP-Complete i.e. it has non-polynomial time solution.
While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets.