SNS COLLEGE OF ENGINEERING
KURUMBAPALAYAM (Po), COIMBATORE – 641 107
AN AUTONOMOUS INSTITUTION
Accredited by NBA – AICTE and Accredited by NAAC – UGC with ‘A’
Grade Approved by AICTE, New Delhi & Affiliated to Anna
University, Chennai.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(INTERNET OF THINGS AND CYBER SECURITY INCLUDING
BLOCKCHAIN TECHNOLOGY)
19503-Design and Analysis of Algorithms
Practical Record
Name :………………………………………………………..
Register Number :………………………………………………………..
Class :………………………………………………………..
Semester :………………………………………………………..
SNS COLLEGE OF ENGINEERING
KURUMBAPALAYAM (Po), COIMBATORE – 641 107
AN AUTONOMOUS INSTITUTION
Accredited by NBA – AICTE and Accredited by NAAC – UGC with ‘A’
Grade Approved by AICTE, New Delhi & Affiliated to Anna
University, Chennai.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(INTERNET OF THINGS AND CYBER SECURITY INCLUDING
BLOCKCHAIN TECHNOLOGY)
Name :………………………………………………………..
Class / Semester :………………………………………………………..
Register Number :
Certified that this is the Bonafide record of work done by the above student
for the 19503-Design and Analysis of Algorithms LABORATORY during
the year 2024 - 2025.
Signature of Faculty Head of the Department
Submitted for practical examination held on…………………….
Internal Examiner External Examiner
LIST OF CONTENTS
S.NO Date Experiments page Marks Sign
1. Find a subset of a given set S={S1,S2,…….Sn} of n
positive integers whose sum is equal to a given
positive integer d.
2(a) Sort a given set of elements using the quick sort
method and determine the time required to sort
the elements.
2(b) Implement merge sort algorithm to sort a given
set of elemnets and determine the time required
to sort the element
3. Implement any scheme to find the optimal
solution for the Travelling sales person problem .
4 Implement 0/1 Knapsack problem using Dynamic
Programming
5. Implement N Queen ‘s Problem using Back
Tracking
PERFORMANCE
RECORD
VIVA-VOCE
TOTAL
SIGNATORE OF THE FACULTY
Ex.No:
Date: SUM OF SUB SETS PROBLEM
AIM:
To write a java program and find the subset of a given set S = {sl, s2,.....,sn} of n
positive integers whose sum is equal to a given positive integer d.
SOURCE CODE:
class GFG {
// Returns true if there is a subset
// of set[] with sum equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum)
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than
// sum, then ignore it
if (set[n - 1] > sum)
return is SubsetSum(set, n - 1, sum);
/* else, check if sum can be obtained
by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n - 1, sum)
|| isSubsetSum(set, n - 1, sum - set[n - 1]);
/* Driver code */
public static void main(String args[])
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset" + " with given sum");
else
System.out.println("No subset with" + " given sum");
}
OUTPUT:
Sorted a Found a subset with given sum
RESULT:
Thus to write a java program and find the subset of a given set S = {sl, s2,.....,sn} of n
positive integers whose sum is equal to a given positive integer d is executed
successfully
Ex.No: Sorting
Date:
AIM
To write a java program and find the Sort a given set of elements using the Quick sort
method and determine the time required to sort the elements.
SOURCE CODE:
// Java implementation of QuickSort
import java.io.*;
class GFG {
// A utility function to swap two elements
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)
{
// pivot
int pivot = arr[high];
// Index of smaller element and
// indicates the right position
// of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller
// than the pivot
if (arr[j] < pivot) {
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
static void quickSort(int[] arr, int low, int high)
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
// Function to print an array
static void printArray(int[] arr, int size)
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
// Driver Code
public static void main(String[] args)
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
OUTPUT:
Sorted array:
1 5 7 8 9 10
RESULT:
Thus to find the Sort a given set of elements using the Quick sort
method and determine the time required to sort the elements is executed successfully.
Ex.no:2 (B) SORTING
Date:
AIM:
To write a java program to implement merge sort algorithm to sort a given set of
elements and determine the time required to sort the elements.
SOURCE CODE:
class GFG
static int tsp(int[][] graph, boolean[] v,
int currPos, int n,
int count, int cost, int ans)
if (count == n && graph[currPos][0] > 0)
ans = Math.min(ans, cost + graph[currPos][0]);
return ans;
for (int i = 0; i < n; i++)
{
if (v[i] == false && graph[currPos][i] > 0)
v[i] = true;
ans = tsp(graph, v, i, n, count + 1,
cost + graph[currPos][i], ans);
v[i] = false;
return ans;
public static void main(String[] args)
int n = 4;
int[][] graph = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
boolean[] v = new boolean[n];
v[0] = true;
int ans = Integer.MAX_VALUE;
ans = tsp(graph, v, 0, n, 1, 0, ans);
System.out.println(ans);
OUTPUT:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
RESULT:
Thus to find the implement merge sort algorithm to sort a given set of
elements and determine the time required to sort the elements is executed successfully.
Ex.no: TRAVELLING SALES PERSON PROBLEM
Date:
AIM:
To Write a java program to Implement travelling sales person problem.
SOURCE CODE:
class GFG
static int tsp(int[][] graph, boolean[] v,
int currPos, int n,
int count, int cost, int ans)
if (count == n && graph[currPos][0] > 0)
ans = Math.min(ans, cost + graph[currPos][0]);
return ans;
for (int i = 0; i < n; i++)
if (v[i] == false && graph[currPos][i] > 0)
v[i] = true;
ans = tsp(graph, v, i, n, count + 1,
cost + graph[currPos][i], ans);
v[i] = false;
return ans;
public static void main(String[] args)
int n = 4;
int[][] graph = {{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}};
boolean[] v = new boolean[n];
v[0] = true;
int ans = Integer.MAX_VALUE;
ans = tsp(graph, v, 0, n, 1, 0, ans);
System.out.println(ans);
OUTPUT:
80
RESULT:
Thus, the java program was Implemented travelling sales person problem and output
was executed successfully.
Ex.no:4 0/1KNAPSACK PROBLEM
Date:
AIM:
Write a java program to Implement 0/1 Knapsack problem using Dynamic
Programming.
SOURCE CODE:
class Knapsack {
static int max(int a, int b)
return (a > b) ? a : b;
static int knapSack(int W, int wt[], int val[], int n)
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n - 1]
+ knapSack(W - wt[n - 1], wt,
val, n - 1),
knapSack(W, wt, val, n - 1));
}
public static void main(String args[])
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
OUTPUT:
220
RESULT:
Thus, the java program was Implement 0/1 Knapsack problem using Dynamic
Programming and output was verified successfully.
Ex.No: N QUEENS PROBLEM
Date:
AIM:
Write a java program to implement N Queen's problem using Back Tracking
SOURCE CODE:
public class NQueenProblem {
final int N = 4;
void printSolution(int board[][])
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
boolean isSafe(int board[][], int row, int col)
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
boolean solveNQUtil(int board[][], int col)
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1) == true)
return true;
board[i][col] = 0;
}
return false;
boolean solveNQ()
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
System.out.print("Solution does not exist");
return false;
printSolution(board);
return true;
public static void main(String args[])
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
OUTPUT:
0010
1000
0001
0100
RESULT:
Thus, the java program was implemented for N Queen's problem using Back Tracking
and output was executed successfully.
