Design and Anaysis of Agorithms Lab Manua

Course Code: CSL47  CSE / ISE  Semester IV

1. Seection Sort Technique

Aim: Sort a given set of eements using Seection Sort technique and compute its time taken.
Run the program for different vaues of N and record the time taken to sort.

Agorithm Paradigm: Comparison-based Brute Force Seection

Time Compexity: Best: O(n²) | Average: O(n²) | Worst: O(n²)

Space Compexity: O1) auxiiary space In-pace)

import [Link].*;
public class Sort {
public static void selectionSort(int arr[]){
int n=[Link], minPos;
for(int i=0;i<n-1;i++){
minPos=i;
for(int j=i+1;j<n;j++){
if(arr[minPos]>arr[j]){
minPos=j;
}
}
int temp=arr[i];
arr[i]=arr[minPos];
arr[minPos]=temp;
}
}

public static void main(String[] args)

{
Random random=new Random();
Scanner sc=new Scanner([Link]);
[Link]("Enter array size:");
int n=[Link]();
int[] arr=new int[n];
[Link]("Enter the elements:");
for(int i=0;i<n;i++)
{
arr[i]=[Link](1000);
}
double start=[Link]();
selectionSort(arr);
double end=[Link]();
[Link]("Sorted array:");
for(int i=0;i<n;i++)
{
[Link](arr[i]+" ");
}
[Link]("Time taken:"+ (end-start)+"ms");
}
}
SAMPLE OUTPUT
2. Merge Sort Technique

Aim: Sort a given set of N integer eements using Merge Sort technique and compute its time
taken. Run the program for different vaues of N and record the time taken to sort.

Agorithm Paradigm: Divide and Conquer

Time Compexity: Best: O(n og n) | Average: O(n og n) | Worst: O(n og n)

Space Compexity: O(n) auxiiary space

import [Link].*;

public class MergeSort {

static int[] a;

public static void simpleMerge(int low, int mid, int high) {

int i = low, j = mid + 1, k = low;
int[] c = new int[[Link]]; // Temporary array for merging

while (i <= mid && j <= high) {

if (a[i] < a[j])
c[k++] = a[i++];
else
c[k++] = a[j++];
}

while (i <= mid)

c[k++] = a[i++];

while (j <= high)

c[k++] = a[j++];

for (i = low; i <= k-1; i++)

a[i] = c[i];
}

public static void mergeSort(int low, int high) {

if (low < high) {
int mid = (low + high) / 2;
mergeSort(low, mid);
mergeSort(mid + 1, high);
simpleMerge(low, mid, high);
}
}

public static void main(String[] args)

{
Random random = new Random();
Scanner sc = new Scanner([Link]);
[Link]("Enter array size:");
 int n = [Link]();
a = new int[n];
[Link]("Generating random elements:");
for (int i = 0; i < n; i++) {
a[i] = [Link](1000);
[Link](a[i] + " ");
}
[Link]();

double start = [Link]();

mergeSort(0, n - 1);
double end = [Link]();

[Link]("Sorted array:");
for (int i = 0; i < n; i++) {
[Link](a[i] + " ");
}
[Link]();

[Link]("Time taken: " + (end - start) + "ms");

}
}

SAMPLE OUTPUT
3. Quick Sort Technique

Aim: Sort a given set of N integer eements using Quick Sort technique and compute its time
taken. Run the program for different vaues of N and record the time taken to sort.

Agorithm Paradigm: Divide and Conquer

Time Compexity: Average: O(n og n) | Worst: O(n²) (occurs when spit is unbaanced)

Space Compexity: Oog n ca stack space

import [Link].*;
public class QuickSort {
static int[] a = new int[20];
static int n, i, j, temp;
public static void quickSort(int low, int high) {
int j;
if (low <= high) {
j = partition(low, high);
quickSort(low, j - 1);
quickSort(j + 1, high);
}
}
public static int partition(int low, int high) {
int i, j, key;
key = a[low];
i = low + 1;
j = high;
while (true) {
while (i < high && a[i] < key)
i++;
while (key < a[j])
j--;
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
} else {
temp = a[low];
a[low] = a[j];
a[j] = temp;
return j;
}
}
}
public static void main(String[] args) {
Random random = new Random();
Scanner sc = new Scanner([Link]);
[Link]("Enter array size:");
int n = [Link]();
a = new int[n]; // Initialize the global array with the specified size
[Link]("Generating random elements:");
 for (int i = 0; i < n; i++) {
a[i] = [Link](1000);
[Link](a[i] + " ");
}
[Link]();
double start = [Link]();
quickSort(0, n - 1);
double end = [Link]();
[Link]("Sorted array:");
for (int i = 0; i < n; i++) {
[Link](a[i] + " ");
}
[Link]();
[Link]("Time taken: " + (end - start) + "ms");
}
}

SAMPLE OUTPUT
4. Horspoo's Agorithm for String Matching

Aim: Write a program to impement Horspooʼs agorithm for String Matching.

Agorithm Paradigm: Input Enhancement / Bad-Character Shift Tabe

Time Compexity: Average: O(n) | Worst: O(m * n) (where m = pattern en, n = text en)

Space Compexity: OΣ) auxiiary space (size of aphabet representation)

public class HorspoolStringMatching {

private static final int ALPHABET_SIZE = 256;
public static void main(String[] args) {
String text = "BESS_KNEW_ABOUT_BAOBABS";
String pattern = "BAOBAB";
int index = search(text, pattern);
if (index != -1) {
[Link]("Pattern found at index " + index);
} else {
[Link]("Pattern not found in the text.");
}
}
public static int[] preprocessPattern(String pattern) {
int[] table = new int[ALPHABET_SIZE];
int patternLength = [Link]();
for (int i = 0; i < ALPHABET_SIZE; i++) {
table[i] = patternLength;
}
for (int i = 0; i < patternLength - 1; i++) {
char c = [Link](i);
table[c] = patternLength - 1 - i;
}
return table;
}
public static int search(String text, String pattern) {
int textLength = [Link]();
int patternLength = [Link]();
int[] shiftTable = preprocessPattern(pattern);
int i = patternLength - 1;
while (i < textLength) {
int j = patternLength - 1;
while (j >= 0 && [Link](i) == [Link](j)) {
i--;
j--;
}
if (j == -1) {
return i + 1;
}
else
{
i += [Link](1, patternLength - 1 - j + shiftTable[[Link](i)]);
}
}
 return -1;
}
}

SAMPLE OUTPUT
5. 0/1 Knapsack Probem Dynamic Programming)

Aim: Design and impement Program to sove 0/1 Knapsack probem using Dynamic
Programming method.

Agorithm Paradigm: Dynamic Programming Tabuation method)

Time Compexity: O(n * W) (where n = number of objects, W = capacity of knapsack)

Space Compexity: O(n * W) for memoization tabe grid

import [Link];

public class Knapsack {

public static int max(int a, int b) {

return a > b ? a : b;
}

public static void knapsack(int n, int[] w, int m, int[][] v, int[] p) {

int i, j;

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

for (j = 0; j <= m; j++) {
if (i == 0 || j == 0)
v[i][j] = 0;
else if (j < w[i])
v[i][j] = v[i - 1][j];
else
v[i][j] = max(v[i - 1][j], v[i - 1][j - w[i]] + p[i]);
}
}
}

public static void main(String[] args) {

int m, i, j, n;
int[] p = new int[10];
int[] w = new int[10];
int[][] v = new int[10][10];

Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of objects:");

n = [Link]();

[Link]("Enter the weights of n objects:");

for (i = 1; i <= n; i++)
w[i] = [Link]();

[Link]("Enter the profits of n objects:");

for (i = 1; i <= n; i++)
p[i] = [Link]();
 [Link]("Enter the capacity of Knapsack:");
m = [Link]();

knapsack(n, w, m, v, p);

[Link]("The output is:");

for (i = 0; i <= n; i++) {
for (j = 0; j <= m; j++)
[Link](v[i][j] + " ");
[Link]();
}

[Link]();
}
}

SAMPLE OUTPUT
7. Dijkstra's Singe Source Shortest Path

Aim: Impement Singe source shortest path using Dijkstraʼs agorithm.

Agorithm Paradigm: Greedy Technique

Time Compexity: O(n²) (can be optimized to OE og V) using Min-Heap)

Space Compexity: O(n) for distance tracking array

import [Link];

public class Dijkstra {

public static void dijkstra(int n, int v, int[][] cost, int[] dist) {

int i, u, count, w;
int[] flag = new int[10];
int min;

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

flag[i] = 0;
dist[i] = cost[v][i];
}
flag[v] = 1;
dist[v] = 0;
count = 2;

while (count <= n) {

min = 999;
u = 0;
for (w = 1; w <= n; w++) {
if (dist[w] < min && flag[w] == 0) {
min = dist[w];
u = w;
}
}
flag[u] = 1;
count++;

for (w = 1; w <= n; w++) {

if ((dist[u] + cost[u][w] < dist[w]) && flag[w] == 0) {
dist[w] = dist[u] + cost[u][w];
}
}
}
}

public static void main(String[] args) {

int n, v, i, j;
int[][] cost = new int[10][10];
int[] dist = new int[10];
 Scanner scanner = new Scanner([Link]);

[Link]("Enter the number of nodes: ");

n = [Link]();

[Link]("\nEnter the cost matrix:");

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
cost[i][j] = [Link]();
if (cost[i][j] == 0) {
cost[i][j] = 999;
}
}
}

[Link]("\nEnter the source vertex: ");

v = [Link]();

dijkstra(n, v, cost, dist);

[Link]("Shortest paths from vertex " + v + ":");

for (j = 1; j <= n; j++) {
if (j != v) {
[Link](v + "->" + j + ":::::" + dist[j]);
}
}

[Link]();
}
}

SAMPLE OUTPUT
8. Minimum Spanning Tree Prim's Agorithm)

Aim: Find Minimum Cost Spanning Tree of a given undirected graph using Primʼs agorithm.

Agorithm Paradigm: Greedy Strategy

Time Compexity: O(n²) (can be optimized to OE og V

Space Compexity: O(n) for component tracking arrays

import [Link];

public class PrimsAlgorithm {

static int a, b, u, v, n, i, j, ne = 1;
static int min, mincost = 0;
static int[] visited = new int[10];
static int[][] cost = new int[10][10];

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);

[Link]("\nEnter the number of nodes: ");

n = [Link]();

[Link]("\nEnter the adjacency matrix:");

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
cost[i][j] = [Link]();
if (cost[i][j] == 0)
cost[i][j] = 999;
}

visited[1] = 1;
[Link]();

while (ne < n) {

for (i = 1, min = 999; i <= n; i++)
for (j = 1; j <= n; j++)
if (cost[i][j] < min)
if (visited[i] != 0) {
min = cost[i][j];
a = u = i;
b = v = j;
}
if (visited[u] == 0 || visited[v] == 0) {
[Link]("\nEdge %d: (%d %d) cost: %d", ne++, a, b, min);
mincost += min;
visited[b] = 1;
}
cost[a][b] = cost[b][a] = 999;
}

[Link]("\nMinimum cost = " + mincost);

 [Link]();
}
}

SAMPLE OUTPUT
9. Minimum Spanning Tree Kruska's Agorithm)

Aim: Find Minimum Cost Spanning Tree of a given undirected graph using Kruskas
agorithm.

Agorithm Paradigm: Greedy Strategy (utiizing Union-Find cyce prevention)

Time Compexity: OE og E) or OE og V (sorting edges takes maximum time)

Space Compexity: OV) for parent pointer array representation

import [Link];

public class Kruskal {

static int i, j, k, a, b, u, v, n, ne = 1;
static int min, mincost = 0;
static int[][] cost = new int[9][9];
static int[] parent = new int[9];

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);

[Link]("\n\n\tImplementation of Kruskal's algorithm\n\n");

[Link]("Enter the number of vertices:");
n = [Link]();
[Link]("\nEnter the cost adjacency matrix:");

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

for (j = 1; j <= n; j++) {
cost[i][j] = [Link]();
if (cost[i][j] == 0) {
cost[i][j] = 999;
}
}
}

[Link]("\nThe edges of Minimum Cost Spanning Tree are\n");

while (ne < n) {
for (i = 1, min = 999; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (cost[i][j] < min) {
min = cost[i][j];
a = u = i;
b = v = j;
}
}
}
u = find(u);
v = find(v);
if (uni(u, v) == 1) {
[Link](ne++ + " edge (" + a + "," + b + ") =" + min);
mincost += min;
 }
cost[a][b] = cost[b][a] = 999;
}

[Link]("\nMinimum cost = " + mincost);

[Link]();
}

public static int find(int i) {

while (parent[i] != 0)
i = parent[i];
return i;
}

public static int uni(int i, int j) {

if (i != j) {
parent[j] = i;
return 1;
}
return 0;
}
}

SAMPLE OUTPUT
11. Sum of Subsets Probem

Aim: Impement “Sum of Subsetsˮ using Backtracking: Find a subset of a given set S = {s1,
s2,……,sn} of n positive integers whose sum is equa to a given positive integer d.

Agorithm Paradigm: Backtracking DFS state-space search with pruning)

Time Compexity: O2ⁿ (exponentia worst-case subset choices)

Space Compexity: O(n) recursive path ca stack size

import [Link];

public class SubsetSum {

public static void subset(int n, int d, int[] w) {
int[] x = new int[10];
int i, k, s;

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

x[i] = 0;

s = 0;
k = 1;
x[k] = 1;

while (true) {
if (k <= n && x[k] == 1) {
if (s + w[k] == d) {
[Link]("\nSolution is:");
for (i = 1; i <= n; i++) {
if (x[i] == 1)
[Link](w[i] + " ");
}
[Link]();
x[k] = 0;
} else if (s + w[k] < d)
s += w[k];
else
x[k] = 0;
} else {
k--;
while (k > 0 && x[k] == 0)
k--;
if (k == 0)
break;
s = s - w[k];
x[k] = 0;
}
k = k + 1;
x[k] = 1;
}
}
 public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
int n, d, i;
int[] w = new int[20];

[Link]("\nEnter the value of n:");

n = [Link]();

[Link]("Enter the set values in increasing order:");

for (i = 1; i <= n; i++)
w[i] = [Link]();

[Link]("\nEnter the maximum value:");

d = [Link]();

subset(n, d, w);

[Link]();
}
}

SAMPLE OUTPUT
12. NQueens Probem Backtracking)

Aim: Impement “NQueens Probemˮ using Backtracking.

Agorithm Paradigm: Backtracking Iterative state search tree sover)

Time Compexity: ON! (worst-case configuration checking)

Space Compexity: ON) coordinate ayout array

import [Link];

public class NQueens {

static int[][] s = new int[100][100];

static void display(int[] m, int n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = 0;
}
}

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

s[i][m[i]] = 1;
}
[Link]();

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

for (int j = 0; j < n; j++) {
[Link](s[i][j] + " ");
}
[Link]();
}
}

static int place(int[] m, int k) {

for (int i = 0; i < k; i++)
if (m[i] == m[k] || ([Link](m[i] - m[k]) == [Link](i - k)))
return 0;
return 1;
}

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);
int[] m = new int[25];
int n, k;

[Link]("\nENTER THE NO OF QUEENS:");

n = [Link]();

[Link]("\nTHE SOLUTION TO QUEENS PROBLEM IS\n");

n--;
 for (m[0] = 0, k = 0; k >= 0; m[k] = m[k] + 1) {
while (m[k] <= n && !(place(m, k) == 1))
m[k] = m[k] + 1;

if (m[k] <= n)
if (k == n)
display(m, n + 1);
else {
k++;
m[k] = -1;
}
else
k--;
}
}
}

SAMPLE OUTPUT