design and analysis of algorithm Lab files

Department of Computer Science & Engineering Lucknow Institute of Technology Lucknow Session (2019-20) Practical lab Files “Design and Analysis of Algorithm Lab” (RCS 552) Submitted To:- Submitted By:- Ms. Arti Singh Nitesh Kumar Dubey (Asst. professor) B.Tech ( 5th semester) Dept. of Computer Science Computer Science & Engg. & Engineering 1836210903

Index Sr .no Experiment Signatures Remarks 1 2 3 4 5 6 7 8 9 10 Program for Recursive Binary & Linear Search. Program for Heap sort Program for Merge sort Program for selection sort Program for Insertion sort Program for Quick sort Knapsack Problem using Greedy Solution Perform Travelling Salesman Problem Find Minimum Spanning Tree Using Kruskal’s algorithm Implement N Queen Problem using Backtracking

Experiment:- 1 Objective: - Program for Recursive Binary & Linear Search. Program Binary Search #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int c, first, last, middle, n, search, array[100]; printf("Enter number of elements:n"); scanf("%d",&n); printf("Enter %d integers:n", n); for (c = 0; c < n; c++) scanf("%d",&array[c]); printf("Enter the value to find:n"); scanf("%d", &search); first = 0; last = n - 1; middle = (first+last)/2; while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) { printf("%d is present at index %d.n", search, middle+1); break; } else last = middle - 1; middle = (first + last)/2; }

if (first > last) printf("Not found! %d is not present in the list.n", search); return 0; } Program Linear search :- #include <stdio.h> #include <conio.h> int search(int [], int, int); int main() { int size, index, key; int list[20]; int count = 0; int i; printf("Enter the size of the list: "); scanf("%d", &size); index = size; printf("Printing the list:n"); for (i = 0; i < size; i++) { list[i] = rand() % size; printf("%dt", list[i]); } printf("nEnter the key to search: "); scanf("%d", &key); while (index > 0) { index = search(list, index - 1, key); /* In an array first position is indexed by 0 */ printf("Key found at position: %dn", index + 1); count++; }

if (!count) printf("Key not found.n"); return 0; } int search(int array[], int size, int key) { int location; if (array[size] == key) { return size; } else if (size == -1) { return -1; } else { return (location = search(array, size - 1, key)); } } Result:- Binary search Linear search

Experiment: - 2 Objective: - Program for heap sort Program #include<stdio.h> #include <conio.h> void create(int []); void down_adjust(int [],int); void main() { int heap[30],n,i,last,temp; printf("Enter no. of elements:"); scanf("%d",&n); printf("nEnter elements:"); for(i=1;i<=n;i++) scanf("%d",&heap[i]); heap[0]=n; create(heap); while(heap[0] > 1) { //swap heap[1] and heap[last] last=heap[0]; temp=heap[1]; heap[1]=heap[last]; heap[last]=temp; heap[0]--; down_adjust(heap,1); } printf("nArray after sorting:n"); for(i=1;i<=n;i++) printf("%d ",heap[i]); }

void create(int heap[]) { int i,n; n=heap[0]; for(i=n/2;i>=1;i--) down_adjust(heap,i); } void down_adjust(int heap[],int i) { int j,temp,n,flag=1; n=heap[0]; while(2*i<=n && flag==1) { j=2*i; if(j+1<=n && heap[j+1] > heap[j]) j=j+1; if(heap[i] > heap[j]) flag=0; else { temp=heap[i]; heap[i]=heap[j]; heap[j]=temp; i=j; } } } Result

Experiment:- 3 Program :- #include<stdio.h> #include <conio.h> void mergesort(int a[],int i,int j); void merge(int a[],int i1,int j1,int i2,int j2); int main() { int a[30],n,i; printf("Enter no of elements:"); scanf("%d",&n); printf("Enter array elements:"); for(i=0;i<n;i++) scanf("%d",&a[i]); mergesort(a,0,n-1); printf("nSorted array is :"); for(i=0;i<n;i++) printf("%d ",a[i]); return 0; } void mergesort(int a[],int i,int j) { int mid; if(i<j) { mid=(i+j)/2; mergesort(a,i,mid); mergesort(a,mid+1,j); merge(a,i,mid,mid+1,j);

} } void merge(int a[],int i1,int j1,int i2,int j2) { int temp[50]; int i,j,k; i=i1; j=i2; k=0; while(i<=j1 && j<=j2) { if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=j1) temp[k++]=a[i++]; while(j<=j2) temp[k++]=a[j++]; for(i=i1,j=0;i<=j2;i++,j++) a[i]=temp[j]; } Result:-

Experiment:- 4 Objective :- Program for selection Sort #include <stdio.h> #include <conio.h> int main() { int array[100], n, c, d, position, swap; printf("Enter number of elementsn"); scanf("%d", &n); printf("Enter %d integersn", n); for (c = 0; c < n; c++) scanf("%d", &array[c]); for (c = 0; c < (n - 1); c++) { position = c; for (d = c + 1; d < n; d++) { if (array[position] > array[d]) position = d; } if (position != c) { swap = array[c]; array[c] = array[position]; array[position] = swap; } }

printf("Sorted list in ascending order:n"); for (c = 0; c < n; c++) printf("%dn", array[c]); return 0; } Result:-

Experiment:- 5 Objective: - Program for Insertion sort Program #include <stdio.h> #include <conio.h> int main() { int n, array[1000], c, d, t; printf("Enter number of elementsn"); scanf("%d", &n); printf("Enter %d integersn", n); for (c = 0; c < n; c++) scanf("%d", &array[c]); for (c = 1 ; c <= n - 1; c++) { d = c; while ( d > 0 && array[d-1] > array[d]) { t = array[d]; array[d] = array[d-1]; array[d-1] = t; d--; } } printf("Sorted list in ascending order:n");

for (c = 0; c <= n - 1; c++) { printf("%dn", array[c]); } return 0; } Result:-

Experiment:- 6 Objective:- Program for Quick Sort Program #include <stdio.h> #include <conio.h> void quicksort (int [], int, int); int main() { int list[50]; int size, i; printf("Enter the number of elements: "); scanf("%d", &size); printf("Enter the elements to be sorted:n"); for (i = 0; i < size; i++) { scanf("%d", &list[i]); } quicksort(list, 0, size - 1); printf("After applying quick sortn"); for (i = 0; i < size; i++) { printf("%d ", list[i]); } printf("n"); return 0; } void quicksort(int list[], int low, int high) { int pivot, i, j, temp; if (low < high) {

pivot = low; i = low; j = high; while (i < j) { while (list[i] <= list[pivot] && i <= high) { i++; } while (list[j] > list[pivot] && j >= low) { j--; } if (i < j) { temp = list[i]; list[i] = list[j]; list[j] = temp; } } temp = list[j]; list[j] = list[pivot]; list[pivot] = temp; quicksort(list, low, j - 1); quicksort(list, j + 1, high); } } Result :-

Experiment:- 7 Objective: - Knapsack Problem using Greedy Solution Program # include<stdio.h> #include <conio.h> void knapsack(int n, float weight[], float profit[], float capacity) { float x[20], tp = 0; int i, j, u; u = capacity; for (i = 0; i < n; i++) x[i] = 0.0; for (i = 0; i < n; i++) { if (weight[i] > u) break; else { x[i] = 1.0; tp = tp + profit[i]; u = u - weight[i]; } } if (i < n) x[i] = u / weight[i]; tp = tp + (x[i] * profit[i]); printf("nThe result vector is:- "); for (i = 0; i < n; i++) printf("%ft", x[i]); printf("nMaximum profit is:- %f", tp); }

int main() { float weight[20], profit[20], capacity; int num, i, j; float ratio[20], temp; printf("nEnter the no. of objects:- "); scanf("%d", &num); printf("nEnter the wts and profits of each object:- "); for (i = 0; i < num; i++) { scanf("%f %f", &weight[i], &profit[i]); } printf("nEnter the capacityacity of knapsack:- "); scanf("%f", &capacity); for (i = 0; i < num; i++) { ratio[i] = profit[i] / weight[i]; } for (i = 0; i < num; i++) { for (j = i + 1; j < num; j++) { if (ratio[i] < ratio[j]) { temp = ratio[j]; ratio[j] = ratio[i]; ratio[i] = temp; temp = weight[j]; weight[j] = weight[i]; weight[i] = temp; temp = profit[j]; profit[j] = profit[i]; profit[i] = temp; } } } knapsack(num, weight, profit, capacity);

Experiment: - 8 Objective: - Perform Travelling Salesman Problem Program #include<stdio.h> #include <conio.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 Matrixn"); for(i=0;i < n;i++) { printf("nEnter Elements of Row: %dn",i+1); for( j=0;j < n;j++) scanf("%d",&ary[i][j]); completed[i]=0; } printf("nnThe 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("nnThe Path is:n"); mincost(0); //passing 0 because starting vertex printf("nnMinimum cost is %dn ",cost); return 0; } Result :-

Experiment :- 9 Objective: - Find Minimum Spanning Tree using kruskal’s Algorithm Program #include<stdio.h> #incluse <conio.h> #define MAX 30 typedef struct edge { int u,v,w; }edge; typedef struct edgelist { edge data[MAX]; int n; }edgelist; edgelist elist; int G[MAX][MAX],n; edgelist spanlist; void kruskal(); int find(int belongs[],int vertexno); void union1(int belongs[],int c1,int c2); void sort(); void print(); void main() { int i,j,total_cost; printf("nEnter number 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]); kruskal(); print(); } void kruskal() { int belongs[MAX],i,j,cno1,cno2; elist.n=0; for(i=1;i<n;i++) for(j=0;j<i;j++) { if(G[i][j]!=0) { elist.data[elist.n].u=i; elist.data[elist.n].v=j; elist.data[elist.n].w=G[i][j]; elist.n++; } } sort(); for(i=0;i<n;i++) belongs[i]=i; spanlist.n=0; for(i=0;i<elist.n;i++) { cno1=find(belongs,elist.data[i].u); cno2=find(belongs,elist.data[i].v); if(cno1!=cno2)

{ spanlist.data[spanlist.n]=elist.data[i]; spanlist.n=spanlist.n+1; union1(belongs,cno1,cno2); } } } int find(int belongs[],int vertexno) { return(belongs[vertexno]); } void union1(int belongs[],int c1,int c2) { int i; for(i=0;i<n;i++) if(belongs[i]==c2) belongs[i]=c1; } void sort() { int i,j; edge temp; for(i=1;i<elist.n;i++) for(j=0;j<elist.n-1;j++) if(elist.data[j].w>elist.data[j+1].w) { temp=elist.data[j]; elist.data[j]=elist.data[j+1]; elist.data[j+1]=temp; }

} void print() { int i,cost=0; for(i=0;i<spanlist.n;i++) { printf("n%dt%dt%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w); cost=cost+spanlist.data[i].w; } printf("nnCost of the spanning tree=%d",cost); } Result: -

Experiment :- 10 Objective: - Implement N Queen Problem using Backtracking Program #include<stdio.h> #include <conio.h> #include<math.h> int board[20],count;int main() { int n,i,j; void queen(int row,int n); printf(" - N Queens Problem Using Backtracking -"); printf("nnEnter number of Queens:"); scanf("%d",&n); queen(1,n); return 0; } void print(int n) { int i,j; printf("nnSolution %d:nn",++count); for(i=1;i<=n;++i) printf("t%d",i); for(i=1;i<=n;++i) { printf("nn%d",i); for(j=1;j<=n;++j) //for nxn board

{ if(board[i]==j) printf("tQ"); //queen at i,j position else printf("t-"); //empty slot } } } int place(int row,int column) { int i; for(i=1;i<=row-1;++i) { if(board[i]==column) return 0; else if(abs(board[i]-column)==abs(i-row)) return 0; } return 1; } void queen(int row,int n) { int column; for(column=1;column<=n;++column) {

if(place(row,column)) { board[row]=column; //no conflicts so place queen if(row==n) //dead end print(n); //printing the board configuration else //try queen with next position queen(row+1,n); } } } Result :-

design and analysis of algorithm Lab files

More Related Content

What's hot

Similar to design and analysis of algorithm Lab files

More from Nitesh Dubey

Recently uploaded

In this document

design and analysis of algorithm Lab files