DAA

By /

Binary search

import java.util.Scanner;
import java.util.Arrays;
class BinarySearch
{
	public static int binarySearch(int a[],int key,int low,int high)
	{
		if(low>high)
		return 0;
		else{
			 int mid=(low+high)/2;
			 if(key==a[mid])
			 return mid;
			 else if(key>a[mid])
			 return binarySearch(a,key,mid+1,high);
			 else
			 return binarySearch(a,key,low,mid-1);
		}
	}
 public static void main(String args[]){
 Scanner s=new Scanner(System.in);
 int n=s.nextInt();
 int a[]=new int[n];
 for(int i=0;i<n;i++)
 {
	a[i]=s.nextInt();
 }
 Arrays.sort(a);
 int key=s.nextInt();
 int low=0;
 int high=a.length;
 int result=binarySearch(a,key,low,high);
 System.out.println("The key value "+key+" found at the position "+result);
 }
 }
min max
import java.util.Scanner;
import java.util.Arrays;
class MinMaxOfArray
{
	public static void min_max(int a[])
	{
		int max=a[0];
		int min=a[0];
		for(int i=1;i<a.length;i++)
		{
			if(a[i]>max)
			max=a[i];
			if(a[i]<min) 
			min=a[i];
		}
		System.out.println("Min element of array "+min);
		System.out.println("Max element of array "+max);
	}
 public static void main(String args[]){
 Scanner s=new Scanner(System.in);
 int n=s.nextInt();
 int a[]=new int[n];
 for(int i=0;i<n;i++)
 {
	a[i]=s.nextInt();
 }
 min_max(a);

 }
 }
merge sort
import java.util.Arrays;
 class Mergesort{
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original Array: " + Arrays.toString(array));       
        mergeSort(array, 0, array.length - 1);        
        System.out.println("Sorted Array: " + Arrays.toString(array));
    }
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;       
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);          
            merge(array, left, mid, right);
        }
    }
    public static void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];
        for (int i = 0; i < n1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = array[mid + 1 + j];
        }
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
       while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

quick sort

import java.util.Arrays;
 class Quicksort {
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original Array: " + Arrays.toString(array));
        
        quickSort(array, 0, array.length - 1);
        
        System.out.println("Sorted Array: " + Arrays.toString(array));
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }+
    public static int partition(int[] array, int low, int high) {       
        int pivot = array[high];
        int i = low - 1; 
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
               
                swap(array, i, j);
            }
        }        
        swap(array, i + 1, high);
        return i + 1; 
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

stressans matrix

import java.util.Scanner;
public class Strassen
{
    public int[][] multiply(int[][] A, int[][] B)
    {        
        int n = A.length;
        int[][] R = new int[n][n];
        if (n == 1)
            R[0][0] = A[0][0] * B[0][0];
        else
        {
            int[][] A11 = new int[n/2][n/2];
            int[][] A12 = new int[n/2][n/2];
            int[][] A21 = new int[n/2][n/2];
            int[][] A22 = new int[n/2][n/2];
            int[][] B11 = new int[n/2][n/2];
            int[][] B12 = new int[n/2][n/2];
            int[][] B21 = new int[n/2][n/2];
            int[][] B22 = new int[n/2][n/2];
  
            split(A, A11, 0 , 0);
            split(A, A12, 0 , n/2);
            split(A, A21, n/2, 0); 
			
            split(A, A22, n/2, n/2);
            split(B, B11, 0 , 0);
            split(B, B12, 0 , n/2);
            split(B, B21, n/2, 0);
            split(B, B22, n/2, n/2);
  
            int [][] M1 = multiply(add(A11, A22), add(B11, B22));
            int [][] M2 = multiply(add(A21, A22), B11);
            int [][] M3 = multiply(A11, sub(B12, B22));
            int [][] M4 = multiply(A22, sub(B21, B11));
            int [][] M5 = multiply(add(A11, A12), B22);
            int [][] M6 = multiply(sub(A21, A11), add(B11, B12));
            int [][] M7 = multiply(sub(A12, A22), add(B21, B22));
  
          
            int [][] C11 = add(sub(add(M1, M4), M5), M7);
            int [][] C12 = add(M3, M5);
            int [][] C21 = add(M2, M4);
            int [][] C22 = add(sub(add(M1, M3), M2), M6);
  
            join(C11, R, 0 , 0);
            join(C12, R, 0 , n/2);
            join(C21, R, n/2, 0);
            join(C22, R, n/2, n/2);
        }
        return R;
    }
    public int[][] sub(int[][] A, int[][] B)
    {
        int n = A.length;
        int[][] C = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                C[i][j] = A[i][j] - B[i][j];
        return C;
    }
    public int[][] add(int[][] A, int[][] B)
    {
        int n = A.length;
        int[][] C = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                C[i][j] = A[i][j] + B[i][j];
        return C;
    }
    public void split(int[][] P, int[][] C, int iB, int jB) 
    {
        for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
            for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
                C[i1][j1] = P[i2][j2];
    }
    public void join(int[][] C, int[][] P, int iB, int jB) 
    {
        for(int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
            for(int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
                P[i2][j2] = C[i1][j1];
    }    
    public static void main (String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Strassen Multiplication Algorithm Test\n");
        Strassen s = new Strassen();
  
         
        int N = 4;
         
        int[][] A =     { { 1, 1, 1, 1 },
                        { 2, 2, 2, 2 },
                        { 3, 3, 3, 3 },
                        { 2, 2, 2, 2 } };
 
        int[][] B =     { { 1, 1, 1, 1 },
                        { 2, 2, 2, 2 },
                        { 3, 3, 3, 3 },
                        { 2, 2, 2, 2 } };
        System.out.println("\nArray A =>");
     
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(A[i][j] +" ");
            System.out.println();
        }
         
        System.out.println("\nArray B =>");
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(B[i][j] +" ");
            System.out.println();
        }
  
        int[][] C = s.multiply(A, B);
  
        System.out.println("\nProduct of matrices A and  B : ");
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                System.out.print(C[i][j] +" ");
            System.out.println();
        }
  
    }
}

knapsack problem

public class KnapSack{
	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(w=0;w<w;w++)
			{
				if(i==0||w==0)
					dp[i][w]=0;
				else if(wt[i-1]<=w)
					dp[i][w]=Math.max(val[i-1]+dp[i-1][w-wt[i-6]],dp[i][w]);
				else
					dp[i][w]=dp[i-1][w];
			}
		}
			return dp[n][w];
	}
	public static void main(String args[])
	{
		int val[]={60,100,120};
		int wt[]={10,20,30};
		int w=50;
		int n=val.length;
		System.out.print("Max value in KnapSack "+knapSack(w,wt,val,n));
	}
}
job sequencing
import java.util.*;
class Job {
    char id;
    int deadline, profit;

    Job(char id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}
class JobSequencing {
    void printJobScheduling(Job arr[], int n) {
        Arrays.sort(arr, (a, b) -> b.profit - a.profit);
        boolean[] result = new boolean[n];
        char[] job = new char[n];
        for (int i = 0; i < n; i++) {
            for (int j = Math.min(n, arr[i].deadline) - 1; j >= 0; j--) {
                if (!result[j]) {
                    result[j] = true;
                    job[j] = arr[i].id;
                    break;
                }
            }
        }
        for (char jb : job) {
            if (jb != '\u0000')
                System.out.print(jb + " ");
        }
    }
    public static void main(String args[]) {
        Job arr[] = {
            new Job('a', 2, 100),
            new Job('b', 1, 19),
            new Job('c', 2, 27),
            new Job('a', 1, 25),
            new Job('d', 2, 15)
        };
        int n = arr.length;
        System.out.println("Following is the maximum profit sequence of jobs: ");
        JobSequencing jobSequencing = new JobSequencing();
        jobSequencing.printJobScheduling(arr, n);
    }
}

shortest path/dijkstra

import java.util.*;
import java.lang.*;
import java.io.*;
class ShortestPath{
	static final int V=9;
	int minDistance(int dist[],Boolean sptSet[]){
		int min=Integer.MAX_VALUE,min_index=-1;
		for(int v=0;v<V;v++)
			if(sptSet[v]==false && dist[v]<=min)
			{
				min=dist[v];
				min_index=v;
			}
			return min_index;
	}
	void printSolution(int dist[],int n)
	{
		System.out.println("Vertex distance from source: ");
		for(int i=0;i<V;i++)
		{
			System.out.println(i+" "+dist[i]);
		}
	}
	void dijkstra(int graph[][],int src)
	{
		int dist[]=new int[V];
		Boolean sptSet[]=new Boolean[V];
		for(int i=0;i<V;i++)
		{
			dist[i]=Integer.MAX_VALUE;
			sptSet[i]=false;
		}
		dist[src]=0;
		for(int count=0;count<V-1;count++)
		{
			int u=minDistance(dist,sptSet);
			sptSet[u]=true;
			for(int v=0;v<V;v++)
			{
				if(!sptSet[v] && graph[u][v]!=0 && dist[u]!=Integer.MAX_VALUE && dist[u]+graph[u][v]<dist[v])
					dist[v]=dist[u]+graph[u][v];
			}
		}
		printSolution(dist,V);
	}
	public static void main(String args[])
	{
		int graph[][]=new int[][]{{0,4,0,0,0,0,0,8,0},
				{4,0,8,0,0,0,0,11,0},
				{0,8,0,7,0,4,0,0,2},
				{0,0,7,0,9,14,0,0,0},
				{0,0,0,9,0,10,0,0,0},
				{0,0,4,14,10,0,2,0,0},
				{0,0,0,0,0,2,0,1,6},
				{8,11,0,0,0,0,1,0,7},
				{0,0,2,0,0,0,6,7,0}};
		ShortestPath t=new ShortestPath();
		t.dijkstra(graph,0);
	}
}
N Queens
public class NQueenProblem{
	final int N=4;
	void printSolution(int board[][])
	{
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
				System.out.println(" "+board[i][j]+" ");
			System.out.println();
		}
	}
	boolean isSafe(int[][] board,int row,int col)
	{
		int i,j;
		for(i=0;i<col;i++)
			if(board[row][i]==1)
				return false;
		for(i=row,j=col;i>=0&&j>=0;i--,j--)
			if(board[i][j]==1)
				return false;
		for(i=row,j=col;i<N && j>=0;i++,j--)
			if(board[i][j]==1)
				return false;
		return true;
	}
	boolean solveNQUtil(int board[][],int col)
	{
		if(col>=N)
			return true;
		for(int i=0;i<N;i++){
			if(isSafe(board,i,col))
			{
				board[i][col]=1;
				if(solveNQUtil(board,col+1)==true)
					return true;
				board[i][col]=0;
			}
		}
		return false;
	}
	boolean solveNQ()
	{
		int board[][]={{0,0,0,0},
			{0,0,0,0},
			{0,0,0,0},
			{0,0,0,0}};
		if(solveNQUtil(board,0)==false){
			System.out.println("Solution does not exist");
			return false;
		}
		printSolution(board);
		return true;
	}
	public static void main(String args[])
	{
		NQueenProblem Queen=new NQueenProblem();
		Queen.solveNQ();
	}
}

sum of subsets

import java.util.ArrayList;
import java.util.List;
public class SubSetSum{
public static void findSubSetSum(int[] nums,int index,int currentSum,List<Integer> result)
{
	if(index==nums.length){
		result.add(currentSum);
		return;
	}
	findSubSetSum(nums,index+1,currentSum+nums[index],result);
	findSubSetSum(nums,index+1,currentSum,result);
}
public static List<Integer> subsetSums(int[] nums)
{
	List<Integer> result=new ArrayList<>();
	findSubSetSum(nums,0,0,result);
	return result;
}
public static void main(String args[])
{	
	int[] nums={1,2,3};
	List<Integer> sums=subsetSums(nums);
	System.out.println("Subset sums: "+sums);
}
}

Bellman ford single source shortest path

import java.util.Arrays;
class Bellman
{
    public static int[] function(int V, int[][] edges, int src)
    {
        int[] dist = new int[V];
        Arrays.fill(dist, (int)1e8);
        dist[src]=0;
        for(int i=0;i<V;i++)
        {
            for(int[] edge: edges)
            {
                int u=edge[0];
                int v=edge[1];
                int wt=edge[2];
                if(dist[u]!=1e8 && dist[u]+wt<dist[v])
                {
                    if(i==V)
                    {
                        return new int[]{-1};
                    }
                    dist[v]=dist[u]+wt;
                }
            }
        }
        return dist;
    }
    public static void main(String args[])
    {
        int V=5;
        int src=0;
        int[][] edges=new int[][]{
            {1,3,2},
                {4,3,-1},
                    {2,4,1},
                        {1,2,1},
                            {0,1,5}
        };
        int[] res = function(V, edges,src);
        for(int dist:res)
        {
            System.out.println(dist+” “);
        }
        
    }
}

 

all pairs shortest path

import java.util.Arrays;
public class AllPairsShortestPath {
    final static int INF = 99999; // Represents “infinity” for unreachable paths
    public static void floydWarshall(int[][] graph) {
        int V = graph.length; // Number of vertices
        int[][] dist = new int[V][V];
        for (int i = 0; i < V; i++) {
            dist[i] = Arrays.copyOf(graph[i], V);
        }
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        printSolution(dist);
    }
    public static void printSolution(int[][] dist) {
        int V = dist.length;
        System.out.println(“Shortest distances between every pair of vertices:”);
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    System.out.print(“INF “);
                } else {
                    System.out.print(dist[i][j] + ” “);
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[][] graph = {
                {0, 3, INF, INF},
                {INF, 0, 1, INF},
                {INF, INF, 0, 7},
                {6, INF, INF, 0}
        };
        floydWarshall(graph);
    }
}

 

travelling sales person

import java.util.*;
public class TravellingSalesperson {
    final static int INF = Integer.MAX_VALUE;
    public static int tsp(int[][] graph, int pos, int visited, int[][] dp) {
        int n = graph.length;
        if (visited == (1 << n) – 1) { // All cities visited
            return graph[pos][0]; // Return to starting city
        }
        if (dp[pos][visited] != -1) { // If already computed
            return dp[pos][visited];
        }
        int minCost = INF;
        for (int city = 0; city < n; city++) {
            if ((visited & (1 << city)) == 0) { // If city not visited
                int cost = graph[pos][city] + tsp(graph, city, visited | (1 << city), dp);
                minCost = Math.min(minCost, cost);
            }
        }
        dp[pos][visited] = minCost;
        return minCost;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print(“Enter number of cities: “);
        int n = scanner.nextInt();
        int[][] graph = new int[n][n];
        System.out.println(“Enter adjacency matrix (distances between cities):”);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
        int[][] dp = new int[n][1 << n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        System.out.println(“Minimum distance to travel all cities: ” +
                tsp(graph, 0, 1, dp)); // Start from city 0
    }
}

Please follow and like us:
error
fb-share-icon
Tweet
fb-share-icon
Paste text,images,html and share with anyone
Scroll to Top