PRACTICAL 1

1. Implement Merge sort algorithm in C/C++/Java.

/* C program for Merge Sort */
#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int
r)
{
int i, j, k;
int n1 = m - l +
1; int n2 = r - m;

/* create temp arrays

*/ int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[]

*/ for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray while (i < n1 &&
j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
} k+
+;
}
 /* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if

there are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of

the sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver code */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
return 0;
}
 PRACTICAL-2
2. Implement quick sort algorithm in C/C++/JAVA

#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot]) j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
 PRACTICAL-3

3. Implement Binary search in C/C++/Java.

#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid; if(end >=
beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right subarray
*/
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array int
val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val); if
(res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0
PRACTICAL-4
 4. Implement strassen’s matrix multiplication in C/C++/JAVA
/*
C code of two 2 by 2 matrix multiplication using Strassen's algorithm
*/ #include<stdio.h>
int main(){
int a[2][2], b[2][2], c[2][2], i, j;
int m1, m2, m3, m4 , m5, m6, m7;
printf("Enter the 4 elements of first matrix: "); for(i =
0;i < 2; i++)
for(j = 0;j < 2; j++)
scanf("%d", &a[i][j]);

printf("Enter the 4 elements of second matrix: "); for(i =

0; i < 2; i++)
for(j = 0;j < 2; j++)
scanf("%d", &b[i][j]);

printf("\nThe first matrix is\n");

for(i = 0; i < 2; i++){
printf("\n");
for(j = 0; j < 2; j++)
printf("%d\t", a[i][j]);
}

printf("\nThe second matrix is\n");

for(i = 0;i < 2; i++){
printf("\n");
for(j = 0;j < 2; j++)
printf("%d\t", b[i][j]);
}

m1= (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);

m2= (a[1][0] + a[1][1]) * b[0][0];
m3= a[0][0] * (b[0][1] - b[1][1]);
m4= a[1][1] * (b[1][0] - b[0][0]);
m5= (a[0][0] + a[0][1]) * b[1][1];
m6= (a[1][0] - a[0][0]) * (b[0][0]+b[0][1]);
m7= (a[0][1] - a[1][1]) * (b[1][0]+b[1][1]);

c[0][0] = m1 + m4- m5 + m7;

c[0][1] = m3 + m5;
c[1][0] = m2 + m4;
c[1][1] = m1 - m2 + m3 + m6;
printf("\nAfter multiplication using Strassen's algorithm \n");
for(i = 0; i < 2 ; i++){
printf("\n");
for(j = 0;j < 2; j++)
printf("%d\t", c[i][j]);

return 0;
}
 PRACTICAL-5
5. Implement the 8 queen problem in C/C++/Java
#include<stdio.h>
#include<math.h>

void queen(int row, int

p); int chess[8],count;

int main()/*from w w w . j ava2 s. c o m*/

{
int p = 8;
queen(1,p);
return 0;
}
void print(int p)
{
int i,j;
printf("\n\nThis is Solution no. %d:\n\n",++count);
for(i=1;i<=p;++i)
printf("\t%d",i);

for(i=1;i<=p;++i){ printf("\n\
n%d",i); for(j=1;j<=p;++j){
if(chess[i]==j)
printf("\tQ");
else
printf("\t-");
}
}
printf("\n\n\nThere are total 92 solutions for 8-queens problem.");
}

int place(int row,int column)

{
int i;
for(i=1;i<=row-1;++i)
{
if(chess[i]==column)
return 0;
else
if(abs(chess[i]-column)==abs(i-row))
return 0;
}
 return 1;
}

void queen(int row,int p)

{
int column;
for(column=1;column<=p;++column)
{
if(place(row,column))
{
chess[row]=column;
if(row==p)
print(p);
else
queen(row+1,p);
}
}
}
 PRACTICAL-6

6. Implement the sum of subsets problem in C/C++/Java

// A recursive solution for subset sum problem
#include <stdio.h>

// Returns true if there is a subset of set[] with sum equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum, then ignore it
if (set[n - 1] > sum)
return isSubsetSum(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 program to test above function

int main()
{
int set[] = { 3, 34, 4, 12, 5, 2 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (isSubsetSum(set, n, sum) == true)
printf("Found a subset with given sum");
else
printf("No subset with given sum");
return 0;
}
 PRACTICAL-7

7. Implement traveling salesman problem in C/C++/Java

#include<stdio.h>

int ary[10][10],completed[10],n,cost=0;

void takeInput()
{
int i,j;

printf("Enter the number of villages: ");

scanf("%d",&n);

printf("\nEnter the Cost Matrix\n");

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

{
printf("\nEnter Elements of Row: %d\n",i+1);
for( j=0;j < n;j++)
scanf("%d",&ary[i][j]);

completed[i]=0;
}

printf("\n\nThe cost list is:");

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

{
printf("\n");

for(j=0;j < n;j++) printf("\t

%d",ary[i][j]);
}
}

void mincost(int city)

{
int i,ncity;

completed[city]=1;
printf("%d--->",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=ary[city][ncity];

return;
}

mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;

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

{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}

if(min!=999)
cost+=kmin;

return nc;
}

int main()
{
takeInput();

printf("\n\nThe Path is:\n");

mincost(0); //passing 0 because starting vertex

printf("\n\nMinimum cost is %d\n ",cost);

return 0;
}
 PRACTICAL-8
8. Implement 0/1 knapsack problem in C/C++/JAVA
#include<stdio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int
n)
{
int i, w;
int K[n+1][W+1];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main()
{
int i, n, val[20], wt[20], W;

printf("Enter number of items:");

scanf("%d", &n);

printf("Enter value and weight of items:\n");

for(i = 0;i < n; ++i){
scanf("%d%d", &val[i], &wt[i]);
}

printf("Enter size of knapsack:");

scanf("%d", &W);

printf("%d", knapSack(W, wt, val, n));

return 0;
}
 PRACTICAL-9
9. Implement job sequencing with deadline
problem in C/C++/JAVA
#include <stdio.h>

#define MAX 100

typedef struct Job {

char id[5];
int deadline;
int profit;
} Job;
void jobSequencingWithDeadline(Job jobs[], int n);

int minValue(int x, int y) {

if(x < y) return x;
return y;
}

int main(void) {
//variables
int i, j;

//jobs with deadline and profit

Job jobs[5] = {
{"j1", 2, 60},
{"j2", 1, 100},
{"j3", 3, 20},
{"j4", 2, 40},
{"j5", 1, 20},
};

//temp
Job temp;

//number of jobs
int n = 5;

//sort the jobs profit wise in descending order

for(i = 1; i < n; i++) {
for(j = 0; j < n - i; j++) {
if(jobs[j+1].profit > jobs[j].profit) {
temp = jobs[j+1];
jobs[j+1] = jobs[j];
 jobs[j] = temp;
}
}
}

printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");

for(i = 0; i < n; i++) {
printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);
}
jobSequencingWithDeadline(jobs, n);

return 0;
}

void jobSequencingWithDeadline(Job jobs[], int n) {

//variables
int i, j, k, maxprofit;

//free time slots

int timeslot[MAX];

//filled time slots

int filledTimeSlot = 0;

//find max deadline value

int dmax = 0;
for(i = 0; i < n; i++) {
if(jobs[i].deadline > dmax) {
dmax = jobs[i].deadline;
}
}

//free time slots initially set to -1 [-1 denotes EMPTY]

for(i = 1; i <= dmax; i++) {
timeslot[i] = -1;
}

printf("dmax: %d\n", dmax);

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

k = minValue(dmax, jobs[i - 1].deadline);
while(k >= 1) {
if(timeslot[k] == -1) {
timeslot[k] = i-1;
filledTimeSlot++;
 break;
}
k--;
}

//if all time slots are filled then stop

if(filledTimeSlot == dmax) {
break;
}
}

//required jobs printf("\

nRequired Jobs: "); for(i =
1; i <= dmax; i++) {
printf("%s", jobs[timeslot[i]].id);

if(i < dmax) {

printf(" --> ");
}
}

//required profit
maxprofit = 0;
for(i = 1; i <= dmax; i++) {
maxprofit += jobs[timeslot[i]].profit;
}
printf("\nMax Profit: %d\n", maxprofit);
}
 PRACTICAL-10
10. Implement minimum cost spanning tree problem
in C/C++/JAVA.

#include<stdio.h> int
main()
{

int cost[10][10],visited[10]={0},i,j,n,no_e=1,min,a,b,min_cost=0; printf("Enter number of nodes

");
scanf("%d",&n);

printf("Enter cost in form of adjacency matrix\n");

//input graph
for(i=1;i<=n;i++)
{

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

scanf("%d",&cost[i][j]);

// cost is 0 then initialize it by maximum value if(cost[i][j]==0)

cost[i][j]=1000;

// logic for finding minimum cost spanning tree

visited[1]=1; // visited first node while(no_e<n)
{

min=1000;
// in each cycle find minimum cost for(i=1;i<=n;i++)

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

if(cost[i][j]<min)

{
 if(visited[i]!=0)

min=cost[i][j]; a=i;
b=j;

//if node is not visited

if(visited[b]==0)
{

printf("\n%d to %d cost=%d",a,b,min);
min_cost=min_cost+min;
no_e++;

visited[b]=1;

// initialize with maximum value you can also use any other value cost[a][b]=cost[b][a]=1000;
}

printf("\nminimum weight is %d",min_cost); return 0;

}
 PRACTICAL-11
11. Implement single source shortest path problem in
C/C++/JAVA.
#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++) scanf("%d",&G[i][j]);
printf("\nEnter the starting node:");
scanf("%d",&u);
dijkstra(G,n,u);
return 0;

void dijkstra(int G[MAX][MAX],int n,int startnode)

{

int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
//pred[] stores the predecessor of each node
//count gives the number of nodes seen so far
//create the cost matrix

for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0)

cost[i][j]=INFINITY;
else cost[i][j]=G[i]
[j];
//initialize pred[],distance[] and
visited[] for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
 visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=INFINITY;
//nextnode gives the node at minimum distance
for(i=0;i<n;i++) if(distance[i]<mindistance&&!
visited[i])
{
mindistance=distance[i];
nextnode=i;
}
//check if a better path exists through nextnode
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])

{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}

//print the path and distance of each

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

if(i!=startnode)
{
printf("\nDistance of node%d=%d",i,distance[i]); printf("\nPath=
%d",i);
j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
}
}