Algorithms

Dynamic Programming (DP)

0-1 Knapsack Problem (Integral Knapsack)

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Brute force approach will take exponential time while a dynamic programming approach will take linear time.

String Algorithms

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

Algorithms

Bell Numbers: Number of partitions of a set

Bell numbers are a sequence of numbers that describe the number of ways a set with N elements can be partitioned into disjoint, non-empty subsets. Dobinski's Formula Satifaction Sum of Sterling's number of second kind, The Peirce Triangle Method. First few Bell numbers are 1, 1, 2, 5, 15, 52, 203

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.

Algorithms

Find primes using Sieve of Eratosthenes

Sieve of Eratosthenes is a simple and ancient algorithm (over 2200 years old) used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers. Implementations in C, C++, C Sharp, Java, Go, Haskell, JavaScript, PHP and Python.

Algorithms

Karatsuba Algorithm (for fast integer multiplication)

Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquer approach to multiply two numbers.

Sorting Algorithms

Merge Sort

Algorithm Pseudocode Visual Run Complexity Implementations Applications Reading time: 20 minutes | Coding time: 10 minutes The Merge Sort is an efficient comparison based sorting algorithm based on divide and conquer strategy. It has

Sorting Algorithms

Quick Sort

Algorithm Complexity Implementations Optimizations Applications Discussions Reading time: 20 minutes | Coding time: 10 minutes Quicksort algorithm is a comparison based sort algorithm based on Divide and Conquer strategy that is it aims to

Sorting Algorithms

Bogo sort

Algorithm Complexity Implementations Discussions BogoSort also known as permutation sort, stupid sort, slow sort, shotgun sort or monkey sort is a particularly ineffective algorithm based on generate and test paradigm. The algorithm successively

Sorting Algorithms

Bead Sort: An algorithm that works faster with hardware implementation

Bead sort (gravity sort) is a natural sorting algorithm. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); The implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers

Sorting Algorithms

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. Implementations in Java, C++, C, Go, Swift, JavaScript and many more.

Sorting Algorithms

Selection Sort

Selection sort is a sorting algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning of the unsorted part. It is used when only O(N) swaps can be made and when memory write is a costly operation

Search Algorithms

Exponential Search Algorithm

Algorithm Complexity Implementations Applications Discussions Exponential search algorithm (also called doubling search, galloping search, Struzik search) is a search algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted,

Search Algorithms

Ternary Search Algorithm

Algorithm Complexity Implementations Applications Discussions Ternary search is a divide-and-conquer search algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before we begin the