The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Continue reading Java Program for Longest Common Subsequence (LCS) Problem →

Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.

Continue reading Implementation of Graph Coloring Algorithm in Java →

The subset sum problem is a classic problem in computer science and is often solved using backtracking. The goal is to find subsets of elements selected from a given set whose sum adds up to a given number K.

Understanding the Problem

Given a set of n positive integers and a value m, the task is to determine all possible subsets whose sum is equal to m. This problem can be efficiently solved using backtracking.

Approach: Backtracking

Backtracking is a general algorithmic technique that incrementally builds candidates to a solution and abandons a candidate as soon as it is determined that the candidate cannot lead to a valid solution. In the subset sum problem, we:

1. Start with an empty subset.
2. Add elements one by one while keeping track of the sum.
3. If the sum equals m, print the subset.
4. If the sum exceeds m, backtrack and try another possibility.

Continue reading Implementing Sum of Subset by Backtracking in Java →

The n queens puzzle is the problem of placing eight chess queens on an n×n chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Continue reading Program for Implementation of N-Queen problem in Java →

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

In 0-1 Knapsack, the restriction is that, one cannot select fraction of any item. He/She must select either whole item or try with alternate one.

Continue reading Implementing 0-1 Knapsack in Java →

In this post, we’ll explore how to implement a Multi-Stage Graph in Java — a specialized graph where each stage (or node) has connections to only certain other stages, and the goal is to find the optimal path and cost through the stages.

What is a Multi-Stage Graph?

A Multi-Stage Graph is a graph where the nodes are grouped into distinct stages, and each node can only connect to the next stage in the sequence. The algorithm finds the minimum cost and optimal path from the start node (source) to the end node (destination).

In this post, we’ll focus on two methods to compute the optimal path:

1. Forward Method: Compute the cost and parent nodes starting from the destination.
2. Backward Method: Compute the cost and parent nodes starting from the source.

How the Multi-Stage Graph Algorithm Works

1. Graph Representation:
   The graph is represented using a 2D matrix where x[i][j] denotes the weight or cost of the edge from node i to node j. A value of 0 means there is no direct edge between the nodes.
2. Cost Calculation:
   • In the Forward Method, we start from the destination node and move backward to compute the cost for each stage.
   • In the Backward Method, we start from the source node and compute the cost to each destination node.
3. Optimal Path:
   The algorithm tracks the parent node for each stage, allowing us to trace the optimal path after computing the costs.

Continue reading Implementation of Multi-Stage Graph in Java →

In this post, we’ll walk through how to implement the All Pair Shortest Path algorithm in Java — a classic solution to find the shortest distances between every pair of vertices in a weighted graph.

What is the All Pair Shortest Path Problem?

The All Pair Shortest Path (APSP) problem involves finding the shortest distance between every possible pair of vertices in a graph. It’s commonly solved using Floyd-Warshall’s Algorithm, a dynamic programming approach that repeatedly updates the shortest distances between pairs of vertices by considering intermediate vertices.

How the Floyd-Warshall Algorithm Works

The core idea is to iteratively improve the estimate of the shortest path between any two vertices (i, j) by considering whether a path through a third vertex k would be shorter.

Here’s a breakdown:

1. Initialize the adjacency matrix:
   • Set the distance between every vertex to infinity (or a large value like 32767 here), except for the diagonal, where the distance from a vertex to itself is 0.
2. Input edges and their weights.
3. Iteratively update shortest distances:
   • For each vertex k, update the distance between all pairs (i, j) as:
     g[i][j] = min(g[i][j], g[i][k] + g[k][j])
4. After all iterations, the matrix g will hold the shortest distances between every pair.

---

Continue reading Implementation of All Pair Shortest Path Algorithm →