INDEX

S. No Practical Signature

1 Write a Program to implement Merge

sort
2 Write a Program to implement Matrix
Multiplication using Divide and
Conquer strategy
3 Write a Program to implement
Knapsack Problem using Greedy
Strategy
4 Write a Program to find Minimum
Spanning Tree of a given graph
using Kruskal's Algorithm

5 Write a Program to find Minimum

Spanning Tree of a given graph
using Prims Algorithm
6 Write a Program to implement Floyd
Warshall Algorithm

7 Write a Program to implement

Knapsack Problem using
Dynamic Programming
8 Write a Program to implement N
queens Problem using
Backtracking
9 Write a Program to perform
Travelling Salesman Problem

10 Write a Program to implement

Knapsack Problem using Branch
and Bound

Practical-1
Aim: Write a Program to implement Merge sort
Code:
import [Link];
public class MergeSort {
static void merge(int[] arr, int start, int mid, int end) {
int i = start;
int j = mid + 1;
int k = start;
int[] temp = new int[100];
while (i <= mid && j <= end) {
if (arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= end)
temp[k++] = arr[j++];
for (i = start; i <= end; i++)
arr[i] = temp[i];
}
static void mergeSort(int[] arr, int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the size of the array: ");
int n = [Link]();
int[] arr = new int[n];
[Link]("Enter the elements of the array: ");
for (int i = 0; i < n; i++) {
arr[i] = [Link]();
}
[Link]("\nOriginal Array:");
for (int i = 0; i < n; i++) {
[Link](arr[i] + " ");
 }
[Link]("\n");
mergeSort(arr, 0, n - 1);
[Link]("Sorted Array:");
for (int i = 0; i < n; i++) {
[Link](arr[i] + " ");
}
[Link]("\n");
[Link]();
}
}
Output:

Practical-2
Aim: Write a Program to implement Matrix Multiplication
using Divide and Conquer strategy
Code:
import [Link];
public class MatrixMultiplication {
static int[][] createMatrix(int n) {
int[][] temp = new int[n][n];
return temp;
}
static int[][] divideAndConquer(int[][] A, int[][]
B, int n) {
if (n == 1) {
int[][] C = createMatrix(1);
C[0][0] = A[0][0] * B[0][0];
return C;
}
int[][] C = createMatrix(n);
int k = n / 2;
int[][] A11 = createMatrix(k);
int[][] A12 = createMatrix(k);
int[][] A21 = createMatrix(k);
int[][] A22 = createMatrix(k);
int[][] B11 = createMatrix(k);
int[][] B12 = createMatrix(k);
int[][] B21 = createMatrix(k);
int[][] B22 = createMatrix(k);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + k];
A21[i][j] = A[i + k][j];
A22[i][j] = A[i + k][j + k];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + k];
B21[i][j] = B[i + k][j];
B22[i][j] = B[i + k][j + k];
}
}
int[][] P1 = divideAndConquer(A11, B11, k);
int[][] P2 = divideAndConquer(A12, B21, k);
int[][] P3 = divideAndConquer(A11, B12, k);
int[][] P4 = divideAndConquer(A12, B22, k);
int[][] P5 = divideAndConquer(A21, B11, k);
int[][] P6 = divideAndConquer(A22, B21, k);
int[][] P7 = divideAndConquer(A21, B12, k);
 int[][] P8 = divideAndConquer(A22, B22, k);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
C[i][j] = P1[i][j] + P2[i][j];
C[i][j + k] = P3[i][j] + P4[i][j];
C[i + k][j] = P5[i][j] + P6[i][j];
C[i + k][j + k] = P7[i][j] + P8[i][j];
}
}
return C;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the size of matrix (in
powers of 2): ");
int size = [Link]();
int[][] A = createMatrix(size);
int[][] B = createMatrix(size);
int[][] C;
[Link]("Enter the elements of
matrix A:");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
A[i][j] = [Link]();
}
}
[Link]("Enter the elements of
matrix B:");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
B[i][j] = [Link]();
}
}
C = divideAndConquer(A, B, size);
[Link]("The product of matrix A
and B is:");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
[Link](C[i][j] + " ");
}
[Link]();
}
 [Link]();
}
}
Output:
 Practical-3
Aim: Write a Program to implement Knapsack Problem
using Greedy Strategy
Code:
import [Link];
import [Link];
class Item {
int value;
int weight;
Item() {}
Item(int value, int weight) {
[Link] = value;
[Link] = weight;
}

public class FractionalKnapsack {

static boolean compare(Item a, Item b) {
double r1 = (double) [Link] / [Link];
double r2 = (double) [Link] / [Link];
return r1 > r2;
}
static double fractionalKnapsack(int W, Item[]
arr, int n) {
[Link](arr, (a, b) -> compare(a, b) ? -1 :
1);
int curWeight = 0;
double finalValue = 0.0;
for (int i = 0; i < n; i++) {
if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalValue += arr[i].value;
} else {
int remain = W - curWeight;
finalValue += arr[i].value * ((double)
remain / arr[i].weight);
break;
}
}
return finalValue;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
 [Link]("Enter the capacity of
knapsack: ");
int W = [Link]();
[Link]("Enter the number of items:
");
int n = [Link]();
Item[] arr = new Item[n];
for (int i = 0; i < n; i++) {
[Link]("Enter the value and
weight of item " + (i + 1) + ": ");
int value = [Link]();
int weight = [Link]();
arr[i] = new Item(value, weight);
}
[Link]();
[Link]("Maximum value we can
obtain = " + fractionalKnapsack(W, arr, n));
[Link]();
}
}
Output:
 Practical-4
Aim: Write a Program to find Minimum Spanning Tree of
a given graph using Kruskal's Algorithm
Code:
import [Link].*;
class Main {
static boolean compare(List<Integer> a,
List<Integer> b) {
return [Link](2) < [Link](2);
}
static int findParent(List<Integer> parent, int
node) {
if ([Link](node) == node) {
return node;
}
return [Link](node, findParent(parent,
[Link](node)));
}
static void unionSet(int u, int v, List<Integer>
parent, List<Integer> rank) {
u = findParent(parent, u);
v = findParent(parent, v);
if ([Link](u) < [Link](v)) {
[Link](u, v);
} else if ([Link](v) < [Link](u)) {
[Link](v, u);
} else {
[Link](v, u);
[Link](u, [Link](u) + 1);
}
}
static int
minimumSpanningTree(List<List<Integer>>
edges, int n) {
[Link]((a, b) -> compare(a, b) ? -1 : 1);
 List<Integer> parent = new
ArrayList<>([Link](n, 0));
List<Integer> rank = new
ArrayList<>([Link](n, 0));
for (int i = 0; i < n; i++) {
[Link](i, i);
}
int minWeight = 0;
[Link]("\nFollowing are the edges
in the constructed MST - ");
for (List<Integer> edge : edges) {
int u = findParent(parent, [Link](0));
int v = findParent(parent, [Link](1));
int wt = [Link](2);
if (u != v) {
minWeight += wt;
unionSet(u, v, parent, rank);
[Link]([Link](0) + " " +
[Link](1));
}
}
[Link]();
return minWeight;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter number of vertices:
");
int n = [Link]();
[Link]("Enter number of edges: ");
int m = [Link]();
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < m; i++) {
[Link]("Enter the edge and
weight: ");
int u = [Link]();
int v = [Link]();
int w = [Link]();
[Link]([Link](u, v, w));
}
int cost = minimumSpanningTree(g, n);
[Link]("Minimum cost of the
 spanning tree: " + cost);
[Link]();
}
}
Output:
 Practical-5
Aim: Write a Program to find Minimum Spanning Tree of
a given graph using Prims Algorithm
Code:
import [Link].*;
class Main {
static List<[Link]<Integer,
List<[Link]<Integer, Integer>>>>
calculatePrimsMST(int n, int m,
List<[Link]<[Link]<Integer, Integer>,
Integer>> g) {
Map<Integer, List<[Link]<Integer,
Integer>>> adj = new HashMap<>();
for (int i = 0; i < [Link](); i++) {
int u = [Link](i).getKey().getKey();
int v = [Link](i).getKey().getValue();
int w = [Link](i).getValue();
[Link](u, k -> new
ArrayList<>()).add(new
[Link]<>(v, w));
[Link](v, k -> new
ArrayList<>()).add(new
[Link]<>(u, w));
}
List<Integer> key = new
ArrayList<>([Link](n + 1,
Integer.MAX_VALUE));
List<Boolean> mst = new
ArrayList<>([Link](n + 1, false));
List<Integer> parent = new
ArrayList<>([Link](n + 1, -1));
[Link](1, 0);
for (int i = 1; i <= n; i++) {
int mini = Integer.MAX_VALUE;
 int u = -1;
for (int v = 1; v <= n; v++) {
if ( && [Link](v) < mini) {
u = v;
mini = [Link](v);
}
}
[Link](u, true);
for ([Link]<Integer, Integer> it :
[Link](u, new ArrayList<>())) {
int v = [Link]();
int w = [Link]();
if ( && [Link](v) > w) {
[Link](v, w);
[Link](v, u);
}
}
}
List<[Link]<[Link]<Integer,
Integer>, Integer>> ans = new ArrayList<>();
for (int i = 2; i <= n; i++) {
[Link](new
[Link]<>(new
[Link]<>([Link](i), i),
[Link](i)));
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter number of vertices:
");
int n = [Link]();
[Link]("Enter number of edges: ");
int m = [Link]();
List<[Link]<[Link]<Integer,
Integer>, Integer>> g = new ArrayList<>();
for (int i = 0; i < m; i++) {
[Link]("Enter the edge and
weight: ");
int u = [Link]();
int v = [Link]();
 int w = [Link]();
[Link](new
[Link]<>(new
[Link]<>(u, v), w));
}
List<[Link]<[Link]<Integer,
Integer>, Integer>> ans = calculatePrimsMST(n,
m, g);
[Link]("\nMST edges are:");
for ([Link]<[Link]<Integer, Integer>,
Integer> entry : ans) {
[Link]([Link]().getKey()
+ " " + [Link]().getValue() + " " +
[Link]());
}
[Link]();
}
}
Output:
 Practical-6
Aim: Write a Program to implement Floyd Warshall
Algorithm
Code:
import [Link].*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter number of vertices:
");
int n = [Link]();
[Link]("Enter number of edges: ");
int m = [Link]();
int[][] g = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
[Link](g[i], Integer.MAX_VALUE);
}
for (int i = 0; i < m; i++) {
[Link]("Enter the edge and
weight: ");
int u = [Link]();
int v = [Link]();
int w =[Link]();
 g[u][v] = w;
}
for (int i = 1; i <= n; i++) {
g[i][i] = 0;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][k] != Integer.MAX_VALUE &&
g[k][j] != Integer.MAX_VALUE && g[i][k] + g[k][j]
< g[i][j]) {
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
[Link]("\nDistance Matrix:");
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
[Link](g[i][j] + " ");
}
[Link]();
}
[Link]();
}
}
Output:
 Practical-7
Aim: Write a Program to implement Knapsack Problem
using Dynamic Programming
Code:
import [Link];
public class Main {
static int knapSack(int W, int[] wt, int[] val, int
n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = [Link](val[i - 1] + dp[i -
1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
 public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of items:
");
int items = [Link]();
int[] profit = new int[items];
int[] weight = new int[items];
for (int i = 0; i < items; i++) {
[Link]("Enter the profit and
weight of item " + (i + 1) + ": ");
profit[i] = [Link]();
weight[i] = [Link]();
}
[Link]("Enter the capacity of the
knapsack: ");
int W = [Link]();
[Link]("Maximum profit is: " +
knapSack(W, weight, profit, items));
[Link]();
}
}

Output:
 Practical-8

Aim: Write a Program to implement N queens Problem using

Backtracking
Code:
import [Link].*;
public class Main {
static boolean isSafe(int row, int col, List<String> board, int
n) {
int x = row, y = col;
// Check row
while (y >= 0) {
if ([Link](x).charAt(y) == 'Q')
return false;
y--;
}
// Top left diagonal
x = row;
y = col;
while (x < n && y >= 0) {
 if ([Link](x).charAt(y) == 'Q')
return false;
x++;
y--;
}
// Bottom left diagonal
x = row;
y = col;
while (x >= 0 && y >= 0) {
if ([Link](x).charAt(y) == 'Q')
return false;
x--;
y--;
}
return true;
}
static void solve(int col, List<String> board, int n,
List<List<String>> ans) {
if (col == n) {
[Link](new ArrayList<>(board));
return;
}
for (int row = 0; row < n; row++) {
if (isSafe(row, col, board, n)) {
StringBuilder sb = new
StringBuilder([Link](row));
[Link](col, 'Q');
[Link](row, [Link]());
solve(col + 1, board, n, ans);
[Link](col, '.');
[Link](row, [Link]());
}
}
}
static List<List<String>> solveNQueens(int n) {
List<String> s = new ArrayList<>();
for (int i = 0; i < n; i++)
[Link](".");
List<String> board = new
ArrayList<>([Link](n, ""));
for (int i = 0; i < n; i++)
[Link](i, [Link](i));
 List<List<String>> ans = new ArrayList<>();
solve(0, board, n, ans);
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the value of n: ");
int n = [Link]();
List<List<String>> ans = solveNQueens(n);
int cnt = 1;
for (List<String> i : ans) {
[Link]("\nSolution no. " + cnt++);
for (String j : i) {
[Link](j);
}
[Link]();
}
[Link]();
}
}

Output:
 Practical-9

Aim: Write a Program to perform Travelling Salesman Problem

Code:
import [Link].*;
public class Main {
static final int V = 4;
static int travellingSalesmanProblem(int[][] graph, int s) {
List<Integer> vertex = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (i != s)
[Link](i);
}
int minPath = Integer.MAX_VALUE;
do {
int currentPathWeight = 0;
int k = s;
for (int i = 0; i < [Link](); i++) {
currentPathWeight += graph[k][[Link](i)];
k = [Link](i);
}
 currentPathWeight += graph[k][s];
minPath = [Link](minPath, currentPathWeight);
} while (nextPermutation(vertex));
return minPath;
}
static boolean nextPermutation(List<Integer> arr) {
int i = [Link]() - 2;
while (i >= 0 && [Link](i) >= [Link](i + 1)) {
i--;
}
if (i < 0) {
return false;
}
int j = [Link]() - 1;
while ([Link](j) <= [Link](i)) {
j--;
}
[Link](arr, i, j);
[Link]([Link](i + 1, [Link]()));
return true;
}
public static void main(String[] args) {
int[][] graph = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int s = 0;
[Link]("\nShortest Path is: " +
travellingSalesmanProblem(graph, s) + "\n\n");
}
}
Output:
 Practical-10

Aim: Write a Program to implement Knapsack Problem using

Branch and Bound
Code:
import [Link].*;
class Item {
float weight;
int value;
Item(float weight, int value) {
[Link] = weight;
[Link] = value;
}
}
class Node {
int level, profit, bound;
float weight;
}
public class Main {
static boolean cmp(Item a, Item b) {
double r1 = (double) [Link] / [Link];
 double r2 = (double) [Link] / [Link];
return r1 > r2;
}
static int bound(Node u, int n, int W, Item[] arr) {
if ([Link] >= W) return 0;
int profitBound = [Link];
int j = [Link] + 1;
int totWeight = (int) [Link];
while (j < n && totWeight + arr[j].weight <= W) {
totWeight += arr[j].weight;
profitBound += arr[j].value;
j++;
}
if (j < n) profitBound += (W - totWeight) * arr[j].value /
arr[j].weight;
return profitBound;
}
static int knapsack(int W, Item[] arr, int n) {
[Link](arr, (a, b) -> [Link]((double)
[Link] / [Link], (double) [Link] / [Link]));
Queue<Node> Q = new LinkedList<>();
Node u = new Node();
Node v = new Node();
[Link] = -1;
[Link] = 0;
[Link] = 0;
[Link](u);
int maxProfit = 0;
while (![Link]()) {
u = [Link]();
if ([Link] == -1) [Link] = 0;
if ([Link] == n - 1) continue;
[Link] = [Link] + 1;
[Link] = [Link] + arr[[Link]].weight;
[Link] = [Link] + arr[[Link]].value;
if ([Link] <= W && [Link] > maxProfit) maxProfit =
[Link];
[Link] = bound(v, n, W, arr);
if ([Link] > maxProfit) [Link](v);
[Link] = [Link];
[Link] = [Link];
[Link] = bound(v, n, W, arr);
 if ([Link] > maxProfit) [Link](v);
}
return maxProfit;
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the number of items: ");
int n = [Link]();
Item[] arr = new Item[n];
for (int i = 0; i < n; i++) {
[Link]("Enter the weight and value of item "
+ (i + 1) + ": ");
float weight = [Link]();
int value = [Link]();
arr[i] = new Item(weight, value);
}
[Link]("Enter the capacity of knapsack: ");
int W = [Link]();
[Link]("Maximum possible profit = " +
knapsack(W, arr, n));
[Link]();
}
}
Output: