Kyatham Srikanth - OpenGenus IQ: Computing Expertise & Legacy

Subset Sum Problem using Dynamic Programming 【O(N*sum) time complexity】

In this article, we will solve this using a dynamic programming approach which will take O(N * sum) time complexity which is significantly faster than the other approaches which take exponential time.

Data Structures

AVL Tree: A tree that can stay balanced by rotating

An AVL Tree (Adelson-Velsky and Landis tree) is a self balancing binary search tree such that for every internal node of the tree the heights of the children of node can differ by at most 1. It uses four types of rotations to keep itself balanced and delete, insert and search take O(log N) time

multiplication

Toom Cook method for multiplication

Multiplication of two n-digits integers has time complexity at worst O(n^2).Toom-Cook algorithm is an algorithm for multiplying two n digit numbers in Θ(c(k)n^e) time complexity. The idea is based on divide-and-conquer technique

matrix multiplication

Cannon’s algorithm for distributed matrix multiplication

Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes. It is especially suitable for computers laid out in an N × N mesh. The main advantage of the algorithm is that its storage requirements remain constant and are independent of the number of processors.

matrix multiplication

Freivalds’ algorithm for verifying Matrix Multiplication

Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n x n matrices, Freivalds' algorithm determines in O(kn^2) whether the matrices are equal for a chosen k value with a probability of failure less than 2^-k.

matrix multiplication

Russian peasant multiplication algorithm

Russian peasant multiplication is an interesting way to multiply numbers that uses a process of halving and doubling without using multiplication operator. The idea is to double the first number and halve the second number repeatedly till the second number doesn’t become 1

matrix multiplication

Strassen’s Matrix Multiplication algorithm

Strassen’s Matrix Multiplication algorithm is the first algorithm to prove that matrix multiplication can be done at a time faster than O(N^3). It utilizes the strategy of divide and conquer to reduce the number of recursive multiplication calls from 8 to 7 and hence, the improvement.