×

Home Discussions Write at Opengenus IQ

×

Algorithms

Algorithms have proven to be the most important domain over the last century which has reformed the way we do tasks. It is actively used to design industry systems and forms the building blocks of companies like Google. We cover all types of algorithms in depth

Binary GCD Algorithm

Binary GCD algorithm or Stein's algorithm is an algorithm that calculates two non-negative integer's largest common divisor by using simpler arithmetic operations than the standard euclidean algorithm and it reinstates division by numerical shifts, comparisons, and subtraction operations.

Finding the Largest 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 largest/ maximum element in an array. The time complexity to solve this is linear O(N) and space complexity is O(1).

Postman Sort

Postman sort works by sorting the integers of an array from their most significant digits to their least significant digits. It is a variant of radix sort.

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.

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.

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.

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.

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.

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.

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).

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).

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.

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.

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.

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).

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.

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.

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.

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.

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).

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.

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.