DFS implementation in java

 package javaCodes;

import java.util.Arrays;

import java.util.Scanner;

class dfs_algorithm

{

void dfs_traversal(int graph[][], int source, boolean visited[], int total_vertices)

{

System.out.print(source+"  ");

visited[source] = true;

for(int i=0; i<total_vertices; i++)

{

if(graph[source][i] == 1 && !visited[i])

{

dfs_traversal(graph, i, visited, total_vertices);

}

}

}

}

public class DFS {

public static void main(String args[])

{

int total_vertices, edges, left_node, right_node;

Scanner sc = new Scanner(System.in);

System.out.println("Enter total number of vertices and esges : ");

total_vertices = sc.nextInt();

edges = sc.nextInt();

boolean visited[] = new boolean[total_vertices+1];

Arrays.fill(visited, false);

int g[][] = new int[total_vertices+1][total_vertices+1];

System.out.println("Enter values of nodes according to each edge : ");

for(int i=0; i<edges; i++)

{

left_node = sc.nextInt();

right_node = sc.nextInt();

g[left_node][right_node] = 1;

g[right_node][left_node] = 1;

}

int source;

System.out.print("Enter source : ");

source = sc.nextInt();

dfs_algorithm dfs = new dfs_algorithm();

dfs.dfs_traversal(g, source, visited, total_vertices);

}

}

BFS implementation in Java

 package javaCodes;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

class bfs_graph

{

void bfs_traversal(int g[][], int source, int total_vertices)

{

Queue<Integer> queue = new LinkedList<>();

queue.add(source);

boolean visited[] = new boolean[total_vertices];

Arrays.fill(visited, false);

System.out.print("BFS sequence : ");

while(queue.size() > 0)

{

int top = queue.remove();

if(!visited[top])

{

visited[top] = true;

System.out.print(top+"  ");

for(int i=0; i<total_vertices; i++)

{

if(g[top][i] == 1 && !visited[i])

{

queue.add(i);

}

}

}

}

}

}

public class BFS {

public static void main(String args[])

{

int total_vertices, edges, left_node, right_node;

Scanner sc = new Scanner(System.in);

System.out.println("Enter total number of vertices and esges : ");

total_vertices = sc.nextInt();

edges = sc.nextInt();

int g[][] = new int[total_vertices+1][total_vertices+1];

System.out.println("Enter values of nodes according to each edge : ");

for(int i=0; i<edges; i++)

{

left_node = sc.nextInt();

right_node = sc.nextInt();

g[left_node][right_node] = 1;

g[right_node][left_node] = 1;

}

int source;

System.out.print("Enter source : ");

source = sc.nextInt();

bfs_graph bfs = new bfs_graph();

bfs.bfs_traversal(g, source, total_vertices+1);

}

}

topological sorting in java

 package javaCodes;

import java.util.ArrayList;

import java.util.Iterator;

import java.util.Stack;

class graph

{

private int vertices;

private ArrayList<ArrayList<Integer> > abj;

public graph(int v)

{

this.vertices = v;

abj = new ArrayList<ArrayList<Integer> > (v);

for(int i=0; i<v; i++)

{

abj.add(new ArrayList<Integer> ());

}

}

void addedge(int u, int vertex)

{

abj.get(u).add(vertex);

}

void topologicalSort()

{

Stack<Integer> stack = new Stack<Integer> ();

boolean visited[] = new boolean[vertices];

for(int i=0; i<vertices; i++)

{

visited[i] = false;

}

for(int i=0; i<vertices; i++)

{

if(visited[i] != true)

{

topologicalSortUtil(i, visited, stack);

}

}

while(stack.empty() == false)

{

System.out.print(stack.pop() + "    " );

}

}

void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {

visited[v] = true;

Iterator<Integer> ite = abj.get(v).iterator();

while(ite.hasNext())

{

int temp = ite.next();

if(!visited[temp])

{

topologicalSortUtil(temp, visited, stack);

}

}

stack.push(new Integer(v));

}

}

public class topological_sorting {

public static void main(String args[])

{

graph g = new graph(6);

g.addedge(5, 2);

g.addedge(5, 0);

g.addedge(4, 0);

g.addedge(4, 1);

g.addedge(2, 3);

g.addedge(3, 1);

System.out.print("topological sorting sequence is : ");

g.topologicalSort();

}

}

Floyd–Warshall algorithm in java

 package javaCodes;

class allPairShortest{

void shortest_path(int g[][])

{

for(int i=0; i<4; i++)

{

for(int j=0; j<4; j++)

{

System.out.print(g[i][j]+"   ");

}

System.out.println("\n");

}

System.out.println("\n");

int dis[][] = new int[4][4];

for(int i=0; i<4; i++)

{

for(int j=0; j<4; j++)

{

dis[i][j] = g[i][j];

}

}

for(int i=0; i<4; i++)

{

for(int j=0; j<4; j++)

{

System.out.print(dis[i][j]+"   ");

}

System.out.println("\n");

}

System.out.println("\n");

for(int k=0; k<4; k++)

{

for(int i=0; i<4; i++)

{

for(int j=0; j<4; j++)

{

if(dis[i][j] > dis[i][k]+dis[k][j])

{

dis[i][j] = dis[i][k]+dis[k][j];

System.out.print(dis[i][j]);

}

}

}

}

for(int i=0; i<4; i++)

{

for(int j=0; j<4; j++)

{

System.out.print(dis[i][j]+"   ");

}

System.out.println("\n");

}

}

}

public class floyd_warshal {

private static final int INF = 99999;

public static void main(String args[])

{

allPairShortest path = new allPairShortest();

int graph1[][] = { {0,   5,  INF, 10},

                {INF, 0,   3, INF},

                {INF, INF, 0,   1},

                {INF, INF, INF, 0}

              };

path.shortest_path(graph1);

}

}

Matrix Multiplication in java

 package javaCodes;

import java.util.Scanner;

public class matrix_multiplication {

public static int[][] multiplication(int arr[][], int arr1[][], int size)

{

int[][] array = new int[3][3];

for(int i=0; i<size; i++)

{

for(int j=0; j<size; j++)

{

for(int k=0; k<size; k++)

{

array[i][j] += arr[i][k]*arr1[k][j];

}

}

}

return array;

}

public static void main(String args[])

{

int[][] arr = new int[3][3];

int[][] arr1 = new int[3][3];

int[][] arr2 = new int[3][3];

Scanner sc = new Scanner(System.in);

for(int i=0; i<3; i++)

{

for(int j=0; j<3; j++)

{

arr[i][j] = sc.nextInt();

arr1[i][j] = sc.nextInt();

}

}

arr2 = multiplication(arr, arr1, 3);

for(int i=0; i<3; i++)

{

for(int j=0; j<3; j++)

{

System.out.print(arr2[i][j]+"    ");

}

System.out.println("\n");

}

}

}

Dijkstra implementation in java

 package javaCodes;

import java.util.ArrayList;

import java.util.Scanner;

class dijkstra

{

private int vertices = 9;

void shortest_path(int g[][], int source)

{

int dis[] = new int[vertices];

boolean sptset[] = new boolean[vertices];

ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>> (vertices);

for(int i=0; i < vertices; i++)

{

dis[i] = Integer.MAX_VALUE;

sptset[i] = false;

path.add(new ArrayList<Integer> ());

}

dis[source] = 0;

for(int v=0; v<vertices; v++)

{

int u = mindistance(dis, sptset);

sptset[u] = true;

for(int i=0; i<vertices; i++)

{

if(!sptset[i] && dis[u]!= Integer.MAX_VALUE && g[u][i]!=0 && dis[u] + g[u][i] < dis[i])

{

if(dis[i] == Integer.MAX_VALUE)

{

dis[i] = dis[u] + g[u][i];

for(int k=0; k < path.get(u).size(); k++)

{

path.get(i).add(path.get(u).get(k));

}

path.get(i).add(u);

}

else

{

dis[i] = dis[u] + g[u][i];

path.get(i).clear();

for(int k=0; k < path.get(u).size(); k++)

{

path.get(i).add(path.get(u).get(k));

}

path.get(i).add(u);

}

}

}

}

display(dis, path);

}

int mindistance(int[] dis, boolean[] sptset) {

int min = Integer.MAX_VALUE, min_index = -1;

for(int i=0; i<vertices; i++)

{

if(!sptset[i] && dis[i] < min)

{

min = dis[i];

min_index = i;

}

}

return min_index;

}

void display(int[] dis, ArrayList<ArrayList<Integer>> path) {

System.out.println("Distance of every node from source is : ");

for(int i=0; i < vertices; i++)

{

System.out.println("Node : "+ i +"   "+"Distance : "+dis[i]+"   ");

System.out.print("Shortest distance path is : ");

for(int j=0; j<path.get(i).size(); j++)

{

System.out.print(path.get(i).get(j)+"   ");

}

System.out.println("\n");

}

}

}

public class Dijkstra_algorithm {

public static void main(String args[])

{

int arr[][] = new int[9][9];

for(int i=0; i<=8; i++)

{

for(int j=0; j<=8; j++)

{

arr[i][j] = 0;

}

}

int edges;

Scanner sc = new Scanner(System.in);

System.out.print("Enter no of edges : ");

edges = sc.nextInt();

for(int i=0; i<edges; i++)

{

System.out.print("Now Enter left, right vertex and edge weight: ");

int temp1, temp2, temp3;

temp1 = sc.nextInt();

temp2 = sc.nextInt();

temp3 = sc.nextInt();

arr[temp1][temp2] = temp3;

arr[temp2][temp1] = temp3;

}

dijkstra obj = new dijkstra();

obj.shortest_path(arr, 0);

}

}

Binary search implementation in Java

package javaCodes;

import java.util.Scanner;

public class binary_search_updated {

public static int binary( int arr[], int low, int high, int key)

{

if(low > high)

return -1;

int mid = (low+high)/2;

if(arr[mid] == key)

{

return 1;

}

else if(arr[mid] > key)

{

return binary(arr, low, mid, key);

}

else if(arr[mid] < key)

{

return binary(arr, mid+1, high, key);

}

return key;

}

public static void main(String args[])

{

int[] arr = new int[100];

int key, low=0, n;

System.out.println("enter how many numbers : ");

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

System.out.println("now enter numbers : ");

for(int i=0; i<n; i++)

{

arr[i] = sc.nextInt();

}

System.out.println("now enter search key : ");

key = sc.nextInt();

int number = binary(arr, low, n-1, key);

if(number==1)

{

System.out.println("Found");

}

else

{

System.out.println("not found");

}

}

}

BITAC_AME_Written (29.01.2021 - BUET)

Question: you have two files containing the marks of the written and practical exam of some students. Currently, The marks are in 100 but the final weight for the written  part is 60 and for the practical part 40. you need to combine the marks and rank them based on the total marks. see the sample I/O for clarification.

Written.txt	Practical.txt
4	4
1505003     41	1505004      72
1505001     59	1505001      80
1505002      65	1505003      56
1505004      84	1505002      78

Rank.txt

Rank           ID               Marks

1           1505004          79.2

2           1505002          70.2

3           1505001          67.4

4           1505003          47.0

                                    

 

Solution: 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    ifstream input_written, input_practical;

    int roll_written1[100], mark_written1[100], roll_practical1[100], mark_practical1[100];

    int i=0, j=0;

    double final_marks[100];

    input_written.open("written.txt.txt");

    input_practical.open("practical.txt.txt");

    while(!input_written.eof())

    {

        int number=0, number1=0;

        input_written>>number;

        input_practical>>number1;

        for(int z=0; z<number; z++)

        {

            int roll, mark, roll_practical, mark_practical;

            input_written>>roll>>mark;

            input_practical>>roll_practical>>mark_practical;

            roll_written1[i] = roll;

            mark_written1[i] = mark;

            roll_practical1[j] = roll_practical;

            mark_practical1[j] = mark_practical;

            i++;

            j++;

        }

    }

    ofstream output;

    output.open("rank.txt");

    output<<"Rank"<<"       "<<"ID"<<"       "<<"Marks"<<"\n";

    for(int k = 0; k<i; k++)

    {

        for(int l=0; l<i; l++)

        {

            if(roll_practical1[l] == roll_written1[k])

            {

                final_marks[k] = ( ((double)mark_written1[k]*60)/100 ) + ( ((double)mark_practical1[l]*40)/100 );

            }

        }

    }

    for(int n=0; n<i-1; n++)

    {

        for(int o=n+1; o<i; o++)

        {

            if(final_marks[n] < final_marks[o])

            {

                swap(final_marks[n], final_marks[o]);

                swap(roll_written1[n], roll_written1[o]);

            }

        }

    }

    for(int p = 0; p<i; p++)

    {

        output<<" "<<p+1<<"       "<<roll_written1[p]<<"       "<<final_marks[p]<<endl;

        cout<<" "<<p+1<<"       "<<roll_written1[p]<<"       "<<final_marks[p]<<endl;

    }

    output.close();

    input_written.close();

    input_practical.close();

}