Daa Record

PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF COMPUTER SCIENCE AND BUSINESS SYSTEMS

REGISTER NO:211421244088
EX NO:1(A)
IMPLEMENTATION AND TIME ANALYSIS OF FACTORIAL USING
ITERATIVE METHOD
PROGRAM:
#include<stdio.h>
#include<conio.h>
void main()
{
int i,fact=1,n;
clrscr();
printf("Enter positive number:");
scanf("%d",&num);
for(i=1;i<=n;i++)
{
fact=fact*i;
}
printf("Factorial of %d is %d",n,fact);
getch();
}
OUTPUT:
Enter a positive integer: 6
Factorial of 6 is 720
RESULT:
EX NO:1(B)
IMPLEMENTATION AND TIME ANALYSIS OF FACTORIAL USING
RECURSIVE METHOD
PROGRAM:
#include<stdio.h>
#include<conio.h>
int factorial(int n);
void main()
{
int n,fact;
clrscr();
printf("Enter number");
scanf("%d",&n);
fact=factorial(n);
printf("Factorial of %d is %d",n,fact);
getch();
}
int factorial(int n)
{
if(n==0)
return 1;
else
return n*factorial(n-1);
}
OUTPUT:
Enter a positive integer: 5
Factorial of 5 is 120
RESULT:
EX NO:1(C)
IMPLEMENTATION AND TIME ANALYSIS OF GCD USING

ITERATIVE METHOD
PROGRAM:
#include<stdio.h>
#include<conio.h>
void main()
{
int n1,n2,GCD,i;
clrscr();
printf("Enter two numbers:");
scanf("%d%d",&n1,&n2);
for(i=1;i<=n1 && i<=n2;++i)
{
if(n1%i==0 && n2%i==0)
GCD=i;
}
printf("GCD of %d and %d is %d",n1,n2,GCD);
getch();
}
}
OUTPUT:
Enter two numbers:60 24
GCD of 60 and 24 is 12
RESULT:
EX NO:1(C)
IMPLEMENTATION AND TIME ANALYSIS OF GCD USING

RECURSIVE METHOD
PROGRAM:
#include<stdio.h>
#include<conio.h>
int gcd(int a,int b)
if (b!=0)
return gcd(b,a%b);
else
return a;
int main()
int a,b;
clrscr();
printf(“enter two numbers:”);
scanf(“%d%d”,&a,&b);
printf(“GCD of %d and %d is %d”,a,b,gcd(a,b));
getch();
return 0;
}
OUTPUT:
Enter two numbers:15 10
GCD of 15 and 10 is 5
RESULT:
EX NO:2(A)
IMPLEMENTATION AND TIME ANALYSIS OF LINEAR SEARCH

PROGRAM:
#include<stdio.h.>
void main()
int n,s,a[10],k=0,i,c;
printf(“enter the no.of.elements:”);
for(i=0;i<n;i++)
printf(“a[%d]=”,i);
scanf(%d”,&a[i]);
printf(“enter the search element:”);
scanf(“%d”,&s);
for(i=0;i<n;i++)
if(a[i]==s)
c=i;
k++;
if(k==0)
printf(“elements %d is not present”,search);
else
printf(“element %d is present in %d location “,s,c);
OUTPUT:
enter the no.of.elements:4
enter the elements:11 10 12 19
enter element to be searched:10
element present at location 1
RESULT:
EX NO:2(B)
IMPLEMENTATION AND TIME ANALYSIS OF BINARY SEARCH
PROGRAM:
#inlcude<stdio.h>
void main()
int first,last,mid,size,i,element,list[100];
printf(“enter the size of the list”);
scanf(“%d”,&size);
printf(“enter elements:”);
for(i=0;i<size;i++)
scanf(“%d”,&list[i]);
printf(“enter the search element”);
scanf(“%d”,element);
first=0;
last=size-1;
mid=(first+last)/2;
while(first<=last)
if(list[mid]<element)
first=mid+1;
else if(list[mid]=element)
printf(“element found at %d”,mid);
break;
else
last=mid-1;
mid=(first+last)/2;
if(first>last)
printf(“element not found”);
OUTPUT:
enter the size of array:5
enter elements: 10 11 17 12 19
enter the element to be searched:11
the elements found at the position 1
RESULT:
EX NO:3(A)
IMPLEMENTATION AND TIME ANALYSIS OF SEARCHING

ALGORITHM –MERGE SORT
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void merge(int arr[], int l,int m, int r)
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[20], R[20];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
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++;
k++;}
while (j < n2)
{arr[k] = R[j];
j++;
k++;
void mergeSort(int arr[],int l, int r)
if (l < r)
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}}
void printArray(int A[], int size)

int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
int main()
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
clrscr();
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
getch();
return 0;
OUTPUT:
Enter the size of the array:5
Enter the array elements :12 48 43 -1 3
Sorted elements are:
-1 3 12 43 48
RESULT:
EX NO:3(A)
IMPLEMENTATION AND TIME ANALYSIS OF SEARCHING

ALGORITHM –QUICK SORT
PROGRAM:
#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
int i;
for(i = 0;i < count-1;i++) {
printf("=");
printf("=\n");
void display() {
int i;
printf("[");
for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
printf("]\n");
void swap(int num1, int num2) {
int temp = intArray[num1];
int Array[num1] = intArray[num2];
int Array[num2] = temp;

int partition(int left, int right, int pivot) {
int leftPointer = left -1;
int rightPointer = right;
while(true) {
while(intArray[++leftPointer] < pivot) {
while(rightPointer > 0 && intArray[--rightPointer] > pivot) {
if(leftPointer >= rightPointer) {
break;
else {
printf(" item swapped :%d,%d\n", intArray[leftPointer],intArray[rightPointer]);
swap(leftPointer,rightPointer);
printf(" pivot swapped :%d,%d\n", intArray[leftPointer],intArray[right]);
swap(leftPointer,right);
printf("Updated Array: ");
display();
return leftPointer;
void quickSort(int left, int right) {
if(right-left <= 0) {
return;
} else {
int pivot = intArray[right];
int partitionPoint = partition(left, right, pivot);
quickSort(left,partitionPoint-1);
quickSort(partitionPoint+1,right);
int main() {
printf("Input Array: ");
display();
printline(50);
quickSort(0,MAX-1);
printf("Output Array: ");
display();
OUTPUT:
Enter the size of the array:4
Enter the array elements :12 5 6 7
Sorted elements are:
5 6 7 12
RESULT:
EX NO:4
IMPLEMENTATION AND TIME ANALYSIS OF KNAPSACK

ALGORITHM
PROGRAM:
#include<stdio.h>
#include<conio.h>
int max(int a,int b)
{
return (a>b)?a:b;
}
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));
}
void main()
{
int profit[50],weight[50];
int w,n,i,result;
clrscr();
printf("enter the no.of items:");
scanf("%d",&n);
printf("enter the knapsack capacity:");
scanf("%d",&w);
printf("enter the weight of items:\n");
for(i=0;i<n;i++)
scanf("%d",&weight[i]);
printf("enter the values of items:\n");
for(i=0;i<n;i++)
scanf("%d",&profit[i]);
printf("the optimal solution is:%d",knapsack(w,weight,profit,n));
getch();
}
OUTPUT:
enter the no.of.items:3
enter the knapsack capacity:50
enter the weight of items:
10
20
30
enter the values:
60
100
120
the optimal solution is:220
RESULT:
EX NO:5(A)
IMPLEMENTATION AND TIME ANALYSIS OF PRIM’S ALGORITHM
PROGRAM:
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
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)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
getch();
}
OUTPUT:
enter the number of nodes:6
enter the adjacency matrix:
031600
305030
150564
605002
036006
004260
edge 1: (1 3) cost:1
minimum cost:13
RESULT:
EX NO:5(B)
IMPLEMENTATION AND TIME ANALYSIS OF KRUSKAL’S

ALGORITHM
PROGRAM:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
int find(int);
int uni(int, int);
void main()
{
printf("Kruskal's algorithm in C\n");
printf("========================\n");
printf("Enter the no. of vertices:\n");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix:\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
printf("The 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))
{
printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("\nMinimum cost = %d\n", mincost);
getch();
}
int find(int i)
{
while (parent[i])
i = parent[i];
return i;
}
int uni(int i, int j)
{
if (i != j)
{
parent[j] = i;
return 1;
}
return 0;
}
OUTPUT:
Kruskal’s algorithm in c
Enter the no. of vertices:
5
Enter the cost adjacency matrix:
04000
00210
00008
50000
0 0 0 10 0
The edges of Minimum Cost Spanning Tree are
1 edge (2,4) =1
2 edge (2,3) =2
3 edge (1,2) =4
4 edge (3,5) =8
Minimum cost = 15
RESULT:
EX NO:6
PRACTICE ITERATIVE IMPROVEMENT STRATEGIES FOR STABLE

MARRIAGE PROBLEM
PROGRAM:
#include <stdio.h>
int prefers(int man, int woman1, int woman2, int preference[][10])
{
for (int i = 0; i < 10; i++) {
if (preference[man][i] == woman1) {
return 1;
}
if (preference[man][i] == woman2) {
return 0;
}
}
}
void stableMarriage(int n, int preference[][10])
{
int matching[10];
int engaged[10];
for (int i = 0; i < n; i++) {
matching[i] = -1;
engaged[i] = 0;
}
int count = 0;
while (count < n) {
int man;
for (man = 0; man < n; man++) {
if (engaged[man] == 0) {
break;
}
}
for (int i = 0; i < n && engaged[man] == 0; i++) {
int woman = preference[man][i];
if (matching[woman] == -1) {
matching[woman] = man;
engaged[man] = 1;
count++;
}
else
{
int otherMan = matching[woman];
if (prefers(woman, man, otherMan, preference)) {
matching[woman] = man;
engaged[man] = 1;
engaged[otherMan] = 0;
}
}
}
}
printf("Matching:\n");
for (int i = 0; i < n; i++) {
printf("Man %d is engaged to Woman %d\n", matching[i], i);
}
}
int main()
{
int n;
printf("Enter the number of men/women (maximum 10): ");

scanf("%d", &n);
int preference[10][10];
printf("Enter the preference list of men and women (in order of preference, separated by
spaces):\n");
for (int i = 0; i < n; i++) {
printf("Man %d: ", i);
for (int j = 0; j < n; j++) {
scanf("%d", &preference[i][j]);
}
}
stableMarriage(n, preference);
return 0;
}
OUTPUT:
Enter the number of men/women (maximum 10): 4
Enter the preference list of men and women (in order of preference, separated by spaces):
Man 0: 3 2 1 0
Man 1: 0 1 2 3
Man 2: 2 1 3 0
Man 3: 3 0 1 2
Matching:
Man 1 is engaged to Woman 0
RESULT:
EX NO:8
DEMONSTRATION OF GRAPH COLORING USING BACKTRACKING
PROGRAM:
#include <stdio.h>
#include <string.h>
#define MAX_NODES 10
int n;
int m;
int graph[MAX_NODES][MAX_NODES];
char color[MAX_NODES][20];
int canColor(int node, char *c)
int i;
for (i = 0; i < n; i++) {
if (graph[node][i] && strcmp(color[i], c) == 0) {
return 0;
return 1;
int colorGraph(int node)
char c[20];
int i;
if (node == n) {
return 1;
for (i = 0; i < m; i++) {
strcpy(c, color[i]);
if (canColor(node, c)) {
strcpy(color[node], c);
if (colorGraph(node + 1)) {
return 1;
strcpy(color[node], "");
return 0;
int main()
int i;
n = 5;
m = 3;
graph[0][1] = graph[1][0] = 1;
graph[0][2] = graph[2][0] = 1;
graph[1][2] = graph[2][1] = 1;
graph[1][3] = graph[3][1] = 1;
graph[2][3] = graph[3][2] = 1;
graph[3][4] = graph[4][3] = 1;
strcpy(color[0], "red");
strcpy(color[1], "blue");
strcpy(color[2], "green");
if (colorGraph(0)) {
printf("The graph can be colored with %d colors as follows:\n", m);
for (i = 0; i < n; i++) {
printf("Node %d: Color %s\n", i, color[i]);
} else {
printf("The graph cannot be colored with %d colors.\n", m);
return 0;
OUTPUT:
The graph can be colored with 3 colors as follows:
Node 0: Color red
Node 1: Color blue
Node 2: Color green
Node 3: Color red
Node 4: Color blue
RESULT:
EX NO:9
DEMONSTRATE KNAPSACK PROBLEM USING BRANCH AND BOUND

TECHNIQUE
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#define MAX_ITEMS 100
#define MAX_WEIGHT 1000
typedef struct {
int value;
int weight;
} item_t;
int read_items(item_t *items, int max_items) {
int n = 0;
while (scanf("%d %d", &items[n].value, &items[n].weight) == 2) {
n++;
if (n >= max_items) {
break;
}
}
return n;
}
int bound(item_t *items, int n, int capacity, int level, int value, int weight)
{
int i;
int bound = value;
for (i = level; i < n && weight + items[i].weight <= capacity; i++) {
weight += items[i].weight;
bound += items[i].value;
}
if (i < n) {
bound += (capacity - weight) * items[i].value / items[i].weight;
}
return bound;
}
void search(item_t *items, int n, int capacity, int level, int value, int
weight, int *best_value) {
if (weight > capacity) {
return;
}
if (level == n) {
if (value > *best_value) {
*best_value = value;
}
return;
}
if (value + bound(items, n, capacity, level, value, weight) <= *best_value) {
return;
}
search(items, n, capacity, level + 1, value, weight, best_value);
search(items, n, capacity, level + 1, value + items[level].value, weight + items[level].weight,
best_value);
}
int main() {
int capacity, n, best_value;
item_t items[MAX_ITEMS];
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);
printf("Enter the items in the format (value weight), terminated by EOF:\n");

n = read_items(items, MAX_ITEMS);
best_value = 0;
search(items, n, capacity, 0, 0, 0, &best_value);
printf("The maximum value is %d.\n", best_value);
return 0;
}
OUTPUT:
Enter the capacity of the knapsack: 5

Enter the items in the format (value weight), terminated by EOF:
12 3
62
44
21
EOF
The maximum value is 18.
RESULT:
EX NO:10
DEMONSTRATE TRAVELLING SALESMAN PROBLEM USING BRANCH AND

BOUND TECHNIQUE
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 10
int n, cost[MAX_N][MAX_N], min_cost = INT_MAX;
int visited[MAX_N] = {0}, path[MAX_N];
void tsp(int pos, int curr_cost, int lower_bound) {
if (pos == n) {
if (curr_cost + cost[path[pos-1]][path[0]] < min_cost) {
min_cost = curr_cost + cost[path[pos-1]][path[0]];
}
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int new_lb = lower_bound + cost[path[pos-1]][i];
if (new_lb < min_cost) {
int old_lb = lower_bound;
lower_bound = new_lb;
curr_cost += cost[path[pos-1]][i];
path[pos] = i;
visited[i] = 1;
tsp(pos+1, curr_cost, lower_bound);
visited[i] = 0;
curr_cost -= cost[path[pos-1]][i];
lower_bound = old_lb;
}
}
}
}
int main() {
printf("Enter the number of cities: ");
scanf("%d", &n);
printf("Enter the cost matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}
visited[0] = 1;
path[0] = 0;
tsp(1, 0, 0);
printf("Minimum cost: %d\n", min_cost);
return 0;
}
OUTPUT:
Enter the number of cities: 4
Enter the cost matrix:
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Minimum cost: 80
RESULT:

Daa Record

Uploaded by

Copyright:

Available Formats

Daa Record

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Daa Record

Uploaded by

Copyright:

Available Formats

PANIMALAR ENGINEERING COLLEGE

DEPARTMENT OF COMPUTER SCIENCE AND BUSINESS SYSTEMS

IMPLEMENTATION AND TIME ANALYSIS OF GCD USING

IMPLEMENTATION AND TIME ANALYSIS OF GCD USING

int gcd(int a,int b)

printf(“enter two numbers:”);

printf(“GCD of %d and %d is %d”,a,b,gcd(a,b));

IMPLEMENTATION AND TIME ANALYSIS OF LINEAR SEARCH

printf(“enter the no.of.elements:”);

printf(“enter the search element:”);

printf(“elements %d is not present”,search);

printf(“element %d is present in %d location “,s,c);

enter the no.of.elements:4

enter the elements:11 10 12 19

enter element to be searched:10

element present at location 1

IMPLEMENTATION AND TIME ANALYSIS OF BINARY SEARCH

printf(“enter the size of the list”);

printf(“enter the search element”);

printf(“element found at %d”,mid);

printf(“element not found”);

enter the size of array:5

enter the element to be searched:11

the elements found at the position 1

IMPLEMENTATION AND TIME ANALYSIS OF SEARCHING

void merge(int arr[], int l,int m, int r)

int L[20], R[20];

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

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

while (i < n1 && j < n2)

if (L[i] <= R[j])

while (i < n1) {

while (j < n2)

void mergeSort(int arr[],int l, int r)

void printArray(int A[], int size)

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

printf("%d ", A[i]);

int arr[] = {12, 11, 13, 5, 6, 7};

int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

mergeSort(arr, 0, arr_size - 1);

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

Enter the size of the array:5

Enter the array elements :12 48 43 -1 3

Sorted elements are:

IMPLEMENTATION AND TIME ANALYSIS OF SEARCHING

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {

for(i = 0;i < count-1;i++) {

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

void swap(int num1, int num2) {

int temp = intArray[num1];

int Array[num1] = intArray[num2];

int Array[num2] = temp;

int partition(int left, int right, int pivot) {

int leftPointer = left -1;