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();

}

All About Database Normalization

Ø Database Normalization

Database normalization is actually a schema design technique which helps to eliminate redundant data and reduce dependencies among the attributes of a schema. It’s a systematic approach of splitting or decomposing tables to avoid undesirable characteristics like insertion, deletion and updating anomalies in the database. Database normalization is a multi-step process to divide larger tables into smaller views to eliminate repetitive data and store data more logically and effectively. Therefore, the motive intention of database normalization is to organize data into the database more logically so that it can be extracted, inserted and updated with minimal intervention.  Since current world is driven by data and so efficiency as well as effectiveness of a real world application mostly depends on how data can be accessed, inserted, deleted and updated.

Ø Why do we need normalization?

This topic can be quite confusing for the beginners and sometimes for the experienced programmers as well. However, overall gist indication on why database normalization is essential can be summarized as follows:

⇒For eliminating duplicate data and data anomalies.

⇒For avoiding unwanted data connections and dependencies.

⇒For optimization of database storage as well as application efficiency.

⇒For reducing the delay and complexity of accessing database.

⇒For making database more natural and logical.

⇒For better facilitate data interpretation and database access to the applications as well as to the end users.

For better visualization and understa, let’s think of a real world example. Suppose, we have a table which describes employees of a well-known software company.

EmployeeId	Name	Department	Team Lead	Phone No (Team Lead)
1231	Arafat Ullah	Software	Tajul Islam	32998656
1232	Mike Hike	Software	Tajul Islam	32998656
1233	Golam Sarowar	Software	Tajul Islam	32998656
1234	Mehedi Hasan	Software	Tajul Islam	32998656

In the above table, we have data of employees of a software company, their id, name, team lead and phone no of team lead. This table is not normalized so what we can see that duplicate value is present there which is referred as redundant data. This redundant data not only consumes extra memory space in the database but also make it difficult to update, delete and insert new entries. Moreover, this insertion, deletion and update anomalies are doubled when the database is not normalized enough. Let’s dive in depth to understand those anomalies for not normalizing data.

 😢   Insertion Anomaly

Now suppose this month 20 more employees have been recruited in software engineering department. So what you have to do now is to insert those new engineers in the above table which leads repetitive insertion of department name, team lead name and team lead’s phone no. This is insertion anomaly which increases data redundancy in one sense.

       😢  Deletion anomaly

From the above mentioned table it is also noticeable that two different information are mentioned there. First one is about employee and another information is about department name and team lead name along with team lead’s phone number. Now, suppose you want to delete only employee information. Oh god!! What will happen? Department information along with department head will be deleted from the table and we will lost those information. This is referred as deletion anomaly.

         😢 Update Anomaly

Now, suppose Mr. Tajul islam who was head of the software engineering department leaves the department for some unavoidable reasons which makes some people smile and of course some employee cry. Now, a new team lead has been recruited and you have to update the name of the team lead and his phone number as well. There, just imagine, you have to update the same information again and again in each and every rows. This is devastating right?  This scenario is regarded as update anomaly.

So, I think above discussion will surely make you realize why database normalization is essential for most of the database system to operate efficiently and effectively.

 

To Be Continued – stay tuned