algorithm

algorithm

Minimum operations to make GCD of array a multiple of k

We are given an array and k, we need to find the minimum operations needed to make GCD of the array equal or multiple of k. Here an operation means either increment or decrement an array element by 1.

similarity measurement

Damerau Levenshtein distance

Damerau Levenshtein distance is a variant of Levenshtein distance which is a type of Edit distance. Damerau stated that the four operations in Damerau Levenshtein distance correspond to more than 80% of all human misspellings. It adds an extra operation named transposition to its set of operations

similarity measurement

Levenshtein distance

evenshtein distance is a type of Edit distance which is a large class of distance metric of measuring the dissimilarity between two strings by computing a minimum number of operations (from a set of operations) used to convert one string to another string. It is a way of pairwise string alignment.

similarity measurement

Chebyshev distance

Chebyshev distance is a distance metric which is the maximum absolute distance in one dimension of two N dimensional points. It has real world applications in Chess, Warehouse logistics and many other fields. It is known as Tchebychev distance, maximum metric, chessboard distance and L∞ metric.

similarity measurement

Euclidean distance (L2 norm)

Euclidean distance is the shortest distance between two points in an N dimensional space also known as Euclidean space. It is used as a common metric to measure the similarity between two data points and used in various fields such as geometry, data mining, deep learning and others.

similarity measurement

Manhattan distance (L1 norm)

Manhattan distance (L1 norm) is a distance metric between two points in a N dimensional vector space. It is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. It was introduced by Hermann Minkowski. It is used in regression analysis

string algorithm

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.

genetic algorithm

Basics of Genetic Algorithms

A genetic algorithm is a search heuristic (related to making guesses) algorithm that is inspired by Charles Darwin’s theory of natural evolution. We have explained the basic concepts of genetic algorithms including initial population, fitness function, selection, crossover and mutation.

bitwise operation

Algorithm to detect whether two numbers have opposite signs using bitwise operators

We present a bitwise algorithm to detect whether two numbers have opposite signs. This is important as using comparision based operations is slow and nearly all hardware support optimizations for bitwise operations

algorithm

Maximize sum of consecutive differences in a circular array

Given an array A with values a1, a2, a3, a4, an Now, arrange all elements of array A such that sum of absolute differences of consecutive elements is maximum, i.e consider after an arrangement the array is b1, b2, b3, b4,..., bn then maximize |b1-b2| + |b2-b3| + |b3-b4| + .. + |bn-1-bn| + |bn-b1|

bitwise operation

Bitwise Algorithm to Find the Number Occurring with Odd Frequency

We have explored the bitwise algorithm to find the only number occuring odd number of times in a given set of numbers. We have used the XOR operator to solve this problem in O(N) time complexity in contrast to the native algorithm which takes O(N^2) time complexity. The space complexity is constant.

bitwise operation

Maximise XOR of a given integer with a number from the given range

Given q queries each of specifies three integers x, l, r. We have to find an integer from given range [l, r] inclusive, such that it gives maximum XOR with x. All values are assumed to be positive. We will show two ways to solve this interesting problem.

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.

string algorithm

Algorithm to find the maximum occurring character in a string

Algorithm Pseudocode Complexity Implementation Applications Reading time: 15 minutes | Coding time: 5 minutes One approach to solve this problem would be to sort the input string and then traverse through the sorted string

convex hull

Kirkpatrick-Seidel Algorithm (Ultimate Planar Convex Hull Algorithm)

Algorithm Complexity Applications Reading time: 15 minutes | Coding time: 9 minutes The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm", is an algorithm for computing the

bitwise operation

Left and Right Bit Rotation using Bitwise Operators

Left Rotation Right Rotation Pseudocode Implementation Applications Question Reading time: minutes | Coding time: minutes A bitwise operation involves manipulation of one or more bits of a bit pattern. A bitwise operation can simply

java memory management

Memory Management in Java: Garbage Collection algorithms

There are several strategies of Garbage Collection each of which is suitable fora particular use case. This is article we have explored some of the best Garbage Collection algorithms. Serial Garbage Collection, Parallel Garbage Collection, Concurrent Mark and Sweep and G1 garbage collection

game theory

Sprague-Grundy Theorem and Game of Kayle

Sprague Grundy function returns smallest non negative integer which is not in the given set. Explore the application of Sprague Grundy Theorem using a famous game of Kayle. Find the complexity and implementation of Sprague Grundy theorem and game of kayle.

game theory

Nimber Arithmetic : A deeper dive in Nim

Explore Nimber Arithmetic in Game theory and always win a game. Nimbers have two particular operations. nim-addition and nim-multiplication. the nimbers are know as Grundy Numbers. Explore applications in the Game of Nim and odd Knight of the round table problem.

game theory

Exploring The Game of Nim

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. The key to the theory of the game is the binary digital sum of the heap sizes "exclusive or" (xor). It is called the nim-sum. Find implementations of winning strategy and applications

catalan number

Catalan Numbers

Catalan Numbers are one of the widest used and evident number patterns. They are named after the Belgian mathematician Eugène Charles Catalan. A sequence of natural numbers that occur in various counting problems. The Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,