×

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

Minimum Bitwise OR operations to make any two array elements equal

Given an array of integers and an integer K, we can perform the Bitwise OR operation between K and elements of the array any number of times. We have to count minimum number of such operations that are required to make any two elements of the array equal.

MiniMax Algorithm: How Machine thinks?

Minimax algorithm is a recursive algorithm used to choose an optimal move for a player, assuming that the opponent is also playing optimally. As its name suggests, its goal is to minimize the maximum loss (reduce the worst-case scenario).

Pancake Sort Algorithm (in-place, not stable)

Pancake sort is a sorting algorithm in which the only allowed operation is to "flip" one end of the list. It is inplace but not stable. Pancake sort is called so because it resembles sorting pancakes on a plate with a spatula, where you can only use the spatula to flip some of the top pancakes.

Counting number of set bits (1) in a number (Brian Kernighan Algorithm)

With this article at OpenGenus, you must have the complete idea of Counting the number of set bits (1) in a number using naive approach and Brian Kernighan Algorithm.

Number of times characters of a string is present in another string

In this article, we have explored the algorithm to find the Number of times characters of a string is present in another string. This can be solved in O(N^2) time.

Transitive Closure Of A Graph using Graph Powering

In this article, we will begin our discussion by briefly explaining about transitive closure and graph powering. We will also see the application of graph powering in determining the transitive closure of a given graph.

Data Structures

Sort a stack using another stack

In this article, we have explored an algorithm to sort a stack using another stack that is by using stack operations like push and pop only. The time complexity of this approach is O(N^2) and space complexity is O(N).

Software Engineering

Idea behind Load Balancer

Load Balancer is placed between the clients and the server accepting incoming requests and distributing the traffic across multiple backend servers using different algorithms.

Transitive Closure Of A Graph using Floyd Warshall Algorithm

In this article, we will begin our discussion by briefly explaining about transitive closure and the Floyd Warshall Algorithm. We will also see the application of Floyd Warshall in determining the transitive closure of a given graph.

Gale Shapley Algorithm for Stable Matching problem

Gale Shapley Algorithm is an efficient algorithm that is used to solve the Stable Matching problem. It takes O(N^2) time complexity where N is the number of people involved.

Minimum Increment and Decrement operations to make array elements equal

We are given an array, we need to find the minimum number of increment and decrement operations (by 1) required to make all the array elements equal. We have explored two approaches where brute force approach take O(N^2) time while the efficient approach O(N logN) time.

Minimum number of increment (by 1) operations to make elements of an array unique

We are given a sorted array which might have duplicate elements, our task is to find the minimum number of increment (by 1) operations needed to make the elements of an array unique. We have solved this using two approaches one using two pointers and other using hashmap.

Hashed Array Tree: Efficient representation of Array

Hashed Array Tree is an improvement over Dynamic Arrays where there can be a large amount of unused allocated memory at a time. This can be visualized as a 2 dimensional array and has been developed by Robert Sedgewick, Erik Demaine and others.

First Unique Character in a String

In this article, we need to find first unique i.e non-repeating character in a given string and return the index or else if no such character exists we return -1.

Reverse alternate groups of K nodes in a Singly Linked List

We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

Divide and Conquer Optimization in Dynamic Programming

Divide and conquer optimization is used to optimize the run-time of a subset of Dynamic Programming problems from O(N^2) to O(N logN). We have demonstrated it with an example.

2-SAT problem

Boolean satisfiability is a NP-complete problem but, a special case of it can be solved in polynomial time. This special case is called case 2-SAT or 2-Satisfiability. We have explained the basic knowledge to understand this problem with depth along with solution.

Applications of Catalan Numbers

In this article, we have explored different applications of Catalan Numbers such as number of valid parenthesis expressions, number of rooted binary trees with n internal nodes, number of ways are there to cut an (n+2)-gon into n triangles and many more.

Knuth's optimization in Dynamic Programming

Knuth's optimization is used to optimize the run-time of a subset of Dynamic programming problems from O(N^3) to O(N^2). We have explained this with a sample problem.

Tim Sort

Tim Sort is a hybrid stable sorting algorithm that takes advantage of common patterns in data, and utilizes a combination of an improved Merge sort and Binary Insertion sort along with some internal logic to optimize the manipulation of large scale real-world data.

Overview of Maximum Flow Problem

The aim of the max flow problem is to calculate the maximum amount of flow that can reach the sink vertex from the source vertex keeping the flow capacities of edges in consideration.

Algorithm to find the maximum power of N that divides M factorial (M!)

We are given two numbers M and N. Our aim is to find the highest power of N that divides Factorial of M (M!). First we have discussed about the Brute Force approach and then we will be discussing this problem using Legendre’s formula.

Maximum houses a Robber can rob

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money the robber can rob tonight without alerting the police. We have solved this problem using Dynamic Programming.

Software Engineering

Implementing Binary search in C++

We have explained in depth how to implement Binary Search in C++. We have covered 3 approaches: Recursive implementation, Iterative implementation and using STL functions.

Kadane's Algorithm for largest subarray sum

Kadane's Algorithm is commonly known for Finding the largest sum of a subarray in linear time O(N). We have presented 3 variants of Kadane's Algorithm along with in-depth explanation of basic ideas.