Algorithms that run our Universe

Number of substrings divisible by 8 but not 3

We need to find total number of substrings that are divisible by 8 but not 3 in the given string. We have solved this problem using Dynamic Programming in linear time O(N) where the brute force approach takes O(N^2) time.

Algorithms

Minimum number of operations to make GCD of an array K

We are given an array and we need to find the minimum number of operations required to make GCD of the array equal to k. Where an operation could be either increment or decrement an array element by 1. We have solved this in O(N log N) time complexity.

Algorithms

Reverse a linked list using 2 pointers technique using XOR operator

You must have come across reversing a linked list using 3 pointers technique which is the most common approach to do it. But do you know how to reverse a linked list with just 2 pointers? This article will teach you just that! Let's dive into it.

Software Engineering

Linear Search in C Programming Language

We have explored Linear Search algorithm and implemented variants of Linear Search in C Programming Language. The variants we have explored are Linear Search in array in C, Linear Search in Linked List in C, Linear Search in array with duplicates and Linear Search in Linked List with duplicates.

Algorithms

String Matching using Bitset

In this article, we have explored how to solve string matching problem (find all occurences of string S1 in another string S2) using Bitset. It is a modification of the naive approach which takes O(L x P x logL) time complexity which improves to O(L x P / K) using bitset.

Software Engineering

Solving Linear Programming problems in Python using cvxpy library

Linear programming requires that all the mathematical functions in the model be linear functions. We have solved linear programming problems in Python using cvxpy library.

Software Engineering

How to formulate a linear programming problem?

In this article, we will explore into sample problems and formulate it as a linear programming problem. We have considered three problems Product Mix Problem, Transportation Problem and Flow Capacity Problem.

Algorithms

Minimum number of increment or decrement (by 1) operations to make array in increasing order

Given an array of size N. Find the minimum number of increment or decrement operations to make the array in increasing order. In each move, we can add or subtract 1 to any element in the array.

Algorithms

Minimum number of increment (by 1) operations to make array in increasing order

Given an array of size N . Find the number of increment (by 1) operations required to make the array in increasing order. In each move, we can add 1 to any element in the array.

Algorithms

Number of ways to reach a number using increments of 1 and 2 (consecutive 2s are not allowed)

The problem states that given a number or a score, we need to find the number of ways to reach it using increments of 1 and 2 with a constraint that consecutive 2s aren't allowed. We will solve this using Dynamic Programming in linear time O(N).

Algorithms

Topological Sort using Breadth First Search (BFS)

In this article, we have explored how to perform topological sort using Breadth First Search (BFS) along with an implementation. We have compared it with Topological sort using Depth First Search (DFS).

Algorithms

DFS vs BFS (in detail)

DFS and BFS are two fundamental graph traversal algorithms and both are significantly different each with its own applications. DFS is used Kosaraju's algorithm while BFS is used in shortest path algorithms.

Algorithms

Bidirectional Search

Bidirectional Search is Graph Search Algorithm where two graph traversals (BFS) take place at the same time and is used to find the shortest distance between a fixed start vertex and end vertex. It is a faster approach, reduces the time required for traversing the graph.

Algorithms

Time bounds for selection

In this article, we have discussed the paper titled "Time bounds for selection" submitted by Blum and others. It presents PICK algorithm for the problem which is "Given an array of n integers, we have to pick the ith smallest number". It takes no more than 5.4305 * n comparisons.

Algorithms

Number of distinct elements in a given range

This is a problem in which we have an integer array which contains some elements and our job is to find out number of distinct elements in a given range. We have solved this using three methods with the most efficient approach being a hashing technique with linear time complexity O(N).

Algorithms

Connected Component Labeling

This article covers: Connected Components (also known as Connected Component Analysis, Blob Extraction, Region Labeling, Blob Discovery or Region Extraction), Connected Component Labeling, Algorithms and an Example of Applying in Python using OpenCV.

Algorithms

Run Length Encoding

Learn more about Run Length encoding which is a lossless data compression algorithm, supported by many bitmap file formats. In short, it picks the next unique character and appends the character and it’s count of subsequent occurrences in the encoded string.

Algorithms

Breadth first search (BFS)

Breadth first search (BFS) is one of the most used graph traversal techniques where nodes at the same level are traversed first before going into the next level. Queue is used internally in its implementation.

Algorithms

Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm

In this article, we have explored the difference between two popular string pattern searching algorithms: Knuth-Morris-Pratt (KMP) vs Boyer Moore Pattern Searching algorithm.

Algorithms

Scheduling tasks to Minimize Lateness

In this article, we have explored techniques to schedule tasks (with a deadline and time required to complete it) in a way to decrease the time lag in finish time and deadline of the chosen request (i.e., lateness).

Algorithms

Understand Genetic Algorithm with overfitting example

In this article, we have explored the ideas in Genetic algorithms (like crossover, mutation, fitness and much more) in depth by going though a Genetic algorithm to reduce overfitting.

Algorithms

Longest palindromic substring using Palindromic tree

Given a string, we are required to find the longest palindromic substring. In this article, we have solved this problem using palindromic tree.

Algorithms

Smallest Missing Positive Integer

The problem is to find out the smallest missing positive integer given an unsorted integer array. We can solve this problem in linear time O(N) and in constant time O(1) using a greedy approach with hash map.

Algorithms

Partition a set into two subsets such that sum of each subset is same

An analysis and explanation of the solution for the partition problem, in which a set of numbers is to be divided into two sub arrays such that their sum is equal, by using dynamic programming.

Algorithms

Find the smallest element in an array

We are given an integer array of size N or we can say number of elements is equal to N. We have to find the smallest/ minimum element in an array. The time complexity to solve this is linear O(N) and space complexity is O(1).