Check whether a directed graph is Eulerian
An Eulerian trail (or Eulerian path) is a path in a graph that visits every edge exactly once. Given a directed graph, check whether it has an Eulerian path or not.
Tag: Algorithm
Maximum Independent Set Problem
An independent set is a set of nodes in a binary tree, no two of which are adjacent. The maximum independent set problem is finding an independent set of the largest possible size for a given binary tree.
Hat Check Problem – Counting Derangements
Find the total number of ways in which n hats can be returned to n people such that no hat makes it back to its owner.
Eulerian cycle in directed graphs
Given a directed graph, check if it is possible to construct a cycle that visits each edge exactly once, i.e., check whether the graph has an Eulerian cycle or not.
Maximum path sum in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum path sum between any two nodes in it. The path can start and end at any node in the tree and need not go through the root.
Minimum-weight triangulation of a convex polygon
A triangulation of a convex polygon results in a set of non-intersecting diagonals between non-adjacent vertices, which completely partition the interior of the convex hull of the polygon into triangles.
Check whether an undirected graph is Eulerian
Given an undirected graph, check whether it has an Eulerian path or not. In other words, check if it is possible to construct a path that visits each edge exactly once.
Water Jugs Problem
Suppose you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, there is a blue jug for every red jug that holds the same amount of water and vice versa.
Check if a number is a perfect square
Given a positive number, check if it is a perfect square without using any built-in library function. A perfect square is a number that is the square of an integer.
Longest Alternating Subarray Problem
The Longest Alternating Subarray is a problem of finding a subarray with alternating positive and negative elements, and in which the subarray is as long as possible.
Weighted Interval Scheduling – Dynamic Programming Solution
Given a list of jobs where each job has a start and finish time, and a profit associated with it, find a maximum profit subset of non-overlapping jobs.
Activity Selection Problem using Dynamic Programming
Given a set of activities and the starting & finishing time of each activity, find the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.