DAA LAb

Merge Sort

class MergeSort {
    int arr[] = {17, 2, 15, 21, 8, 1};
 
    void sort(int l, int r) {
        if (l < r) {
            int mid = (l+r) / 2;
            sort(l, mid);
            sort(mid+1, r);
            merge(l, mid, r);
        }
    }
 
    void merge(int l, int mid, int r) {
        int n1 = mid - l + 1;
        int n2 = r - mid;
 
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        for (int i = 0; i < n1; i++)
            L[i] = arr[l+i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
 
        int i = 0, j = 0, k = l;
        while( i < n1 && j < n2) {
            if (L[i] < R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        while(i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while(j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    void print() {
        System.out.println("Elements of array:");
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
    }
 
    public static void main(String args[]) {
        MergeSort s = new MergeSort();
        s.sort(0, s.arr.length-1);
        s.print();
    }
}

Quick Sort

class QuickSort {
    int arr[] = {17, 2, 15, 21, 8, 1};
 
    void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
 
    int partition(int l, int r) {
        int pivot = arr[r];
 
        int p = l - 1;
        for (int i = l; i < r; i++) {
            if (arr[i] <= pivot) {
                p++;
                swap(p, i);
            }
        }
        swap(p+1, r);
        return p+1;
    }
 
    void sort(int l, int r) {
        if (l < r) {
            int p = partition(l, r);
            sort(l, p-1);
            sort(p+1, r);
        }
    }
 
    void print() {
        System.out.println("Elements of array:");
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);
    }
 
    public static void main(String args[]) {
        QuickSort s = new QuickSort();
        s.sort(0, s.arr.length-1);
        s.print();
    }
}

Depth First Search

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
 
public class DFS
{
    private Stack<Integer> stack;
    public DFS()
    {
        stack = new Stack<Integer>();
    }
 
    public void dfs(int adjacency_matrix[][], int source)
    {
        int number_of_nodes = adjacency_matrix[source].length - 1;
        int visited[] = new int[number_of_nodes + 1];
        int element = source;
        int i = source;
        System.out.print(element + "\t");
        visited[source] = 1;
        stack.push(source);
        while (!stack.isEmpty())
        {
            element = stack.peek();
            i = element;
            while (i <= number_of_nodes)
            {
                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
                {
                    stack.push(i);
                    visited[i] = 1;
                    element = i;
                    i = 1;
                    System.out.print(element + "\t");
                    continue;
                }
                i++;
            }
            stack.pop();
        }
    }
    public static void main(String...arg)
    {
        int number_of_nodes, source;
        Scanner scanner = null;
        try
        {
            System.out.println("Enter the number of nodes in the graph");
            scanner = new Scanner(System.in);
            number_of_nodes = scanner.nextInt();
            int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
            System.out.println("Enter the adjacency matrix");
            for (int i = 1; i <= number_of_nodes; i++)
                for (int j = 1; j <= number_of_nodes; j++)
                    adjacency_matrix[i][j] = scanner.nextInt();
            System.out.println("Enter the source for the graph");
            source = scanner.nextInt();
            System.out.println("The DFS Traversal for the graph is given by ");
            DFS dfs = new DFS();
            dfs.dfs(adjacency_matrix, source);
        }catch(InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input format");
        }
        scanner.close();
    }
}

Output

Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The DFS Traversal for the graph is given by
1 2 3 4

Breadth First Search

import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class BFS
{
    private Queue<Integer> queue;
    public BFS()
    {
        queue = new LinkedList<Integer>();
    }
 
    public void bfs(int adjacency_matrix[][], int source)
    {
        int number_of_nodes = adjacency_matrix[source].length - 1;
        int[] visited = new int[number_of_nodes + 1];
        int i, element;
        visited[source] = 1;
        queue.add(source);
        while (!queue.isEmpty())
        {
            element = queue.remove();
            i = element;
            System.out.print(i + "\t");
            while (i <= number_of_nodes)
            {
                if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
                {
                    queue.add(i);
                    visited[i] = 1;
                }
                i++;
            }
        }
    }
 
    public static void main(String... arg)
    {
        int number_no_nodes, source;
        Scanner scanner = null;
        try
        {
            System.out.println("Enter the number of nodes in the graph");
            scanner = new Scanner(System.in);
            number_no_nodes = scanner.nextInt();
            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
            System.out.println("Enter the adjacency matrix");
            for (int i = 1; i <= number_no_nodes; i++)
                for (int j = 1; j <= number_no_nodes; j++)
                    adjacency_matrix[i][j] = scanner.nextInt();
            System.out.println("Enter the source for the graph");
            source = scanner.nextInt();
            System.out.println("The BFS traversal of the graph is ");
            BFS bfs = new BFS();
            bfs.bfs(adjacency_matrix, source);
        } catch (InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input Format");
        }
        scanner.close();
    }
}

Output

Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The DFS Traversal for the graph is given by
1 2 3 4

Job Sequencing

import java.util.*;
 
public class Job
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the number of Jobs");
        int n=sc.nextInt();
        String a[]=new String[n];
        int b[]=new int[n];
        int c[]=new int[n];
        for(int i=0;i<n;i++)
        {
            System.out.println("Enter the Jobs");
            a[i]=sc.next();
            System.out.println("Enter the Profit");
            b[i]=sc.nextInt();
            System.out.println("Enter the DeadLine");
            c[i]=sc.nextInt();
        }
        System.out.println("--Arranged Order--\nJobs: ");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.print("\nProfit: ");
        for(int i=0;i<n;i++)
        {
            System.out.print(b[i]+" ");
        }
        System.out.print("\nDeadLine:");
        for(int i=0;i<n;i++)
        {
            System.out.print(c[i]+" ");
        }
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(b[i]<b[j])
                {
                    int temp=b[i];
                    b[i]=b[j];
                    b[j]=temp;
                    temp=c[i];
                    c[i]=c[j];
                    c[j]=temp;
                    String temp1=a[i];
                    a[i]=a[j];
                    a[j]=temp1;
                }
            }
        }
        System.out.println("\n--Sorted Order--\nJobs: ");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.print("\nProfit: ");
        for(int i=0;i<n;i++)
        {
            System.out.print(b[i]+" ");
        }
        System.out.print("\nDeadLine:");
        for(int i=0;i<n;i++)
        {
            System.out.print(c[i]+" ");
        }
        System.out.println();
        int max=c[0];
        for(int i=0;i<n;i++)
        {
            if(c[i]>max)
            {
                max=c[i];
            }
        }
        String x[]=new String[max];
        int xx[]=new int[max];
        int profit=0;
        for(int i=0;i<n;i++)
        {
            int pp=c[i];
            pp=pp-1;
            if(x[pp]==null )
            {
                x[pp]=a[i];
                profit+=b[i];
            }
            else
            {
                while(pp!=-1)
                {
                    if(x[pp]==null)
                    {
                        x[pp]=a[i];
                        profit+=b[i];
                        break;
                    }
                    pp=pp-1;
                }
            }
        }
        for(int i=0;i<max;i++)
        {
            System.out.print("-->"+x[i]);
        }
        System.out.print("\nProfit Earned"+profit);
    }
}

Kruskal’s

import java.util.*;
import java.util.Scanner;
 
class Graph {
    class Edge implements Comparable<Edge> {
        int src, dst, weight;
 
        public int compareTo(Edge another) {
            return this.weight - another.weight;
        }
    };
 
    // Union
    class subset {
        int parent, rank;
    }
 
    int vertices, edges;
    Edge edge[];
 
    Graph (int v, int e) {
        vertices = v;
        edges = e;
        edge = new Edge[edges];
        for (int i = 0; i < e; i++)
            edge[i] = new Edge();
    }
 
    int find (subset s[], int i) {
        if (s[i].parent != i)
            s[i].parent = find(s, s[i].parent);
        return s[i].parent;
    }
 
    void Union (subset s[], int x, int y) {
        int xroot = find(s, x);
        int yroot = find(s, y);
 
        if (s[xroot].rank < s[yroot].rank)
            s[xroot].parent = yroot;
        else if (s[xroot].rank > s[yroot].rank)
            s[yroot].parent = xroot;
        else {
            s[yroot].parent = xroot;
            s[xroot].rank++;
        }
    }
 
    void Kruskal() {
        Edge result[] = new Edge[vertices];
        int i = 0, e = 0;
 
        for (i = 0; i < vertices; i++)
            result[i] = new Edge();
 
        Arrays.sort(edge);
        subset[] s = new subset[vertices];
        for (i = 0; i < vertices; i++) {
            s[i] = new subset();
            s[i].parent = i;
            s[i].rank = 0;
        }
 
        i = 0;
        while (e < vertices - 1 && i < edges) {
            Edge nextEdge = new Edge();
            nextEdge = edge[i++];
            int x = find(s, nextEdge.src);
            int y = find(s, nextEdge.dst);
 
            if (x != y) {
                result[e++] = nextEdge;
                Union(s, x, y);
            }
        }
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " - " + result[i].dst + ": " + result[i].weight);
    }
 
    public static void main(String[] args) {
        int vertices = 6; // Number of vertices
        int edges = 8; // Number of edges
        Graph G = new Graph(vertices, edges);
 
        G.edge[0].src = 0;
        G.edge[0].dst = 1;
        G.edge[0].weight = 4;
 
        G.edge[1].src = 0;
        G.edge[1].dst = 2;
        G.edge[1].weight = 4;
 
        G.edge[2].src = 1;
        G.edge[2].dst = 2;
        G.edge[2].weight = 2;
 
        G.edge[3].src = 2;
        G.edge[3].dst = 3;
        G.edge[3].weight = 3;
 
        G.edge[4].src = 2;
        G.edge[4].dst = 5;
        G.edge[4].weight = 2;
 
        G.edge[5].src = 2;
        G.edge[5].dst = 4;
        G.edge[5].weight = 4;
 
        G.edge[6].src = 3;
        G.edge[6].dst = 4;
        G.edge[6].weight = 3;
 
        G.edge[7].src = 5;
        G.edge[7].dst = 4;
        G.edge[7].weight = 3;
        G.Kruskal();
    }
}

Prim’s Algorithm

import java.util.Arrays;
 
class Prims {
 
  public void Prim(int G[][], int V) {
    int edges = 0;
 
    boolean[] selected = new boolean[V];
    Arrays.fill(selected, false);
    selected[0] = true;
 
    System.out.println("Edge : Weight");
    while (edges < V - 1) {
        int min = Integer.MAX_VALUE, x = 0, y = 0;
        for (int i = 0; i < V; i++) {
            if (selected[i]) {
                for (int j = 0; j < V; j++) {
                    if (!selected[j] && G[i][j] != 0) {
                        if (min > G[i][j]) {
                            min = G[i][j];
                            x = i;
                            y = j;
                        }
                    }
                }
            }
        }
        System.out.println(x + " - " + y + " :  " + G[x][y]);
        selected[y] = true;
        edges++;
    }
  }
 
  public static void main(String[] args) {
    Prims g = new Prims();
    int V = 5;
    int[][] G = { { 0, 9, 75, 0, 0 },
        { 9, 0, 95, 19, 42 },
        { 75, 95, 0, 51, 66 },
        { 0, 19, 51, 0, 31 },
        { 0, 42, 66, 31, 0 } };
 
    g.Prim(G, V);
  }
}

Knapsack Problem

import java.util.Arrays;
 
class Knapsack {
    int[] solve(int[] price, int[] weight, int max) {
        int arr[][] = new int[price.length+1][max+1];
        Arrays.fill(arr[0], 0);
        for (int i = 0; i < arr.length; i++)
            arr[i][0] = 0;
 
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                if (j - weight[i-1] < 0 || j - weight[i-1] > max)
                    arr[i][j] = arr[i-1][j];
                else
                    arr[i][j] = Math.max(arr[i-1][j], (arr[i-1][j-weight[i-1]] + price[i-1]));
            }
        }
 
        int[] ans = new int[price.length];
        Arrays.fill(ans, 0);
        int tmp = arr[price.length][max];
 
        for (int i = arr.length - 2; i > 0; i--) {
            for (int j = arr[0].length - 1; j > 0; j--) {
                if (arr[i][j] == tmp)
                    break;
                if (arr[i][j] < tmp) {
                    ans[i] = 1;
                    tmp -= price[i]; break;
                }
            }
        }
 
 
        return ans;
    }
 
    public static void main(String args[]) {
        Knapsack k = new Knapsack();
        int[] weight = {2, 3, 4, 5};
        int[] price = {1, 2, 5, 6};
        int max = 8;
        int ans[] = k.solve(price, weight, max);
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == 1)
                System.out.println(weight[i]);
        }
    }
}
 

Optimal Binary Search Tree

import java.util.*;
 
class OptimalBST {
    int[][] cost;
 
    int Sum(int freq[], int i, int j) {
        int s = 0;
        for (int k = i; k <= j; k++)
            s += freq[k];
        return s;
    }
 
    int cache(int freq[], int i, int j) {
        if (i < 0 || j < 0)
            return 0;
        if (cost[i][j] != 0)
            return cost[i][j];
 
        int sum = Sum(freq, i, j);
        int Min = Integer.MAX_VALUE;
        for (int r = i; r <= j; r++) {
            int c = cache(freq, i, r-1) + cache(freq, r + 1, j)+sum;
            if (c < Min) {
                Min = c;
                cost[i][j] = c;
            }
        }
        return cost[i][j];
    }
 
    int solve(int keys[], int freq[], int n) {
        cost = new int[n+1][n+1];
        for (int i = 0; i < n; i++)
            Arrays.fill(cost[i], 0);
        for (int i = 0; i < n; i++)
            cost[i][i] = freq[i];
        return cache(freq, 0, n - 1);
    }
 
    public static void main(String[] args) {
        int keys[] = { 10, 12, 20 };
        int freq[] = { 34, 8, 50 };
        int n = keys.length;
 
        OptimalBST t = new OptimalBST();
        System.out.println( "Cost of Optimal BST is " + t.solve(keys, freq, n));
    }
}

All path Shortest (Floyd)

class FloydWarshall {
    void solve(int arr[][]) {
        int A = 0;
        while (A < arr.length) { 
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    if (i != A && j != A && i != j) {
                        if (arr[i][j] == 0)
                            arr[i][j] = arr[i][A] + arr[A][j];
                        else
                            arr[i][j] = Math.min(arr[i][j], (arr[i][A] + arr[A][j]));
                    }
                }
            }
            A++;
        }
    }
 
    public static void main(String args[]) {
        int[][] arr = {{0, 3, 0, 7},
            {8, 0, 2, 0},
            {5, 0, 0, 1},
            {2, 0, 0, 0}};
        FloydWarshall f = new FloydWarshall();
        f.solve(arr);
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++)
                System.out.print(arr[i][j]);
            System.out.println();
        }
    }
}

NQueen Problem

import java.util.Arrays;
 
class NQueen {
    int[][] board;
 
    void solve(int n) {
        board = new int[n][n];
        for (int i=0; i < n; i++)
            Arrays.fill(board[i], 0);
        
        if (backTrack(0)) {
            for (int i = 0; i < n; i++) {
                for (int j =0; j < n; j++)
                    System.out.print(board[i][j]);
                System.out.println();
            }
        }
    }
 
    boolean backTrack(int row) {
        if (row >= board.length)
            return true;
 
        for (int j = 0; j < board.length; j++) {
            if (isSafe(row, j)) {
                board[row][j] = 1;
                if (backTrack(row+1) == true)
                    return true;
                board[row][j] = 0;
            }
        }
        return false;
    }
 
    boolean isSafe(int row, int col) {
        int i, j;
        for (i = 0; i < board.length; i++)
            if (board[i][col] == 1)
                return false;
        for (i = row-1, j = col-1; i>=0 && j>=0; i--,j--)
            if (board[i][j] == 1)
                return false;
        for (i = row-1, j = col+1; i >=0 && j < board.length; i--,j++)
            if (board[i][j] == 1)
                return false;
 
        return true;
    }
 
    public static void main(String args[]) {
        NQueen b = new NQueen();
        b.solve(4);
    }
}

Sum of Subsets

import java.util.Scanner;
 
public class SumOfSubsets {
    int[] w;
    int[] x;
    int sum;
    public void process() {
        getData();
    }
    private void getData() {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements:");
        int n = sc.nextInt();
        w = new int[n + 1];
        x = new int[n + 1];
        int total = 0;
        System.out.println("Enter " + n + " Elements :");
        for (int i = 1; i < n + 1; i++) {
            w[i] = sc.nextInt();
            total += w[i];
        }
        System.out.println("Enter the sum to be obtained: ");
        sum = sc.nextInt();
        if (total < sum) {
            System.out.println("Not possible to obtain the subset!!!");
            System.exit(1);
        }
        subset(0, 1, total);
    }
    private void subset(int s, int k, int r) {
        int i = 0;
        x[k] = 1;
        if (s + w[k] == sum) {
            System.out.println();
            for (i = 1; i <= k; i++) {
                System.out.print("\t" + x[i]);
            }
        } else if ((s + w[k] + w[k + 1]) <= sum) {
            subset(s + w[k], k + 1, r - w[k]);
        }
        if ((s + r - w[k]) >= sum && (s + w[k + 1]) <= sum) {
            x[k] = 0;
            subset(s, k + 1, r - w[k]);
        }
    }
    public static void main(String[] args) {
        new SumOfSubsets().process();
    }
}

Output

Enter the number of elements:4
Enter 4 Elements :
7
11
13
24
Enter the sum to be obtained:
31
1 1 1
1 0 0 1

Hamilton Problem

import java.util.Scanner;
import java.util.Arrays;
 
public class HamiltonianCycle {
    private int V, pathCount;
    private int[] path;
    private int[][] graph;
 
    public void findHamiltonianCycle(int[][] g) {
        V = g.length;
        path = new int[V];
        Arrays.fill(path, -1);
        graph = g;
        try {
            path[0] = 0;
            pathCount = 1;
            solve(0);
            System.out.println("No solution");
        } catch (Exception e) {
            System.out.println(e.getMessage());
            display();
        }
    }
 
    public void solve(int vertex) throws Exception {
        if (graph[vertex][0] == 1 && pathCount == V)
            throw new Exception("Solution found");
        if (pathCount == V)
            return;
        for (int v = 0; v < V; v++) {
            if (graph[vertex][v] == 1 ) {
                path[pathCount++] = v;
                graph[vertex][v] = 0;
                graph[v][vertex] = 0;
                if (!isPresent(v))
                    solve(v);
                graph[vertex][v] = 1;
                graph[v][vertex] = 1;
                path[--pathCount] = -1;
            }
        }
    }
 
    public boolean isPresent(int v) {
        for (int i = 0; i < pathCount - 1; i++)
            if (path[i] == v)
                return true;
        return false;
    }
 
    public void display() {
        System.out.print("\nPath : ");
        for (int i = 0; i <= V; i++)
            System.out.print(path[i % V] +" ");
        System.out.println();
    }
 
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("HamiltonianCycle Algorithm Test\n");
        HamiltonianCycle hc = new HamiltonianCycle();
        System.out.println("Enter number of vertices\n");
        int V = scan.nextInt();
        System.out.println("\nEnter matrix\n");
        int[][] graph = new int[V][V];
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                graph[i][j] = scan.nextInt();
        hc.findHamiltonianCycle(graph);
    }
}

Graph Coloring

import java.util.Scanner;
 
public class GraphColoring
{
    private int V, numOfColors;
    private int[] color;
    private int[][] graph;
    public void graphColor(int[][] g, int noc)
    {
        V = g.length;
        numOfColors = noc;
        color = new int[V];
        graph = g;
        try
        {
            solve(0);
            System.out.println("No solution");
        }
        catch (Exception e)
        {
            System.out.println("\nSolution exists ");
            display();
        }
    }
    public void solve(int v) throws Exception
    {
        if (v == V)
            throw new Exception("Solution found");
        for (int c = 1; c <= numOfColors; c++)
        {
            if (isPossible(v, c))
            {
                color[v] = c;
                solve(v + 1);
                color[v] = 0;
            }
        }
    }
    public boolean isPossible(int v, int c)
    {
        for (int i = 0; i < V; i++)
            if (graph[v][i] == 1 && c == color[i])
                return false;
        return true;
    }
    public void display()
    {
        System.out.print("\nColors : ");
        for (int i = 0; i < V; i++)
            System.out.print(color[i] +" ");
        System.out.println();
    }
    public static void main (String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Graph Coloring Algorithm Test\n");
        GraphColoring gc = new GraphColoring();
        System.out.println("Enter number of verticesz\n");
        int V = scan.nextInt();
        System.out.println("\nEnter matrix\n");
        int[][] graph = new int[V][V];
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                graph[i][j] = scan.nextInt();
        System.out.println("\nEnter number of colors");
        int c = scan.nextInt();
        gc.graphColor(graph, c);
    }
}

Output

Graph Coloring Algorithm Test
Enter number of vertices
4
Enter matrix
1 0 1 0
0 0 0 1
1 1 1 0
1 0 0 1
Enter number of colors
2
Solution exists
Colors : 1 1 2 2