Algorithms that run our Universe

Regula Falsi Method for finding root of a polynomial

Regula Falsi method or the method of false position is a numerical method for solving an equation in one unknown. It is quite similar to bisection method algorithm and is one of the oldest approaches.

Algorithms

Introduction to Dynamic Programming

In this article, we will understand crux of Dynamic Programming, different methodologies for solving DP problems, identifying a DP problem and trying to solve a specific problem

Algorithms

How to calculate Complexity of an Algorithm? (+ different Notations)

In this article, we will understand the complexity notations for Algorithms along with Big-O, Big-Omega, B-Theta and Little-O and see how we can calculate the complexity of any algorithm.

Algorithms

Print Fibonacci Series in Reverse Order

In this article, we will explore how to print fibonacci series in reverse order. A key point to note here is that as Fibonacci number depends on previous fibonacci numbers

Algorithms

Bisection Method for finding the root of any polynomial

Bisection Method for root finding (also called the interval halving method, the binary search method, or the dichotomy method) is based on the Bolzano’s theorem for continuous functions

Algorithms

Find if a Subset with sum divisible by m exist

In this article, we find if a Subset with sum divisible by m exist. A naive approach takes O(2^N) time while dynamic programming takes O(N*M) time

Problems on Binary Tree

Find height or depth of a binary tree

Length of the longest path from the root node to a leaf node is the height of the binary tree. We find it in linear time using a recursive algorithm

Problems on Binary Tree

Largest Independent Set in Binary Tree

In this article, we solve the Largest Independent Set in Binary Tree problem using Dynamic Programming and use an augmented binary tree to achieve this.

Algorithms

Minimum Cost for Triangulation of a Convex Polygon

We find the Minimum Cost for Triangulation of a Convex Polygon using a dynamic programming approach in O(N^2) space and O(N^3) time complexity.

Algorithms

The smallest subset with sum greater than sum of all other elements

In this article, we explored a greedy algorithm to find the smallest subset with sum greater than sum of all other elements in O(N log N) time complexity

Algorithms

Find Minimum sum of product of two arrays

In this article, we explored a greedy algorithm to find the minimum sum of product of two arrays in O(N log N) time whereas the brute force approach takes O(N!^2) time

Algorithms

Find the Largest Cube formed by deleting minimum number of digits from a number

In this article, we find the Largest Cube formed by deleting minimum number of digits from a number using a greedy algorithm which takes O(N^(1/3)log(N)log(N)) time

Algorithms

Find n-th Fibonacci number using Dynamic Programming

In this article, we have explored a dynamic programming approach to find the n th fibonacci number followed by a space optimized technique.

Algorithms

Solving Unbounded Knapsack Problem using Dynamic Programming

Restriction of limited items is removed in Unbounded Knapsack Problem. An item can be used infinite times and can be solved efficiently using Dynamic Programming.

Algorithms

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.

Algorithms

Subset Sum Problem solved using Backtracking approach 【O(2^N) time complexity】

In this article, we will solve Subset Sum problem using a backtracking approach which will take O(2^N) time complexity

Algorithms

Subset sum problem solved using a recursive brute force approach 【O(2^N) time complexity】

In this article, we will solve Subset Sum problem using a recursive approach where the key idea is to generate all subset recursively. It will take O(2^N) time complexity.

Algorithms

Find all primes with Sieve of Sundaram

Sieve of Sundaram is an efficient algorithm used to find all the prime numbers till a specific number say N.

Algorithms

Overview of Graph Colouring Algorithms

In this introductory article on Graph Colouring, we explore topics such as vertex colouring, edge colouring, face colouring, chromatic number, k colouring, loop, edge, chromatic polynomial, total colouring and various algorithmic techniques for graph colouring.

Algorithms

Shortest Common SuperSequence 【O(M*N) time complexity】

Given two strings X and Y, the supersequence of string X and Y is such a string Z that both X and Y is subsequence of Z.

Algorithms

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

Algorithms

Word Break Problem 【O(n * s) time complexity】

In this problem we are given with a string and a dictionary of words, we need to find if the string can be segmented to words so that all the segmented words are present in the dictionary.

Algorithms

Stooge Sort

Stooge sort performs sorting in first 2/3 part and then it performs sorting in last 2/3 part. After that, sorting is done on first 2/3 part to ensure the array is sorted.

Algorithms

Find Minimum Swaps required for Bracket Balancing

Given a string of 2N characters consisting of N '[' brackets and N ']' brackets, our target is to find the minimum number of swaps required to make the set of brackets balanced.

Algorithms

Generating all permutations of an array in C++ using STL

We can generate all permutations of an array by making use of the C++ STL function next_permutation.