Strassen’s Algorithm for Matrix multiplication

Strassen’s Algorithm for Matrix multiplication is a recursive algorithm for multiplying n*n matrices in O(n^lg(7)) ie O(n^2.81) time. It outperforms the naive O(n^3) matrix multiplication algorithm. Naive Matrix-Multiplication (A, B) Pseudocode 1. n = Length[A] 2. C = n x n matrix 3. for i = 1 to n 4. do […]

Multiset Partitioning Problem

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that number of elements in the original set always equals to the sum of number of elements in each partition. Equivalently, a family of sets P is a partition of X if and only if […]

A Chocolate Fiesta | HackerRank

Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today’s topic is Set Theory. For today’s game, she had given a set A = {a1, a2, …aN} of N integers to her students and asked them to play the game as follows. […]