DAA-LAB Manual

https://www.youtube.com/watch?v=FbOfNoXrevY

Part A:

Write a program to sort a list of N elements using Selection Sort Technique.

import java.util.Scanner;
import java.util.Random;

public class selection_sort {

public static void main(String args[])

{
int i, j, temp;

System.out.println("Enter array size");

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] arr = new int[500];

Random generator = new Random();

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

arr[i] = generator.nextInt(100);
}

System.out.println("Array before sorting");

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

System.out.println(arr[i] + " ");
}

long startTime = System.nanoTime();

for (i = 0; i <= n - 2; i++)

 {
int min = i;

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

if (arr[j] < arr[min])

min = j;

temp = arr[i];

arr[i] = arr[min];

arr[min] = temp;

long stopTime = System.nanoTime();

long elapseTime = (stopTime - startTime);

System.out.println("Time taken to sort array is:" + elapseTime + "nanoseconds");

System.out.println("Sorted array is");

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

System.out.println(arr[i]);
System.out.println("Time taken to sort array is:" + elapseTime + "nanoseconds");
}
}
Output:

Part A: Write a program to find minimum and maximum value in an array using
divide and conquer.
import java.util.Scanner;

public class MaxMinDC {

static Scanner sc = new Scanner(System.in);

static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
static int a[];
static int size;

static void MaxMin(int i, int j)

{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1){
if(a[i] < a[j]){
max = a[j];
min = a[i];
}
else{
max = a[i];
min = a[j];
}
}

else{
mid = (i+j)/2;
MaxMin(i, mid);

max1 = max;
min1 = min;
MaxMin(mid+1, j);
if(max < max1) max = max1;//updating here
if(min > min1) min = min1;
}
}
}

public static void inputArray()

{
for(int i=0; i< size; i++){
a[i] = sc.nextInt();
}
}

public static void main(String[] args) {

System.out.println("Enter the size of the array: ");
size = sc.nextInt();
a = new int[size];
 inputArray();
MaxMin(0, size-1);
System.out.println("Max value: "+max+"\n Min value: "+min);
}

OutPut:

A2: Implement Travelling Sales Person problem using Dynamic

programming.
import java.util.Scanner;
public class Tsp
{
static int cost[][];
public int tsp(int[] path,int start,int n)
{
int i,j,k,ccost;
int[] mintour=new int[n+1];
int[] temp=new int[n+1];
if(start==n-1)
return cost[path[n-1]][path[n]]+cost[path[n]][1];
int mincost=999;
for(i=start+1;i<=n;i++)
{
for(j=1;j<=n;j++)
temp[j]=path[j];
temp[start+1]=path[i];
temp[i]=path[start+1];
if(cost[path[start]][path[i]]+(ccost=tsp(temp,start+1,n))<mincost)
{
mincost=cost[path[start]][path[i]]+ccost;
for(k=1;k<=n;k++)
mintour[k]=temp[k];
}
} fo
r(i=1;i<=n;i++)
path[i]=mintour[i];
return mincost;

}
public static void main(String[] args)
{
int mincost,n,i,j;
Scanner s = new Scanner(System.in);
System.out.println("enter the no of cities");
n=s.nextInt();
int path[] =new int[n+1];
cost = new int[n+1][n+1];
System.out.println("Enter the cost matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=s.nextInt();
for(i=1;i<=n;i++)
path[i]=i;
Tsp obj = new Tsp();
mincost=obj.tsp(path,1,n);
System.out.println("tsp tour");
for(i=1;i<=n;i++)
System.out.print(path[i] + "--->");
System.out.println("1");
System.out.println("Tourcost=" + mincost);
}
}

OUTPUT:
Enter the no of cities
4

Enter the cost matrix

999 1 3 6
1 999 2 3
3 2 999 1
6 3 1 999
tsp tour
1--->2--->4--->3--->1
Tourcost = 8

```````````````````````````````````````````

A3: 6. Implement in Java, the 0/1 Knapsack problem using

(a) Dynamic Programming method
import java.util.Scanner;
class DKnapsack
{
int n;
int c;
int p[];
int w[];
int v[][];
public DKnapsack(int n, int c, int[] p, int[] w)
{
super();
this.n = n;
this.c = c;
this.p = p;
this.w = w;
this.v = new int[n + 1][c + 1];
}

void compute()
{
for ( int i = 0; i <= n; ++ i)
{
for ( int j = 0; j <= c; ++ j)
{
if ( i == 0 || j == 0 )
{
v[i][j] = 0;
}

else if ( j - w[i] >= 0 )

{
v[i][j] = max ( v[i - 1][j], p[i] + v[i - 1][j - w[i]]);
}

else if ( j - w[i] < 0 )

{
v[i][j] = v[i - 1][j];
}
}
}

System.out.println("Optimal Solution: " + v[n][c]);

traceback();
}

void traceback()
{
System.out.println("The objects picked up into knapsack are:");
int i = n;
int j = c;
while( i > 0)
{
if(v[i][j] != v[i-1][j])
{
System.out.print(i + " ");
j = j - w[i];
i--;
}

else
{
i--;
}
}
}

private int max(int i, int j)

{
if ( i > j ) return i;
else return j;
}
}

public class KpDynamic

{
public static void main(String[] args)
{
int n;
int c;
Scanner input = new Scanner(System.in);
System.out.println("Enter number of objects");
n = input.nextInt();
int[] p = new int[n+1];
int[] w = new int[n+1];
int i;

System.out.println("Enter capacity of Knapsack");

c = input.nextInt();
System.out.println("Enter profit for each " + n + " objects");
for ( i = 1; i <= n; i ++)
p[i] = input.nextInt();
System.out.println("Enter weight for each " + n + " objects");
for ( i = 1; i <= n; i ++)
w[i] = input.nextInt();
DKnapsack dk = new DKnapsack(n, c, p, w);
dk.compute();
}
}

OUTPUT:
Enter number of objects
5

Enter capacity of Knapsack

20

Enter profit for each 5 objects

3

10
Enter weight for each 5 objects
2

Optimal Solution: 26
The objects picked up into knapsack are:
5431

A4: (b) Greedy method.

import java.util.Scanner;
class GKnapsack
{
int n;
double c;
double p[];
double w[];
public GKnapsack(int n, double c, double[] p, double[] w)
{
super();
this.n = n;
this.c = c;
this.p = p;
this.w = w;
}

void compute()
{
int i;
double[] x= new double[n+1];
for (i=0; i<n; i++)
{
x[i] = 0.0;
}d
ouble rc = c;
for(i=0; i<n; i++)
{
if(w[i] > rc) break;
x[i] = 1;
rc = rc - w[i];
} if
(i<=n)
{
x[i] = rc/w[i];
}

double netProfit = 0.0;

for ( i = 0; i < n; ++ i)
{
if ( x[i] > 0.0)
{
netProfit = netProfit + x[i] * p[i];
}
}S
ystem.out.println("Net Profit: " + netProfit);
System.out.println("The objects picked up into knapsack are:");
for ( i = 0; i < n; ++ i)
{
System.out.println(x[i] + " ");
}
}
}

public class KpGreedy

{
public static void main(String[] args)
{
int n;
double c;
Scanner input = new Scanner(System.in);
System.out.println("Enter number of objects");
n = input.nextInt();
double[] p = new double[n+1];
double[] w = new double[n+1];
int i;
System.out.println("Enter capacity of Knapsack");
c = input.nextDouble();
System.out.println("Enter profit for each " + n + " objects");
for ( i = 0; i < n; i ++)
p[i] = input.nextDouble();
System.out.println("Enter weight for each " + n + " objects");

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

w[i] = input.nextDouble();
GKnapsack gk = new GKnapsack(n, c, p, w);
gk.compute();
}
}

OUTPUT:
Enter number of objects
7

Enter capacity of Knapsack

15
Enter profit for each 7 objects
6
10
18
15
3

Enter weight for each 7 objects

1

4
5

Net Profit: 55.333333333333336

The objects picked up into knapsack are:
1.0
1.0
1.0
1.0
1.0
0.6666666666666666
0.0

A6: Write a program to find minimum and maximum value in an array using
divide and conquer.
import java.util.Scanner;

public class MaxMinDC {

static Scanner sc = new Scanner(System.in);

static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
static int a[];
static int size;

static void MaxMin(int i, int j)

{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1){
if(a[i] < a[j]){
max = a[j];
min = a[i];
}
else{
max = a[i];
min = a[j];
}
}

else{
mid = (i+j)/2;
MaxMin(i, mid);

max1 = max;
min1 = min;
MaxMin(mid+1, j);
if(max < max1) max = max1;//updating here
if(min > min1) min = min1;
}
}
}

public static void inputArray()

{
for(int i=0; i< size; i++){
a[i] = sc.nextInt();
}
}

public static void main(String[] args) {

System.out.println("Enter the size of the array: ");
size = sc.nextInt();
a = new int[size];
inputArray();
MaxMin(0, size-1);
System.out.println("Max value: "+max+"\n Min value: "+min);
}
}
====================== ===

EXPERIMENT 4
PROGRAM STATEMENT
Sort a given set of n integer elements using Quick Sort method and compute its time complexity.
Run the program for varied values of n > 5000 and record the time taken to sort. Plot a graph of
the time taken versus n on graph sheet. The elements can be read from a file or can be generated
using the random number generator. Demonstrate using Java how the divide- and-conquer
method works along with its time complexity analysis: worst case, average case and best case.

CONCEPT
Divide and Conquer: In divide and conquer approach, the problem in hand, is divided into
smaller sub-problems and then each problem is solved independently. When we keep on dividing
the subproblems into even smaller sub-problems, we may eventually reach a stage where no
more division is possible. Those "atomic" smallest possible sub-problem (fractions) are solved.
The solution of all sub-problems is finally merged in order to obtain the solution of an original
problem.

Broadly, we can understand divide-and-conquer approach in a three-step process.

Divide/Break: This step involves breaking the problem into smaller sub-problems. Subproblems
should represent a part of the original problem. This step generally takes a recursive approach to
divide the problem until no sub-problem is further divisible. At this stage, sub problems become
atomic in nature but still represent some part of the actual problem.
Conquer/Solve: This step receives a lot of smaller sub-problems to be solved. Generally, at this
level, the problems are considered 'solved' on their own.
Merge/Combine: When the smaller sub-problems are solved, this stage recursively combines
them until they formulate a solution of the original problem. This algorithmic approach works
recursively and conquer & merge steps works so close that they appear as one.

The following computer algorithms are based on divide-and-conquer programming approach .

Merge Sort
Quick Sort Method:
Quick Sort divides the array according to the value of elements. It rearranges elements of a given array
A[0..n-1] to achieve its partition, where the elements before position s are smaller than or equal to A[s]
and all the elements after position s are greater than or equal to A[s].

A[0]…A[s-1] A[s] A[s+1]…A[n-1]

All are <=A[s] all are >=A[s]

Algorithm : QUICKSORT(a[l..r]) //Sorts a subarray by quicksort

//Input: A subarray A[l..r] of A[0..n-1],defined by its left and right indices l and r
//Output: Subarray A[l..r] sorted in nondecreasing order
{
if l<r
{}
}
s← Partition(A[l..r]) //s is a split position
QUICKSORT(A[l..s-1])
QUICKSORT(A[s+1..r])
Algorithm :
Partition(A[l..r])
//Partition a subarray by using its first element as its pivot
//Input:A subarray A[l..r] of A[0..n-1],defined by its left and right indices l and r (l<r)
//Output:A partition of A[l..r],with the split position returned as this function’s value
{
Design & Analysis of Algorithm Lab Manual 2020
Dept of ISE, SJCIT Page 45
p ← A[l]
i ← l; j ← r+1 repeat
{
repeat i ← i+1 until A[i] >=p
repeat j ← j-1 until A[j] <=p
swap(A[i],A[j]) } until i>=j
swap(A[i],A[j]) // undo last swap when i>=j
swap(A[l],A[j]) return j
}
Complexity: Cbest (n) =2 Cbest (n/2) +n for n>1
Cbest (1) =0 Cworst (n) (n2)
Cavg (n) ≈ 1.38nlog2n
PROGRAM
Program :
Sort a given set of n integer elements using Quick Sort method and compute its
time complexity. Run the program for varied values of n > 5000 and record the
time taken to sort. Plot a graph of the time taken versus n on graph sheet. The
elements can be read from a file or can be generated using the random number
generator. Demonstrate using Java how the divide-and-conquer method works
along with its time complexity analysis:
worst case, average case and best case.