PRACTICAL FILE OF LAB-II: ADVANCED ALGORITHM

(MTCS152)
(2025- 2026)
[Link]. Name of Experiment Page No.
Write a Java program to implement all the functions of a dictionary (ADT)
1 using hashing.
3
Write a Java program to implement Dijkstra’s algorithm for Single source
2 shortest path problem.
7
Write Java programs that use recursive and non-recursive functions to traverse the
3 13
given binary tree in (a) Pre order ( b) In order (c) Post order .
Write Java programs for the implementation of bfs and dfs for a given graph.
4 16
Write a Java program to perform the following operations: a) Insertion into a B-tree b)
5 Searching in a B-tree 18
1. Write a Java program to implement all the functions of a dictionary (ADT) using hashing.

import [Link];

import [Link];

class Dictionary {

private int size;

private LinkedList<Entry>[] table;

// Entry class to store key-value pair

class Entry {

String key;

String value;

Entry(String key, String value) {

[Link] = key;

[Link] = value;

// Constructor

Dictionary(int size) {

[Link] = size;

table = new LinkedList[size];

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

table[i] = new LinkedList<>();

// Hash Function

private int hash(String key) {

return [Link]([Link]()) % size;

// Insert Key-Value pair

public void insert(String key, String value) {

for (Entry e : table[index]) {

if ([Link](key)) {

[Link] = value;

[Link]("Key already exists. Value updated.");

return;

table[index].add(new Entry(key, value));

[Link]("Inserted Successfully.");

// Search Key

public String search(String key) {

int index = hash(key);

for (Entry e : table[index]) {

if ([Link](key))

return [Link];

return null;

// Delete Key

public boolean delete(String key) {

int index = hash(key);

for (Entry e : table[index]) {

if ([Link](key)) {

table[index].remove(e);

return true;

}
 return false;

// Display Dictionary

public void display() {

[Link]("\nDictionary Contents:");

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

[Link]("Bucket " + i + ": ");

for (Entry e : table[i])

[Link]("[" + [Link] + " : " + [Link] + "] ");

[Link]();

// Main Class

public class DictionaryHashingDemo {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

Dictionary dict = new Dictionary(10);

int choice;

String key, value;

do {

[Link]("\n--- Dictionary using Hashing ---");

[Link]("1. Insert");

[Link]("2. Search");

[Link]("3. Delete");

[Link]("4. Display");

[Link]("5. Exit");

[Link]("Enter choice: ");

choice = [Link]();

[Link]();
switch (choice) {

case 1:

[Link]("Enter Key: ");

key = [Link]();

[Link]("Enter Value: ");

value = [Link]();

[Link](key, value);

break;

case 2:

[Link]("Enter Key to Search: ");

key = [Link]();

value = [Link](key);

if (value == null)

[Link]("Key not found!");

else

[Link]("Value = " + value);

break;

case 3:

[Link]("Enter Key to Delete: ");

key = [Link]();

if ([Link](key))

[Link]("Deleted Successfully.");

else

[Link]("Key not found!");

break;

case 4:

[Link]();

break;

case 5:

[Link]("Exiting...");

break;
 default:

[Link]("Invalid Choice!");

} while (choice != 5);

[Link]();

2. Write a Java program to implement Dijkstra’s algorithm for Single source shortest path problem

import [Link].*;

public class DijkstraAlgorithm {

static final int INF = Integer.MAX_VALUE;

public static void dijkstra(int graph[][], int source) {

int n = [Link];

int dist[] = new int[n]; // Shortest distance array

boolean visited[] = new boolean[n]; // Visited vertices

// Initialize distances

[Link](dist, INF);

dist[source] = 0;

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

int u = minDistance(dist, visited);

visited[u] = true;
 // Update distances

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

if (!visited[v] && graph[u][v] != 0 &&

dist[u] != INF &&

dist[u] + graph[u][v] < dist[v]) {

dist[v] = dist[u] + graph[u][v];

printSolution(dist, source);

// Function to get minimum distance vertex

private static int minDistance(int dist[], boolean visited[]) {

int min = INF, minIndex = -1;

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

if (!visited[v] && dist[v] <= min) {

min = dist[v];

minIndex = v;

return minIndex;

// Print Result

private static void printSolution(int dist[], int src) {

[Link]("\nShortest distances from Source Vertex " + src + ":");

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

[Link]("Vertex " + i + " -> Distance = " + dist[i]);

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter number of vertices: ");

int n = [Link]();

int graph[][] = new int[n][n];

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

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

graph[i][j] = [Link]();

[Link]("Enter source vertex: ");

int source = [Link]();

dijkstra(graph, source);

[Link]();

3 Write Java programs that use recursive and non-recursive functions to traverse the given
binary tree in a) Pre order b) In order c) Post order.
// Binary Tree Traversal - Recursive & Non Recursive

import [Link];

class Node {

int data;

Node left, right;

Node(int data) {

[Link] = data;

left = right = null;

public class BinaryTreeTraversal {

Node root;

// ---------------- Recursive Traversals ----------------

void preorderRecursive(Node node) {

if (node == null) return;

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

preorderRecursive([Link]);
 preorderRecursive([Link]);

void inorderRecursive(Node node) {

if (node == null) return;

inorderRecursive([Link]);

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

inorderRecursive([Link]);

void postorderRecursive(Node node) {

if (node == null) return;

postorderRecursive([Link]);

postorderRecursive([Link]);

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

// ---------------- Non-Recursive Traversals ----------------

// Preorder Iterative

void preorderIterative(Node node) {

if (node == null) return;

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

[Link](node);

while (![Link]()) {

Node curr = [Link]();

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

if ([Link] != null) [Link]([Link]);

if ([Link] != null) [Link]([Link]);

}
// Inorder Iterative

void inorderIterative(Node node) {

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

Node curr = node;

while (curr != null || ![Link]()) {

while (curr != null) {

[Link](curr);

curr = [Link];

curr = [Link]();

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

curr = [Link];

// Postorder Iterative (Using Two Stacks)

void postorderIterative(Node node) {

if (node == null) return;

Stack<Node> s1 = new Stack<>();

Stack<Node> s2 = new Stack<>();

[Link](node);

while (![Link]()) {

Node temp = [Link]();

[Link](temp);

if ([Link] != null) [Link]([Link]);

if ([Link] != null) [Link]([Link]);

while (![Link]())

[Link]([Link]().data + " ");

// ---------------- Main ----------------

public static void main(String[] args) {

BinaryTreeTraversal tree = new BinaryTreeTraversal();

/* Creating Binary Tree

/ \

2 3

/\ /\

4 5 6 7

*/

[Link] = new Node(1);

[Link] = new Node(2);

[Link] = new Node(3);

[Link] = new Node(4);

[Link] = new Node(5);

[Link] = new Node(6);

[Link] = new Node(7);

[Link]("Recursive Traversals:");

[Link]("Preorder : ");

[Link]([Link]);

[Link]("\nInorder : ");

[Link]([Link]);

[Link]("\nPostorder: ");

[Link]([Link]);

[Link]("\n\nNon-Recursive Traversals:");

[Link]("Preorder : ");

[Link]([Link]);

[Link]("\nInorder : ");
 [Link]([Link]);

[Link]("\nPostorder: ");

[Link]([Link]);

4. Write Java programs for the implementation of bfs and dfs for a given graph.

import [Link].*;

public class GraphTraversal {

private int vertices;

private LinkedList<Integer> adj[];

// Constructor

GraphTraversal(int v) {

vertices = v;

adj = new LinkedList[v];

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

adj[i] = new LinkedList<>();

// Add Edge

void addEdge(int src, int dest) {

adj[src].add(dest);

adj[dest].add(src); // remove this line for directed graph

// ---------- BFS ----------

void BFS(int start) {

boolean visited[] = new boolean[vertices];

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

[Link](start);

[Link]("BFS Traversal: ");

while (![Link]()) {

int node = [Link]();

[Link](node + " ");

for (int n : adj[node]) {

if (!visited[n]) {

visited[n] = true;

[Link](n);

[Link]();

// ---------- DFS ----------

void DFS(int start) {

boolean visited[] = new boolean[vertices];

[Link]("DFS Traversal: ");

dfsUtil(start, visited);

[Link]();

void dfsUtil(int node, boolean visited[]) {

visited[node] = true;

[Link](node + " ");

for (int n : adj[node]) {

if (!visited[n])

dfsUtil(n, visited);

}
 }

// ---------- Main ----------

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter number of vertices: ");

int v = [Link]();

GraphTraversal g = new GraphTraversal(v);

[Link]("Enter number of edges: ");

int e = [Link]();

[Link]("Enter edges (u v):");

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

int src = [Link]();

int dest = [Link]();

[Link](src, dest);

[Link]("Enter starting vertex: ");

int start = [Link]();

[Link](start);

[Link](start);

[Link]();

}
5. Write a Java program to perform the following operations: a) Insertion into a B-tree b) Searching in a
B-tree .

import [Link];

class BTreeNode {

int keys[];

int t; // Minimum degree

BTreeNode child[];

int n; // Current number of keys

boolean leaf; // Is true when node is leaf

BTreeNode(int t, boolean leaf) {

this.t = t;

[Link] = leaf;

keys = new int[2 * t - 1];

child = new BTreeNode[2 * t];

n = 0;

// Search key in subtree rooted with this node

BTreeNode search(int key) {

int i = 0;

while (i < n && key > keys[i])

i++;

if (i < n && keys[i] == key)

return this;

if (leaf)

return null;
 return child[i].search(key);

void insertNonFull(int key) {

int i = n - 1;

if (leaf) {

while (i >= 0 && keys[i] > key) {

keys[i + 1] = keys[i];

i--;

keys[i + 1] = key;

n++;

} else {

while (i >= 0 && keys[i] > key)

i--;

if (child[i + 1].n == 2 * t - 1) {

splitChild(i + 1, child[i + 1]);

if (keys[i + 1] < key)

i++;

child[i + 1].insertNonFull(key);

void splitChild(int i, BTreeNode y) {

BTreeNode z = new BTreeNode(y.t, [Link]);

z.n = t - 1;

for (int j = 0; j < t - 1; j++)

[Link][j] = [Link][j + t];

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

[Link][j] = [Link][j + t];

y.n = t - 1;

for (int j = n; j >= i + 1; j--)

child[j + 1] = child[j];

child[i + 1] = z;

for (int j = n - 1; j >= i; j--)

keys[j + 1] = keys[j];

keys[i] = [Link][t - 1];

n++;

void traverse() {

int i;

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

if (!leaf)

child[i].traverse();

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

if (!leaf)

child[i].traverse();

class BTree {

BTreeNode root;
int t;

BTree(int t) {

this.t = t;

root = null;

void insert(int key) {

if (root == null) {

root = new BTreeNode(t, true);

[Link][0] = key;

root.n = 1;

} else {

if (root.n == 2 * t - 1) {

BTreeNode s = new BTreeNode(t, false);

[Link][0] = root;

[Link](0, root);

int i = 0;

if ([Link][0] < key)

i++;

[Link][i].insertNonFull(key);

root = s;

} else {

[Link](key);

boolean search(int key) {

return (root == null) ? false : [Link](key) != null;

void display() {
 if (root != null)

[Link]();

[Link]();

public class BTreeDemo {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter minimum degree (t) of B-Tree: ");

int t = [Link]();

BTree tree = new BTree(t);

int choice, key;

do {

[Link]("\n--- B-Tree Operations ---");

[Link]("1. Insert");

[Link]("2. Search");

[Link]("3. Display Tree");

[Link]("4. Exit");

[Link]("Enter choice: ");

choice = [Link]();

switch (choice) {

case 1:

[Link]("Enter key to insert: ");

key = [Link]();

[Link](key);

[Link]("Key Inserted.");

break;

case 2:

[Link]("Enter key to search: ");

key = [Link]();
 if ([Link](key))

[Link]("Key Found in B-Tree.");

else

[Link]("Key NOT Found.");

break;

case 3:

[Link]("B-Tree Traversal:");

[Link]();

break;

case 4:

[Link]("Exiting...");

break;

default:

[Link]("Invalid choice!");

} while (choice != 4);

[Link]();

-----------------------------------------------------------------------------------------------------------------------------------------------------