Algorithms that run our Universe

Find the Longest Increasing Odd Even Subsequence

In this problem, we have formulated an algorithm to find the Longest Increasing Odd Even Subsequence. Brute force approach takes exponential time O(2^N) but a Dynamic Programming approach takes O(N^2) time.

Algorithms

Find the Longest Common Increasing Subsequence

In this problem, we have formulated an algorithm to find the Longest Common Increasing Subsequence. Brute force approach takes exponential time but a Dynamic Programming approach takes O(N^2) time.

Algorithms

Minimum characters added to the front of string to make it palindrome

In this problem, we have to formulate an algorithm to find the minimum number of characters to be added to the front of a string to make it a palindrome. To solve this efficiently in linear time O(N), we have to use longest prefix suffix of Knuth Morris Pratt pattern matching algorithm.

Algorithms

Rearrange string such that no two adjacent characters are same

In this problem, we have to rearrange the characters of the string such that no two adjacent characters are same. To solve this efficiently in O(N log N) time, we will use priority queue data structure.

Algorithms

Range Minimum query using segment tree [O(log N) update + O(log N) query]

In this article, we have solved the Range Minimum Query using Segment tree which takes O(log N) time for both update and range query. This is one of the best approaches to solve this problem.

Algorithms

Longest common substring using rolling hash approach

We can solve the longest common substring problem using the rolling hash technique in O(N * log(N)^2) time and O(N) space which is significantly better than other approaches.

Algorithms

Range Minimum query using square root decomposition [O(1) update + O(sqrt N) query]

In this article at OpenGenus, we have solved the Range Minimum Query problem using Square Root Decomposition which takes constant time O(1) for update and O(square root of N) time for range query.

Algorithms

Range Minimum query using Naive algorithm [O(1) update + O(N) query]

In the naive approach for range minimum query, we can execute the update query in constant time which is efficient and the best case but the query operation takes linear time O(N) which is slow depending upon number of elements and queries.

Algorithms

Maximum product cutting problem

In Maximum product cutting problem. we are given a rod of length N which we need to cut into small pieces such that the product of the length of the pieces is maximum. This is similar to the Rod Cutting problem and can be solved using Dynamic Programming.

Algorithms

Pairs whose sum is divisible by a given number

In this article, we explored how we can find the number of pairs whose sum is divisible by a given number K. This can be done using brute force approach in O(N^2) time but an efficient approach can reduce it to O(N) time.

Algorithms

Try these questions if you think you know Linear Search

Must attempt questions on Linear Search algorithm. Linear Search seem to be a simple algorithm but understanding it deeply requires expertise. It is a guarantee that you will learn new things about this on going through our questions.

Algorithms

Find the number of subsets with given Bitwise OR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the Bitwise OR value of all elements in the subset. This can be solved using Dynamic Programming in polynomial time.

Algorithms

Find minimum number of deletions to make a string palindrome

We need to find the minimum number of characters to be deleted in a string to make it a palindrome. This can be done in O(N^2) time with the help of Dynamic Programming approach of Longest Palindromic Subsequence.

Algorithms

Minimum insertions to make the frequency of each character unique

We developed a string algorithm to find out the minimum number of insertions to be made in a string so that the frequency of each character is unique

Algorithms

Longest Common Subsequence

In this problem, we solved the Longest Common Subsequence problem using Dynamic Programming which takes O(N*M) time while a brute force approach takes O(2^N) time

Algorithms

Longest Common Substring in two strings

In this problem, we explored a Dynamic Programming approach to find the longest common substring in two strings which is solved in O(N*M) time. Brute force takes O(N^2 * M) time.

Algorithms

Evolution of Integer Multiplication Algorithms (from 1960 with end in 2019)

We started with an O(N^2) time Integer Multiplication algorithm and it was the first time ever in 1960 that we developed an faster Integer Multiplication algorithm which ran at O(N^1.58) time and now in 2019, we are nearly at the end of this domain with O(N logN) time algorithm.

Algorithms

Research papers on Integer Multiplication (1960 to 2019)

hese are the papers that you should read and understand to understand how we have improved Integer Multiplication over the years and now in 2020, we are on the verge of completing this domain once for all.

People in Computer Science

Hans Peter Luhn, the man behind Hash Map

Hans Peter Luhn was a computer scientist who is famously remembered as the inventor of Hash Map and has laid the foundations of text information processing.

Algorithms

Rod cutting problem

In this article, we explored the rod cutting problem in depth which can be solved using a Dynamic Programming approach that takes O(N^2) time and O(N) space

Algorithms

Volker Strassen, the man who changed Matrix Multiplication

Volker Strassen is a Computer Scientist and Mathematician who is best known as the person who broke the strongly held belief that Matrix Multiplication cannot be done faster than O(N^3) time.

Algorithms

Minimum deletions to make frequency of each character unique

The problem we will solve is that given a string s, we need to find the minimum number of characters to be deleted from s so that the frequency of each character in the string is unique.

Algorithms

Find if a string is a sub-string of another string

We have presented two approaches to check whether a string is a substring of another string namely naive method which takes O(N^2) time and efficient method using the concept of Rolling Hash which takes linear time O(N).

Software Engineering

Round Robin Scheduling Algorithm

The key idea of Round Robin Scheduling algorithm is to allocate CPU to all processes in the same order for the same amount of time in turns. It provides real time computing experience.

Algorithms

Iterative and Recursive Binary Search Algorithm

The major difference between the iterative and recursive version of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1)