SYLHET INTERNATIONAL UNIVERSITY

SHAMIMABAD, BAGBARI, SYLHET

Topics: Algorithm Final Lab Assignment

Course Title: Algorithm Lab
Course Code: CSE 208

Submitted to:

Name: Mr. Rajarshi Roy Chowdhury

Department: CSE

Submitted by:
Name: Ashraful Goni
Roll: 36004
Level: 2-2
Department: CSE
Date: 03-Nov-2022
 Answer to Question number 1:

(a) Bubble Sort:

public class BubbleSort {

public static void bubbleSort(int[] ara, int size){

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

for (int j = 0; j < size - i - 1; j++){

if(ara[j] > ara[j+1]){

int temp = ara[j];

ara[j] = ara[j+1];

ara[j+1] = temp;

public static void printArray(int[] ara){

for (int i: ara){

[Link](i+ " ");

 }

[Link]();

public static void main(String[] args) {

int[] ara = {120, 12, 18, 201, 291, 0, 1, 23, 11, 2};

printArray(ara);

bubbleSort(ara, [Link]);

printArray(ara);

(b) Quick Sort:

public class QuickSort {

static void swap(int[] arr, int i, int j)

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;
}

static int partition(int[] arr, int low, int high)

int pivot = arr[high];

int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {

i++;

swap(arr, i, j);

}
 swap(arr, i + 1, high);

return (i + 1);

static void quickSort(int[] arr, int low, int high)

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

public static void printArray(int[] ara){

 for (int i: ara){

[Link](i+ " ");

[Link]();

public static void main(String[] args) {

int[] ara = {120, 12, 18, 201, 291, 0, 1, 23, 11, 2};

printArray(ara);

quickSort(ara, 0,[Link]-1);

printArray(ara);

(C) Merge Sort:

public class MergeSort {

public static void merge(int arr[], int l, int m, int r)

int n1 = m - l + 1;

int n2 = r - m;

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[m + 1 + j];

int i = 0, j = 0;

int 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++;

public static void mergeSort(int arr[], int l, int r)

if (l < r) {

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

public static void printArray(int[] ara){

 for (int i: ara){

[Link](i+ " ");

[Link]();

public static void main(String[] args) {

int[] ara = {120, 12, 18, 201, 291, 0, 1, 23, 11, 2};

printArray(ara);

mergeSort(ara, 0,[Link]-1);

printArray(ara);

Answer to Question number 2:

(a) Applications of using Stack and Queue

Stack:
Application of Stack Data Structure (Geeksforgeeks,
Applications, Advantages and Disadvantages of Stack, 2022):

• Stack is used for evaluating expressions with operands and

operations.
• Matching tags in HTML and XML
• Undo function in any text editor.
• Infix to Postfix conversion.
• Stacks are used for backtracking and parenthesis matching.
• Stacks are used for the conversion of one arithmetic notation
to another arithmetic notation.
• Stacks are useful for function calls, storing the activation
records, and deleting them after returning from the function.
It is very useful in processing function calls.
• Stacks help in reversing any set of data or strings.

Queue:

Applications of Queue Data Structure (Geeksforgeeks,

Applications, Advantages and Disadvantages of Queue, 2022):

• Multi programming: Multiprogramming means when

multiple programs are running in the main memory. It is
essential to organize these multiple programs and these
multiple programs are organized as queues.
 • Network: In a network, a queue is used in devices such as a
router or a switch. another application of a queue is a mail
queue which is a directory that stores data and controls files
for mail messages.
• Job Scheduling: The computer has a task to execute a
particular number of jobs that are scheduled to be executed
one after another. These jobs are assigned to the processor
one by one which is organized using a queue.
• Shared resources: Queues are used as waiting lists for a
single shared resource.

(b)Implementation of Stack & Queue(Using Array):

Stack:

public class Stack {

static final int MAX = 1000;

public int top;

int a[] = new int[MAX]; // Maximum size of Stack

public boolean isEmpty()

return (top < 0);

Stack()

top = -1;

public boolean push(int x)

if (top >= (MAX - 1)) {

[Link]("Stack Overflow");

return false;

}
 else {

a[++top] = x;

[Link](x + " pushed into stack");

return true;

public int pop()

if (top < 0) {

[Link]("Stack Underflow");

return 0;

else {

int x = a[top--];

return x;
 }

public int peek()

if (top < 0) {

[Link]("Stack Underflow");

return 0;

else {

int x = a[top];

return x;

public void print(){

 for(int i = top;i>-1;i--){

[Link](" "+ a[i]);

public static void main(String[] args) {

Stack s = new Stack();

[Link](10);

[Link](20);

[Link](30);

[Link]([Link]() + " Popped from stack");

[Link]("Top element is :" + [Link]());

[Link]("Elements present in stack :");

[Link]();

}
Queue:

public class Queue {

static private int front, rear, capacity;

static private int queue[];

Queue(int c)

front = rear = 0;

capacity = c;

queue = new int[capacity];

static void queueEnqueue(int data)

if (capacity == rear) {

[Link]("\nQueue is full\n");
 return;

else {

queue[rear] = data;

rear++;

return;

static void queueDequeue()

if (front == rear) {

[Link]("\nQueue is empty\n");

return;

}
 else {

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

queue[i] = queue[i + 1];

if (rear < capacity)

queue[rear] = 0;

rear--;

return;

static void queueDisplay()

{
 int i;

if (front == rear) {

[Link]("\nQueue is Empty\n");

return;

for (i = front; i < rear; i++) {

[Link](" %d <-- ", queue[i]);

return;

static void queueFront()

if (front == rear) {

[Link]("\nQueue is Empty\n");
 return;

[Link]("\nFront Element is: %d",

queue[front]);

return;

public static void main(String[] args) {

Queue q = new Queue(4);

[Link]();

[Link](20);

[Link](30);

[Link](40);

[Link](50);
 [Link]();

[Link](60);

[Link]();

[Link]();

[Link]();

[Link](

"\n\nafter two node deletion\n\n");

[Link]();

[Link]();

}
}

Answer to Question number 3:

(a) Application of Tree data structure (Programiz, 2022):

• Binary Search Trees(BSTs) are used to quickly check

whether an element is present in a set or not.
• Heap is a kind of tree that is used for heap sort.
• A modified version of a tree called Tries is used in modern
routers to store routing information.
• Most popular databases use B-Trees and T-Trees, which are
variants of the tree structure we learned above to store their
data
• Compilers use a syntax tree to validate the syntax of every
program you write

(b) Implementation of BST(Including insert, delete &

Search):

public class BST {

class Node {

int key;

Node left, right;

public Node(int item) {

key = item;

left = right = null;

Node insertKey(Node root, int key) {

if (root == null) {

root = new Node(key);

return root;

if (key < [Link])

 [Link] = insertKey([Link], key);

else if (key > [Link])

[Link] = insertKey([Link], key);

return root;

Node deleteRec(Node root, int key) {

if (root == null)

return root;

if (key < [Link])

[Link] = deleteRec([Link], key);

else if (key > [Link])

[Link] = deleteRec([Link], key);

else {

if ([Link] == null)

return [Link];
 else if ([Link] == null)

return [Link];

[Link] = minValue([Link]);

[Link] = deleteRec([Link], [Link]);

return root;

int minValue(Node root) {

int minv = [Link];

while ([Link] != null) {

minv = [Link];

root = [Link];

return minv;
}

Node search(Node root, int key){

if(root == null || [Link] == key){

return root;

if([Link] > key){

return search([Link], key);

return search([Link], key);

void inorderRec(Node root) {

if (root != null) {

inorderRec([Link]);

[Link]([Link] + " -> ");

inorderRec([Link]);

}
}

public static void main(String[] args) {

Node root = null;

BST bst = new BST();

root = [Link](root, 8);

root = [Link](root, 3);

root = [Link](root, 1);

root = [Link](root, 6);

root = [Link](root, 7);

root = [Link](root, 10);

root = [Link](root, 14);

root = [Link](root, 4);

[Link]("Inorder traversal: ");

[Link](root);

[Link]();
 [Link]("\n\nAfter deleting 10");

[Link](root,10);

[Link]("Inorder traversal: ");

[Link](root);

[Link]();

Node searhItm = [Link](root, 70);

if(searhItm != null){

[Link]("Item is found");

else {

[Link]("Item is not found");

Answer to Question number 4:

(a) Application of Graph Data Structure
(Geeksforgeeks, Applications of Graph Data Structure,
2022):

• In Computer science graphs are used to represent the flow

of computation.
• Google maps uses graphs for building transportation
systems, where intersection of two(or more) roads are
considered to be a vertex and the road connecting two
vertices is considered to be an edge, thus their navigation
system is based on the algorithm to calculate the shortest
path between two vertices.
• In Facebook, users are considered to be the vertices and if
they are friends then there is an edge running between
them. Facebook’s Friend suggestion algorithm uses graph
theory. Facebook is an example of undirected graph.
• In World Wide Web, web pages are considered to be the
vertices. There is an edge from a page u to other page v if
there is a link of page v on page u. This is an example of
Directed graph. It was the basic idea behind Google Page
Ranking Algorithm.
• In Operating System, we come across the Resource
Allocation Graph where each process and resources are
 considered to be vertices. Edges are drawn from resources
to the allocated process, or from requesting process to the
requested resource. If this leads to any formation of a cycle
then a deadlock will occur.
• In mapping system we use graph. It is useful to find out
which is an excellent place from the location as well as your
nearby location. In GPS we also use graphs.
• Facebook uses graphs. Using graphs suggests mutual
friends. it shows a list of the f following pages, friends, and
contact list.
• Microsoft Excel uses DAG means Directed Acyclic Graphs.
• In the Dijkstra algorithm, we use a graph. we find the
smallest path between two or many nodes.
• On social media sites, we use graphs to track the data of
the users. liked showing preferred post suggestions,
recommendations, etc.

(b) Key difference between Tree and Graph Data

Structure (Geeksforgeeks, Difference between graph and
tree, 2022):
 The basis of Tree Graph
comparison

Definition Tree is a non-linear Graph is a non-linear

data structure. data structure.

Structure It is a collection of Each node can have

nodes and edges. any number of
edges.
Edges If there is n nodes Each node can have
then there would be any number of
n-1 number of edges edges.
Types of Edges They are always They can be directed
directed or undirected.

Root node There is a unique There is no unique

node called node called root in
root(parent) node in graph.
trees.
Loop Formation There will not be any A cycle can be
cycle. formed.
Traversal We traverse a tree For graph traversal,
using in-order, pre- we use Breadth-First
order, or post-order Search (BFS), and
traversal methods. Depth-First Search
(DFS).

(c)Implement a Graph data structure(including

Dijkstra, Prims and Kruskal algorithms):

(i) Graph Implementation:

public class Graph {

class Edge {

int src, dest;

int vertices, edges;

Edge[] edge;
Graph(int vertices, int edges) {

[Link] = vertices;

[Link] = edges;

edge = new Edge[edges];

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

edge[i] = new Edge();

public static void main(String[] args) {

int noVertices = 5;

int noEdges = 8;

Graph g = new Graph(noVertices, noEdges);

[Link][0].src = 1;

[Link][0].dest = 2;

[Link][1].src = 1;

[Link][1].dest = 3;

[Link][2].src = 1;

[Link][2].dest = 4;

[Link][3].src = 2;

[Link][3].dest = 4;

[Link][4].src = 2;

[Link][4].dest = 5;

[Link][5].src = 3;

[Link][5].dest = 4;
 [Link][6].src = 3;

[Link][6].dest = 5;

[Link][7].src = 4;

[Link][7].dest = 5;

// print graph

for (int i = 0; i < noEdges; i++) {

[Link]([Link][i].src + " - " + [Link][i].dest);

(ii) Dijkstra Algorithm Implementation:

import [Link].*;

public class Dijkstra {

private int dist[];

private Set<Integer> settled;

private PriorityQueue<Node> pq;

private int V;

List<List<Node> > adj;

public Dijkstra(int V)

this.V = V;

dist = new int[V];

settled = new HashSet<Integer>();

pq = new PriorityQueue<Node>(V, new Node());

public void dijkstra(List<List<Node> > adj, int src)

{

[Link] = adj;

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

dist[i] = Integer.MAX_VALUE;

[Link](new Node(src, 0));

dist[src] = 0;

while ([Link]() != V) {

if ([Link]())

return;

int u = [Link]().node;
 if ([Link](u))

continue;

[Link](u);

e_Neighbours(u);

private void e_Neighbours(int u)

int edgeDistance = -1;

int newDistance = -1;

for (int i = 0; i < [Link](u).size(); i++) {

Node v = [Link](u).get(i);
 if () {

edgeDistance = [Link];

newDistance = dist[u] + edgeDistance;

if (newDistance < dist[[Link]])

dist[[Link]] = newDistance;

[Link](new Node([Link], dist[[Link]]));

public static void main(String arg[])

int V = 5;

int source = 0;
List<List<Node> > adj

= new ArrayList<List<Node> >();

for (int i = 0; i < V; i++) {

List<Node> item = new ArrayList<Node>();

[Link](item);

[Link](0).add(new Node(1, 9));

[Link](0).add(new Node(2, 6));

[Link](0).add(new Node(3, 5));

[Link](0).add(new Node(4, 3));

[Link](2).add(new Node(1, 2));

[Link](2).add(new Node(3, 4));

Dijkstra dpq = new Dijkstra(V);

 [Link](adj, source);

[Link]("The shorted path from node :");

for (int i = 0; i < [Link]; i++)

[Link](source + " to " + i + " is "

+ [Link][i]);

class Node implements Comparator<Node> {

public int node;

public int cost;

public Node() {}

public Node(int node, int cost)

 {

[Link] = node;

[Link] = cost;

@Override public int compare(Node node1, Node node2)

if ([Link] < [Link])

return -1;

if ([Link] > [Link])

return 1;

return 0;

}
(iii) Prim’s Algorithm Implementation:

public class Prims {

private static final int V = 5;

int minKey(int key[], Boolean mstSet[])

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

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

if (mstSet[v] == false && key[v] < min) {

min = key[v];

min_index = v;

return min_index;

void printMST(int parent[], int graph[][])

{

[Link]("Edge \tWeight");

for (int i = 1; i < V; i++)

[Link](parent[i] + " - " + i + "\t"

+ graph[i][parent[i]]);

void primMST(int graph[][])

int parent[] = new int[V];

int key[] = new int[V];

Boolean mstSet[] = new Boolean[V];

for (int i = 0; i < V; i++) {

key[i] = Integer.MAX_VALUE;

mstSet[i] = false;
}

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++) {

int u = minKey(key, mstSet);

mstSet[u] = true;

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

if (graph[u][v] != 0 && mstSet[v] == false

&& graph[u][v] < key[v]) {

parent[v] = u;

key[v] = graph[u][v];

}
 printMST(parent, graph);

public static void main(String[] args)

Prims p = new Prims();

int graph[][] = new int[][] { { 0, 2, 0, 6, 0 },

{ 2, 0, 3, 8, 5 },

{ 0, 3, 0, 0, 7 },

{ 6, 8, 0, 0, 9 },

{ 0, 5, 7, 9, 0 } };

[Link](graph);

(iv) Kruskal Algorithm Implementation:

import [Link].*;

public class Kruskal {

class Edge implements Comparable<Edge> {

int src, dest, weight;

public int compareTo(Edge compareEdge)

return [Link] - [Link];

};

class subset {

int parent, rank;

};

int V, E;

Edge edge[];
Kruskal(int v, int e)

V = v;

E = e;

edge = new Edge[E];

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

edge[i] = new Edge();

int find(subset subsets[], int i)

if (subsets[i].parent != i)

subsets[i].parent

= find(subsets, subsets[i].parent);

return subsets[i].parent;

}
void Union(subset subsets[], int x, int y)

int xroot = find(subsets, x);

int yroot = find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

else {

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

void KruskalMST()

{
Edge result[] = new Edge[V];

int e = 0;

int i = 0;

for (i = 0; i < V; ++i)

result[i] = new Edge();

[Link](edge);

subset subsets[] = new subset[V];

for (i = 0; i < V; ++i)

subsets[i] = new subset();

for (int v = 0; v < V; ++v) {

subsets[v].parent = v;

subsets[v].rank = 0;

}
i = 0;

while (e < V - 1) {

Edge next_edge = edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

if (x != y) {

result[e++] = next_edge;

Union(subsets, x, y);

[Link]("Following are the edges in "

+ "the constructed MST");

int minimumCost = 0;
 for (i = 0; i < e; ++i) {

[Link](result[i].src + " -- "

+ result[i].dest

+ " == " + result[i].weight);

minimumCost += result[i].weight;

[Link]("Minimum Cost Spanning Tree "

+ minimumCost);

public static void main(String[] args)

int V = 4;

int E = 5;

Kruskal graph = new Kruskal(V, E);

[Link][0].src = 0;
[Link][0].dest = 1;

[Link][0].weight = 10;

[Link][1].src = 0;

[Link][1].dest = 2;

[Link][1].weight = 6;

[Link][2].src = 0;

[Link][2].dest = 3;

[Link][2].weight = 5;

[Link][3].src = 1;

[Link][3].dest = 3;

[Link][3].weight = 15;

[Link][4].src = 2;

[Link][4].dest = 3;

[Link][4].weight = 4;
 [Link]();

END