INDEX
S.N Description Date Signature
1. Searching Algorithms
Linear Search and Binary Search with recursive and
non-recursive implementations.
2. Dictionary ADT using Hashing
Implementation using Java HashMap.
3. Dijkstra’s Algorithm
Single source shortest path implementation.
4. Binary Tree Traversals
Preorder, Inorder, Postorder traversals.
5. BFS and DFS
Graph traversal techniques.
6. Sorting Algorithms
Bubble, Insertion, Quick, Merge, Heap, Radix, Binary
Tree Sort.
7. B-Tree Operations
Insertion and Searching.
8. Kruskal’s Algorithm
Minimum Cost Spanning Tree.
9. KMP Algorithm
Pattern matching technique.
Experiment – 1
Objective : -
To implement Linear Search and Binary Search using both recursive and non-
recursive methods in Java.
1(a) Linear Search
Definition
Linear Search is a simple searching technique where each element of the list is checked
sequentially until the desired element is found or the list ends.
Algorithm
1. Start from the first element.
2. Compare each element with the key.
3. If match found, return index.
4. Else continue till end.
Program :-
class LinearSearch {
static int recursiveSearch(int arr[], int index, int key) {
if (index == [Link])
return -1;
if (arr[index] == key)
return index;
return recursiveSearch(arr, index + 1, key);
static int iterativeSearch(int arr[], int key) {
for (int i = 0; i < [Link]; i++)
if (arr[i] == key)
return i;
return -1;
public static void main(String args[]) {
int arr[] = {10, 20, 30, 40, 50};
int key = 30;
[Link]("Recursive Search Index: " +
recursiveSearch(arr, 0, key));
[Link]("Iterative Search Index: " +
iterativeSearch(arr, key));
1(b) Binary Search
Definition
Binary Search works on sorted arrays by repeatedly dividing the search interval in half.
Algorithm
1. Find middle element.
2. If key equals mid → success.
3. If key < mid → search left half.
4. Else search right half.
Program :-
class BinarySearch {
static int recursiveBinary(int arr[], int low, int high, int key) {
if (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
if (key < arr[mid])
return recursiveBinary(arr, low, mid - 1, key);
return recursiveBinary(arr, mid + 1, high, key);
return -1;
static int iterativeBinary(int arr[], int key) {
int low = 0, high = [Link] - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
if (key < arr[mid]) high = mid - 1;
else low = mid + 1;
return -1;
public static void main(String args[]) {
int arr[] = {10, 20, 30, 40, 50};
int key = 40;
[Link](recursiveBinary(arr, 0, [Link] - 1, key));
[Link](iterativeBinary(arr, key));
Output :-
Linear and Binary Search were successfully implemented using recursive and non-
recursive approaches.
Experiment – 2
Objective : -
To implement Dictionary ADT using Hashing.
Algorithm
1. Use HashMap.
2. Insert key–value pairs.
3. Perform search and delete operations.
Program :-
import [Link];
class DictionaryADT {
public static void main(String args[]) {
HashMap<String, String> dict = new HashMap<>();
[Link]("OS", "Operating System");
[Link]("DBMS", "Database Management System");
[Link]([Link]("OS"));
[Link]("DBMS");
Output :-
Dictionary operations were implemented using hashing successfully.
Experiment – 3
Objective : -
To implement Dijkstra’s Algorithm for single source shortest path.
Algorithm
1. Initialize distance of source as 0.
2. Mark all nodes unvisited.
3. Pick minimum distance node.
4. Update distances of neighbors.
Program :-
import [Link].*;
class Dijkstra {
static final int INF = 999;
static void dijkstra(int g[][], int s) {
int d[] = new int[[Link]];
boolean v[] = new boolean[[Link]];
[Link](d, INF);
d[s] = 0;
for (int i = 0; i < [Link]; i++) {
int u = -1, min = INF;
for (int j = 0; j < [Link]; j++)
if (!v[j] && d[j] < min) {
min = d[j];
u = j;
v[u] = true;
for (int k = 0; k < [Link]; k++)
if (g[u][k] != 0 && d[u] + g[u][k] < d[k])
d[k] = d[u] + g[u][k];
[Link]([Link](d));
public static void main(String args[]) {
int g[][] = {{0,2,0},{2,0,3},{0,3,0}};
dijkstra(g, 0);
Output :-
Shortest paths from the source vertex were successfully computed.
Experiment – 4
Objective : -
To traverse a binary tree using Preorder, Inorder, and Postorder traversals.
Program :-
class Tree {
static class Node {
int data;
Node left, right;
Node(int d) { data = d; }
static void preorder(Node r) {
if (r != null) {
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
static void inorder(Node r) {
if (r != null) {
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
static void postorder(Node r) {
if (r != null) {
postorder([Link]);
postorder([Link]);
[Link]([Link] + " ");
public static void main(String args[]) {
Node r = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);
preorder(r);
inorder(r);
postorder(r);
Output :-
Binary tree traversals were performed successfully.
Experiment – 5
Objective : -
To implement BFS and DFS for a given graph.
Program :-
import [Link].*;
class Graph {
LinkedList<Integer>[] adj;
Graph(int v) {
adj = new LinkedList[v];
for (int i = 0; i < v; i++)
adj[i] = new LinkedList<>();
void addEdge(int u, int v) {
adj[u].add(v);
void bfs(int s) {
boolean v[] = new boolean[[Link]];
Queue<Integer> q = new LinkedList<>();
[Link](s);
v[s] = true;
while (![Link]()) {
s = [Link]();
[Link](s + " ");
for (int n : adj[s])
if (!v[n]) {
v[n] = true;
[Link](n);
void dfs(int s, boolean v[]) {
v[s] = true;
[Link](s + " ");
for (int n : adj[s])
if (!v[n])
dfs(n, v);
public static void main(String args[]) {
Graph g = new Graph(4);
[Link](0,1);
[Link](0,2);
[Link](1,3);
[Link](0);
[Link](0, new boolean[4]);
Output :-
Graph traversal using BFS and DFS was successful.
Experiment – 6
Objective : -
To implement different Sorting Algorithms.
Program :-
class QuickSort {
static void quick(int a[], int l, int h) {
if (l < h) {
int p = a[h], i = l - 1;
for (int j = l; j < h; j++)
if (a[j] < p) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
int t = a[i+1]; a[i+1] = a[h]; a[h] = t;
quick(a, l, i);
quick(a, i+2, h);
public static void main(String args[]) {
int a[] = {5,2,8,1};
quick(a, 0, [Link]-1);
for (int i : a) [Link](i+" ");
}}
Experiment – 7
Objective : -
To implement Insertion and Searching operations in a B-Tree using Java.
Definition :-
A B-Tree is a self-balancing search tree in which all leaf nodes are at the same level.
It is widely used in database systems and file systems because it minimizes disk
accesses.
Algorithm
Insertion in B-Tree
1. Start from root node.
2. If node is full, split it.
3. Insert key in the appropriate child.
4. Maintain sorted order of keys.
Searching in B-Tree
1. Start from root.
2. Compare key with node keys.
3. Move to appropriate child.
4. Repeat until key is found or leaf is reached.
Program :-
class BTree {
int t = 2; // Minimum degree
class Node {
int n = 0;
int key[] = new int[2 * t - 1];
Node child[] = new Node[2 * t];
boolean leaf = true;
}
Node root = new Node();
void insert(int k) {
Node r = root;
if (r.n == 2 * t - 1) {
Node s = new Node();
root = s;
[Link] = false;
[Link][0] = r;
split(s, 0, r);
insertNonFull(s, k);
} else
insertNonFull(r, k);
void insertNonFull(Node x, int k) {
int i = x.n - 1;
if ([Link]) {
while (i >= 0 && k < [Link][i]) {
[Link][i + 1] = [Link][i];
i--;
}
[Link][i + 1] = k;
x.n++;
} else {
while (i >= 0 && k < [Link][i]) i--;
insertNonFull([Link][i + 1], k);
void split(Node x, int i, Node y) {
Node z = new Node();
[Link] = [Link];
z.n = t - 1;
for (int j = 0; j < t - 1; j++)
[Link][j] = [Link][j + t];
y.n = t - 1;
[Link][i + 1] = z;
[Link][i] = [Link][t - 1];
x.n++;
public static void main(String args[]) {
BTree bt = new BTree();
[Link](10);
[Link](20);
[Link](5);
[Link]("B-Tree insertion completed");
Output :-
To implement Kruskal’s Algorithm to generate the Minimum Cost Spanning Tree
(MCST).
Experiment – 8
Objective : -
To implement Kruskal’s Algorithm to generate the Minimum Cost Spanning Tree
(MCST).
Definition :-
Kruskal’s algorithm is a greedy algorithm that builds the MST by selecting the
minimum weight edges without forming cycles.
Algorithm
1. Sort all edges by increasing weight.
2. Pick smallest edge.
3. Check for cycle formation.
4. Include edge if no cycle.
5. Repeat until MST is formed.
Program :-
import [Link].*;
class Kruskal {
static class Edge {
int src, dest, weight;
Edge(int s, int d, int w) {
src = s; dest = d; weight = w;
static int find(int parent[], int i) {
if (parent[i] == i) return i;
return find(parent, parent[i]);
}
static void union(int parent[], int x, int y) {
parent[find(parent, x)] = find(parent, y);
public static void main(String args[]) {
Edge edges[] = {
new Edge(0,1,10),
new Edge(1,2,15),
new Edge(0,2,5)
};
[Link](edges, [Link](e -> [Link]));
int parent[] = {0,1,2};
for (Edge e : edges) {
if (find(parent, [Link]) != find(parent, [Link])) {
[Link]([Link] + " - " + [Link] + " : " + [Link]);
union(parent, [Link], [Link]);
Output :-
Minimum Cost Spanning Tree was generated successfully using Kruskal’s Algorithm.
Experiment – 9
Objective : -
To implement Knuth–Morris–Pratt (KMP) Algorithm for pattern matching.
Definition : -
KMP algorithm improves pattern matching by avoiding unnecessary comparisons using
the LPS (Longest Prefix Suffix) array.
Algorithm
1. Preprocess pattern to compute LPS array.
2. Compare pattern with text.
3. On mismatch, use LPS to skip comparisons.
4. Continue until pattern is found.
Program :-
class KMP {
static void computeLPS(String pat, int lps[]) {
int len = 0;
lps[0] = 0;
for (int i = 1; i < [Link](); ) {
if ([Link](i) == [Link](len))
lps[i++] = ++len;
else if (len > 0)
len = lps[len - 1];
else
lps[i++] = 0;
}
static void search(String txt, String pat) {
int lps[] = new int[[Link]()];
computeLPS(pat, lps);
int i = 0, j = 0;
while (i < [Link]()) {
if ([Link](i) == [Link](j)) {
i++; j++;
if (j == [Link]()) {
[Link]("Pattern found at index " + (i - j));
j = lps[j - 1];
} else if (i < [Link]() && [Link](i) != [Link](j)) {
if (j != 0) j = lps[j - 1];
else i++;
public static void main(String args[]) {
search("ABABDABACDABABCABAB", "ABABCABAB");
}
Output :-
Pattern matching using KMP algorithm was successfully performed..