Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-1
1. Write a program to sort given elements of an array in ascending order
using bubble sort. Analyze the time complexity for best, average and worst
case.
package PROFDAA.PR1;
import java.util.*;
public class BubbleSort{
public static void Bubble(int arr[]) {
for (int turn = 0; turn < arr.length - 1; turn++) {
boolean swap = false;
for (int j = 0; j < arr.length - 1 - turn; j++) {
if (arr[j] > arr[j + 1]) {
// For Swapping
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
}
}
if (!swap) {
break;
}
}
}
public static void Display(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {

PARTH TEJANI 1
Design and Analysis of Algorithms CP 12202040601044

Scanner sc = new Scanner(System.in);

System.out.println("Choose the case:");
System.out.println("1. Best Case");
System.out.println("2. Average Case");
System.out.println("3. Worst Case");
int choice = sc.nextInt();
int size = 100;
int arr[] = new int[size];
switch (choice) {
case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best Case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
System.out.println("Average Case:");
break;
case 3:
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
System.out.println("Worst Case:");
break;
default:
System.out.println("Invalid choice!");
return;
}

PARTH TEJANI 2
Design and Analysis of Algorithms CP 12202040601044

Display(arr);
long startTime = System.nanoTime(); // Use nanoTime for better resolution
// BubbleSort(arr);
Bubble(arr);
long endTime = System.nanoTime();
Display(arr);
long duration = endTime - startTime;
System.out.println("Start time: " + startTime);
System.out.println("End time: " + endTime);
System.out.println("Time taken to sort: " + duration / 1000000.0 + " milliseconds");
}
}

 OUTPUT:

PARTH TEJANI 3
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-2
2. Write a program to sort given elements of an array in ascending order
using selection sort. Analyze the time complexity for best, average and worst
case.
package PROFDAA.PR2;
import java.util.*;
public class SelectionSort {
public static void Selection(int arr[]){
for (int i = 0; i < arr.length - 1; i++) {
int MinPos = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[MinPos] > arr[j]) { // Increasing order
MinPos = j;
}
}
// For Swapping
int temp = arr[MinPos];
arr[MinPos] = arr[i];
arr[i] = temp;
}
}
public static void Display(int arr[]){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Choose the case:");
System.out.println("1. Best Case");

PARTH TEJANI 4
Design and Analysis of Algorithms CP 12202040601044

System.out.println("2. Average Case");

System.out.println("3. Worst Case");
int choice = sc.nextInt();
int size = 100; // Increase the size for better time measurement
int arr[] = new int[size];
switch (choice) {
case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best Case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
System.out.println("Average Case:");
break;
case 3:
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
System.out.println("Worst Case:");
break;
default:
System.out.println("Invalid choice!");
return;
}
Display(arr);
long startTime = System.nanoTime(); // Use nanoTime for better resolution
Selection(arr);

PARTH TEJANI 5
Design and Analysis of Algorithms CP 12202040601044

long endTime = System.nanoTime();

Display(arr);
long duration = endTime - startTime;
System.out.println("Start time: " + startTime);
System.out.println("End time: " + endTime);
System.out.println("Time taken to sort: " + duration / 1000000.0 + " milliseconds");

}
}

 OUTPUT:

PARTH TEJANI 6
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-3
3. Write a program to implement heap sort.
package PROFDAA.PR3;
import java.util.*;
public class heapSort {
public static void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

heapify(arr, n, i);
}
}
public static void heapSort(int arr[]) {
int n = arr.length;
for (int i = ((n / 2) - 1); i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];

PARTH TEJANI 7
Design and Analysis of Algorithms CP 12202040601044

arr[i] = temp;
heapify(arr, n, 0);
}
}
public static void Display(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Choose the case:");
System.out.println("1.Best case");
System.out.println("2.Average case");
System.out.println("3.Worst case");
int choice = sc.nextInt();
int size = 100;
int[] arr = new int[size];
switch (choice) {
case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
System.out.println("Average case:");

PARTH TEJANI 8
Design and Analysis of Algorithms CP 12202040601044

break;
case 3:
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
System.out.println("Worst case:");
break;
default:
System.out.println("Invalid choice!");
break;
}
Display(arr);
long startTime = System.nanoTime();
heapSort(arr);
long endTime = System.nanoTime();
Display(arr);
long duration = endTime - startTime;
System.out.println("Start time:" + startTime);
System.out.println("End time:" + endTime);
System.out.println("Time taken to sort:" + duration / 1000000.0 + "milliseconds");
}
}

 OUTPUT:

PARTH TEJANI 9
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-4
4. Write a program to search given element from an array using sequential
search and binary search. Analyze the time complexity for best, average and
worst case.
package PROFDAA.PR4;

import java.util.*;

public class Search {

public static int sequentialSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}

public static int binarySearch(int[] arr, int target) {

int left = 0;
int right = arr.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {

PARTH TEJANI 10
Design and Analysis of Algorithms CP 12202040601044

right = mid - 1;
}
}
return -1;
}

public static void Display(int arr[]) {

for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Choose the case:");
System.out.println("1.Best Case");
System.out.println("2.Average case");
System.out.println("3.Worst case");
int choice = sc.nextInt();
int size = 100;
int[] arr = new int[size];
switch (choice) {
case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);

PARTH TEJANI 11
Design and Analysis of Algorithms CP 12202040601044

}
Arrays.sort(arr);
System.out.println("Average case:");
break;
case 3:
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
Arrays.sort(arr);
System.out.println("Worst case:");
break;
default:
System.out.println("Invalid choice!");
return;
}
Display(arr);
System.out.println("Enter the element to search:");
int target = sc.nextInt();
long startTimeSeq = System.nanoTime();
int resultSeq = sequentialSearch(arr, target);
long endTimeSeq = System.nanoTime();
long durationSeq = endTimeSeq - startTimeSeq;
long startTimeBin = System.nanoTime();
int resultBin = binarySearch(arr, target);
long endTimeBin = System.nanoTime();
long durationBin = endTimeBin - startTimeBin;
// Display results
System.out.println("Sequential Search:");
System.out.println("Index: " + resultSeq);
System.out.println("Time taken: " + durationSeq / 1000000.0 + " milliseconds");
System.out.println("Binary Search:");
System.out.println("Index: " + resultBin);

PARTH TEJANI 12
Design and Analysis of Algorithms CP 12202040601044

System.out.println("Time taken: " + durationBin / 1000000.0 + " milliseconds");

}
}

 OUTPUT:

PARTH TEJANI 13
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-5
5. Write a program to sort given elements of an array in ascending order
using merge sort. Analyze the time complexity for best, average and worst
case.
//package PROFDAA.PR5;
import java.util.*;
public class MergeSort {
public static void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
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++;

PARTH TEJANI 14
Design and Analysis of Algorithms CP 12202040601044

k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void sort(int arr[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
sort(arr, beg, mid);
sort(arr, mid + 1, end);
merge(arr, beg, mid, end);
}
}
public static void Display(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Choose the case:");
System.out.println("1.Best Case");
System.out.println("2.Average case");
System.out.println("3. Worst Case");
int choice = sc.nextInt();
int size = 100;
int arr[] = new int[size];
switch (choice) {

PARTH TEJANI 15
Design and Analysis of Algorithms CP 12202040601044

case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best Case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
System.out.println("Average Case:");
break;
case 3:
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
System.out.println("Worst Case:");
break;
default:
System.out.println("Invalid choice!");
return;
}
Display(arr);
long startTime = System.nanoTime();
sort(arr, 0, arr.length - 1);
long endTime = System.nanoTime();
Display(arr);
long duration = endTime - startTime;
System.out.println("Start time: " + startTime);
System.out.println("End time: " + endTime);
System.out.println("Time taken to sort: " + duration / 1000000.0 + " milliseconds");

PARTH TEJANI 16
Design and Analysis of Algorithms CP 12202040601044

}
}

 OUTPUT:

PARTH TEJANI 17
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-6
6. Write a program to sort given elements of an array in ascending order
using quick sort. Analyze the time complexity for best, average and worst
case.
// package PROFDAA.PR6;

import java.util.Random;
import java.util.Scanner;
public class QuickSort {
public 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 int partition(int arr[],int low,int high){
int pivot=arr[high];
int i=(low-1);
for(int j=low;j<high;j++){
if(arr[j]<pivot){
i++;
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int temp=arr[i+1];
arr[i+1]=arr[high];
arr[high]=temp;
return i+1;

PARTH TEJANI 18
Design and Analysis of Algorithms CP 12202040601044

}
public static void Display(int arr[]){
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]+" ");
}
System.out.println();
}
public static void main(String[] args) ;
Scanner sc = new Scanner(System.in);
System.out.println("Choose the case:");
System.out.println("1. Best Case");
System.out.println("2. Average Case");
System.out.println("3. Worst Case");
int choice = sc.nextInt();
int size = 100; // Increase the size for better time measurement
int arr[] = new int[size];
switch (choice) {
case 1:
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
System.out.println("Best Case:");
break;
case 2:
Random rand = new Random();
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(100);
}
System.out.println("Average Case:");
break;
case 3:
for (int i = 0; i < size; i++) {

PARTH TEJANI 19
Design and Analysis of Algorithms CP 12202040601044

arr[i] = size - i;
}
System.out.println("Worst Case:");
break;
default:
System.out.println("Invalid choice!");
return;
}
Display(arr);
long startTime = System.nanoTime(); // Use nanoTime for better resolution
Quicksort(arr, 0, arr.length - 1);
long endTime = System.nanoTime();
Display(arr);
long duration = endTime - startTime;
System.out.println("Start time: " + startTime);
System.out.println("End time: " + endTime);
System.out.println("Time taken to sort: " + duration / 1000000.0 + " milliseconds");
}
}

 OUTPUT:

PARTH TEJANI 20
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-7
7. Write a program to implement making change problem using greedy
algorithm.
import java.util.Scanner;
public class GA_makingChange {
public static void findMinCoin(int[] denomination, int amount) {
int coinCount = 0;
System.out.println("coins used to make the amount:");
for (int i = 0; i < denomination.length; i++) {
if (amount >= denomination[i]) {
int numCoins = amount / denomination[i];
amount = amount % denomination[i];
coinCount += numCoins;
System.out.println(denomination[i] + " X " + numCoins);
}
}
if (amount != 0) {
System.out.println("The amount cannot be made with given demomations.");
} else {
System.out.println("minimum number of coins required: " + coinCount);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] denomination = { 1000, 500, 100, 50, 25, 10, 5, 1 };
System.out.print("Enter the amount in Rupees: ");
int amount = scanner.nextInt();
findMinCoin(denomination, amount);
scanner.close();
}
}

PARTH TEJANI 21
Design and Analysis of Algorithms CP 12202040601044

 OUTPUT:

PARTH TEJANI 22
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-8
8. Write a program to implement the knapsack problem using greedy
algorithm.
// package PROFDAA.PR8;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
public class GA_knapsack {
public static void main(String[] args) {
int val[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int w = 50;
double ratio[][] = new double[val.length][2];
for (int i = 0; i < val.length; i++) {
ratio[i][0] = i;
ratio[i][1] = val[i] / (double) weight[i];
}
Arrays.sort(ratio, Comparator.comparingDouble(o -> o[1]));
int capacity = w;
int finalVal = 0;
for (int i = ratio.length - 1; i >= 0; i--) {
int idx = (int) ratio[i][0];
if (capacity >= weight[idx]) {
finalVal += val[idx];
capacity -= weight[idx];
} else {
finalVal += (ratio[i][1] * capacity);
capacity = 0;
break;
}
}

PARTH TEJANI 23
Design and Analysis of Algorithms CP 12202040601044

System.out.println("final value= " + finalVal);

}
}

 OUTPUT:

PARTH TEJANI 24
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-9
9. Write a program to implement making change problem using dynamic
programming.
import java.util.Arrays;
import java.util.Scanner;
public class DA_makingChangeDP {
public static void findMinCoinDP(int[] denomination, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;

for (int i = 1; i <= amount; i++) {

for (int coin : denomination) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
if (dp[amount] > amount) {
System.out.println("The amount cannot be made with given denominations.");
} else {
System.out.println("Minimum number of coins required: " + dp[amount]);
printCoinsUsed(denomination, dp, amount);
}
}
public static void printCoinsUsed(int[] denomination, int[] dp, int amount) {
System.out.println("Coins used to make the amount:");
int remainingAmount = amount;
while (remainingAmount > 0) {
for (int coin : denomination) {
if (remainingAmount >= coin && dp[remainingAmount] == dp[remainingAmount -
coin] + 1) {

PARTH TEJANI 25
Design and Analysis of Algorithms CP 12202040601044

System.out.println(coin);
remainingAmount -= coin;
break;
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] denomination = {1000, 500, 100, 50, 25, 10, 5, 1};
System.out.print("Enter the amount in Rupees: ");
int amount = scanner.nextInt();
findMinCoinDP(denomination, amount);
scanner.close();
}
}

 OUTPUT:

PARTH TEJANI 26
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-10
10. Write a program to implement the knapsack problem using dynamic
programming.
import java.util.Scanner;
public class DA_knapsackDP {
public static int knapsackDP(int[] val, int[] weight, int W) {
int n = val.length;
int[][] dp = new int[n + 1][W + 1]
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weight[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + val[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] val = { 60, 100, 120 };
int[] weight = { 10, 20, 30 };
int W = 50; // Maximum weight capacity of the knapsack
int maxValue = knapsackDP(val, weight, W);
System.out.println("Maximum value in knapsack = " + maxValue);
scanner.close();
}
}

 OUTPUT:

PARTH TEJANI 27
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-11
11. Write a program to implement Floyd’s algorithm for finding shortest path
using dynamic programming.
import java.util.Scanner;
public class DA_FloydWarshall {
final static int INF = 99999; // Infinity (used to represent no path)
public static void floydWarshall(int[][] graph, int n) {
int[][] dist = new int[n][n];
// Initialize the solution matrix same as input graph matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
// Dynamic programming approach
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printSolution(dist, n);
}
public static void printSolution(int[][] dist, int n) {
System.out.println("Shortest distances between every pair of vertices:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF) {

PARTH TEJANI 28
Design and Analysis of Algorithms CP 12202040601044

System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of vertices: ");
int n = scanner.nextInt();
int[][] graph = new int[n][n];
System.out.println("Enter the adjacency matrix (enter 99999 for no direct path):");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = scanner.nextInt();
}
}
floydWarshall(graph, n);
scanner.close();
}
}

 OUTPUT:

PARTH TEJANI 29
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-12
12. Write a program to implement chained matrix multiplication using
dynamic programming.
import java.util.Scanner;
public class DA_MatrixChainMultiplication {
public static int matrixChainOrder(int[] p, int n) {
int[][] dp = new int[n][n];
// dp[i][i] is 0 since only one matrix, so no cost of multiplication
for (int i = 1; i < n; i++) {
dp[i][i] = 0;
}
// L is chain length
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
}
}
}
}
return dp[1][n - 1]; // Minimum cost to multiply the full chain of matrices
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of matrices: ");
int n = scanner.nextInt();
int[] p = new int[n + 1];

PARTH TEJANI 30
Design and Analysis of Algorithms CP 12202040601044

System.out.println("Enter the dimensions of matrices:");

for (int i = 0; i <= n; i++) {
System.out.print("p[" + i + "] = ");
p[i] = scanner.nextInt();
}
int minMultiplications = matrixChainOrder(p, n + 1);
System.out.println("Minimum number of scalar multiplications: " + minMultiplications);
scanner.close();
}
}

 OUTPUT:

PARTH TEJANI 31
Design and Analysis of Algorithms CP 12202040601044

PRACTICAL-13
13. Write a program to implement longest common subsequence using
dynamic programming.
import java.util.Scanner;
public class DA_LongestCommonSubsequence {
public static int lcs(String X, String Y, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
// Building the dp matrix in bottom-up fashion
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0; // Initialize first row and column to 0
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1; // Match found
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Take maximum
}
}
}
return dp[m][n]; // The value in dp[m][n] contains the length of LCS
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the first string: ");
String X = scanner.nextLine();
System.out.print("Enter the second string: ");
String Y = scanner.nextLine();
int m = X.length();
int n = Y.length();
int lengthOfLCS = lcs(X, Y, m, n);

PARTH TEJANI 32
Design and Analysis of Algorithms CP 12202040601044

System.out.println("Length of the Longest Common Subsequence: " + lengthOfLCS);

scanner.close();
}
}

 OUTPUT:

PARTH TEJANI 33