algorithm

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,

convex hull

Chan's Algorithm to find Convex Hull

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n log h) time, where h is the number of vertices of the output (the convex hull).

convex hull

Graham Scan Algorithm to find Convex Hull

Graham's Scan Algorithm is an efficient algorithm for finding the convex hull of a finite set of points in the plane with time complexity O(N log N). The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary.

convex hull

Gift Wrap Algorithm (Jarvis March Algorithm) to find Convex Hull

Gift Wrap Algorithm ( Jarvis March Algorithm ) to find the convex hull of any given set of points. We start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in a counterclockwise direction. Find pseudocode, implementations, complexity and questions

convex hull

Divide and Conquer algorithm to find Convex Hull

Divide and Conquer algorithm to find Convex Hull. The key idea is that is we have two convex hull then, they can be merged in linear time to get a convex hull of a larger set of points. It requires to find upper and lower tangent to the right and left convex hulls C1 and C2

java memory management

Memory Management in Java: Mark Sweep Compact Copy algorithm

The basic strategy to remove unreferenced objects to is identify the life objects and deleting all the remaining objects. This is divided into two phases: Mark and Sweep. Every Garbage Collection algorithm used in Java Virtual Machine starts by finding out all objects that are still alive.

sorting algorithm

Merge Sort

Algorithm Pseudocode Visual Run Complexity Implementations Applications Questions The Merge Sort is an efficient comparison-based sorting algorithm based on divide and conquer strategy. It has a usual performance of Θ(N log N)

sorting algorithm

Quick Sort

Algorithm Complexity Implementations Optimizations Applications Discussions Quicksort algorithm is a comparison sort algorithm based on Divide and Conquer strategy. It has an average performance of Θ(n*log(n)) and is considered as