OpenGenus Foundation - OpenGenus IQ

Flattening a Linked List

In this article, we explored an algorithm to flatten a linked list where each node has two pointers with one to another linked list. Our approach explored a novel application of the merge component of merge sort to solve this problem.

linked list

Find the middle element of a singly Linked List

In this article, we will explore two approaches to find the middle element of a singly linked list. In one approach, we will use one traversal to count the number of elements and the other to find the middle element. The second approach is to use one traversal and concept of fast and slow pointers.

graph colouring

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.

graph colouring

Graph Coloring Greedy Algorithm

In this article, we have explored the greedy algorithm for graph colouring. graph coloring is a special case of graph labeling ; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

graph colouring

Wigderson Graph Colouring Algorithm

Wigderson Algorithm is a graph colouring algorithm to color any n-vertex 3-colorable graph with O(√n) colors, and more generally to color any k-colorable graph. In this article, we have explored this wonderful graph colouring article in depth.

Artificial Intelligence

L1 and L2 Regularization Methods

A regression model that uses L1 regularization technique is called Lasso Regression and model which uses L2 is called Ridge Regression. The key difference between these two is the penalty term. Lasso shrinks the less important feature’s coefficient to zero

Artificial Intelligence

Gradient descent

Gradient descent algorithm is one of the most popuarl algorithms for finding optimal parameters for most machine learning models including neural networks. The basic method that this algorithm uses is to find optimal values for the parameters that define your ‘cost function’.

Artificial Intelligence

Regularization

Regularization is a method used to reduce the variance of your model and increase the bias. It is used when your model overfits the training data. Another method to do regularization is called Lasso regression. This is the solution to Biase-Variance Dilemma.

Artificial Intelligence

Cross Validation

Cross Validation is a procedure used to evaluate your machine learning model on limited sample of data. With the help of this, we can actually tell how well our model performs on unseen data. Other variants are stratified cross validation and leave one out cross validation. Learn through an example

Artificial Intelligence

Decision Trees

Decision Tree is a popular machine learning algorithm mainly used for classification. Concepts of entropy and information gain are required to apply decision tree for a data set. It is used for non-linear classification and regression Learn through an example

red black tree

Red Black Tree: Deletion

We will explore the deletion operation on a Red Black tree in the session. Deleting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

red black tree

Red Black Tree: Insertion

We will explore the insertion operation on a Red Black tree in the session. Inserting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

red black tree

Red Black Tree: Search

We will explore the search operation on a Red Black tree in the session. Searching in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.

graph colouring

Welsh-Powell Algorithm

Pseudocode Implementations Complexity Applications Reading time: 20 minutes | Coding time: 9 minutes In graph theory, Welsh Powell is used to implement graph labeling; it is an assignment of labels traditionally called "colors&

dynamic programming

The Coin Change Problem

Given a set of coins S with values { S1, S2, ..., Sm }, find the number of ways of making the change to a certain value N. There is an infinite quantity of coins and the order of the coins doesn't matter. This real life problem can be solved by Dynamic Programming in

dynamic programming

Box stacking Problem

Given a set of n types of 3D rectangular boxes, find the maximum height that can be reached stacking instances of these boxes. This problem can be solved efficiently by using Dynamic programming in O(N^2) time complexity and linear O(N) space complexity.

dynamic programming

0-1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

string algorithm

Algorithm to find the maximum occurring character in a string

Algorithm Pseudocode Complexity Implementation Applications Reading time: 15 minutes | Coding time: 5 minutes One approach to solve this problem would be to sort the input string and then traverse through the sorted string

binary tree

Properties of a Binary Tree

properties of Binary Tree are as follows: The maximum number of nodes at level ‘L’ of a binary tree is 2L-1, Maximum number of nodes in a binary tree of height ‘H’ is 2H – 1, In a Binary Tree with N nodes, minimum possible height or minimum number of levels is ⌈ Log2(N+1) ⌉

binary tree

Binary Tree

A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree

nash equilibrium

Nash Equilibrium

Algorithm Complexity Implementations Applications: Tinder questions Reading time: 25 minutes | Coding time: 10 minutes In game theory, the Nash equilibrium, named after American mathematician John Forbes Nash Jr., is a solution concept of

linked list

Sort a Linked List which is already sorted on absolute values

Algorithm Example Complexity Implementations Questions Reading time: 15 minutes | Coding time: 5 minutes The problem at hand is to sort a singly Linked List which is already sorted on absolute value. Sorting always

linked list

Merge Sort a singly Linked List

Algorithm Complexity Implementations Questions Merge sort is a fast comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Merge Sort is preferred for sorting a linked list.

linked list

Insertion Sort a Linked List

Algorithm Pseudocode Complexity Implementations Questions Reading time: 15 minutes | Coding time: 20 minutes Insertion sort is a comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Insertion

linked list

Insert element in a sorted Linked List

Pseudocode Implementations Complexity Can binary search be used to improve performance? Reading time: 15 minutes | Coding time: 20 minutes In this session, we will explore how to insert an element in a sorted