GTU CSE

Posts

Showing posts with the label Design and Analysis of Algorithms

Prim’s Algorithm For Minimum Spanning Tree In C Programming

#include #include #define size 20 #define infi 9999 void prim(int L[][size],int node) { int T[size],i,j,k; int min_dist,v1,v2,total=0; for(i=1;i OUTPUT ---------------------------------------------------- PRIM`s MINIMUM SPANNING TREE ALGORITHM ---------------------------------------------------- Enter Number of nodes in the Graph:7 Enter Number of Edges in the Graph:12 --------Enter edges and length---------- Enter edge in form {v1,v2}:1 2 Enter Length from 1 to 2:1 Enter edge in form {v1,v2}:1 4 Enter Length from 1 to 4:4 Enter edge in form {v1,v2}:2 3 Enter Length from 2 to 3:2 Enter edge in form {v1,v2}:2 4 Enter Length from 2 to 4:6 Enter edge in form {v1,v2}:2 5 Enter Length from 2 to 5:4 Enter edge in form {v1,v2}:3 6 Enter Length from 3 to 6:6 Enter edge in form {v1,v2}:3 5 Enter Length from 3 to 5:5 Enter edge in form {v1,v2}:4 5 Enter Length from 4 to 5:3 Enter edge in form {v1,v2}:4 7 Enter Length from 4 to 7:4 Enter edge in form {v1,v2}:...

Bubble Sort in C Programming

#include< stdio.h> #include<conio.h> void display(int*,int); void bubble_sort(int*,int); void main() { int i,*a,n; clrscr(); printf("\n Enter number of element you want:"); scanf("%d",&n); for(i=0;i < n;i++) { printf("\n Enter element[%d]:",i); scanf("%d",&a[i]); } printf("\n------------------------------------------"); printf("\n Elements before sorting:"); display(a,n); printf("\n------------------------------------------"); bubble_sort(a,n); printf("\n------------------------------------------"); printf("\n Elements after sorting:"); display(a,n); printf("\n------------------------------------------"); getch(); } void bubble_sort(int *a,int n) { int pass,i,temp; for(pass=0;pass<= n-1;pass++) { for(i=0;i< n-pass-1;i++) { if(a[i]>=a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; } } printf("\...

Chain Matrix Multiplication in C Programming

#include #include void MatrixChain(long*,long); void pop(long[10][10],long,long); long s[10][10],m[10][10]; void main() { long *p,n,i,j,str,end; clrscr(); printf("\n Enter number of element for p Matrix:"); scanf("%ld",&n); printf("\n Enter dimension for P matrix:"); for(i=0;i OUTPUT Enter number of element for p Matrix:6 Enter dimension for P matrix:30 3 15 5 10 20 8 --------------------M matrix-------------------- 0 1350 675 1275 2775 2175 -1 0 225 375 975 1455 -1 -1 0 750 2500 2400 -1 -1 -1 0 1000 1800 -1 -1 -1 -1 0 1600 -1 -1 -1 -1 -1 0 --------------------S matrix-------------------- -1 1 1 1 1 1 -1 -1 2 3 4 5 -1 -1 -1 3 3 3 -1 -1 -1 -1 4 5 -1 -1 -1 -1 -1 5 ...

Knapsack using Greedy Algorithm in C Programming

# include # include void knapsack(int n, float weight[], float value[], float W) { float x[20], tp= 0; int i, j, u; u=W; for (i=0;i u) break; else { x[i]=1.0; tp= tp+value[i]; u=u-weight[i]; } } if(i OUTPUT ------------------------------------------------------------------------------------ KNAPSACK PROBLEM USING GREEDY APPROACH ------------------------------------------------------------------------------------ Enter number of Objects you want:5 ----------------Enter the weights and values of each object-------------- Enter weight and value for object1:10 20 Enter weight and value for object2:20 30 Enter weight and value for object3:30 66 Enter weight and value for object4:40 40 Enter weight and value for object5:50 60 Enter the capacity of knapsack:100 ------------------------------------------------------------------------------------ weight | 30.00 10.00 20.00 50.00 40.00 value | 66.00 20.00 30.00 60.00 40.00 x ...

Kruskal’s Algorithm For Minimum Spanning Tree in C Programming

#include #include #define INFINITY 999 typedef struct Graph { int v1,v2,length; }GR; GR G[20]; int tot_edge,tot_node; void create(); void krushkal(); int find(int,int[]); void merge(int i,int j,int parent[]); void main() { clrscr(); printf("\n----------------------------------------------------"); printf("\nKRUSHKAL`s MINIMUM SPANNING TREE ALGORITHM"); printf("\n----------------------------------------------------"); create(); printf("\n Enter any key to see Minimum Spanning Tree?"); getch(); krushkal(); getch(); } void create() { int k; printf("\n Enter Number of nodes in the Graph:"); scanf("%d",&tot_node); printf("\n Enter Number of Edges in the Graph:"); scanf("%d",&tot_edge); printf("\n--------Enter edges and length----------\n"); for(k=0;k OUTPUT ---------------------------------------------------- KRUSHKAL`s MINIMUM SPANNING TREE ALGORITHM ----...

make a change using Greedy Algorithm in C Programming

#include #include int C[]={1,5,10,25,100}; void make_change(int n); int bestsol(int,int); void main() { int n; clrscr(); printf("\n------------------------------------------------"); printf("\n MAKING CHANGE USING GREEDY ALGORITHM "); printf("\n------------------------------------------------"); printf("\n Enter amount you want:"); scanf("%d",&n); make_change(n); getch(); } void make_change(int n) { int S[100],s=0,x,ind=0,i; printf("\n----------------AVAILABLE COINS-----------------\n"); for(i=0;i -1;i--) { if((s+C[i]) OUTPUT ------------------------------------------------------------------------------- MAKING CHANGE USING GREEDY ALGORITHM ------------------------------------------------------------------------------- Enter amount you want:196 ---------------------------AVAILABLE COINS------------------------- 1 5 10 25 100 ------------------------------------...

Rabin-Karp Algorithm String Matching in C Programming

#include #include #define tonum(c) (c >= 'A' && c OUTPUT Enter String:rabin karp algorithm for pattern matching Enter Pattern you want to search into string:pattern Enter value of q:11 Pattern is found at displacement:25

Knapsack Using Backtracking in C Programming

#include #include #define MAX 20 float final_profit; int w[MAX]; int p[MAX]; int n,m; int temp[MAX],x[MAX]; float final_wt; float Bound_Calculation(int,int,int); void BackTracking(int,int,int); void main() { int i; clrscr(); printf("\n-------------------------------------------------------"); printf("\n KNAPSACK PROBLEM USING BACKTRACKING"); printf("\n-------------------------------------------------------"); printf("\n Enter number of Objects you want:"); scanf("%d",&n); printf("\n-------------------------------------------------------"); for(i=1;i final_profit)&&(k==n)) { final_profit=new_cp; final_wt=new_cw; for(j=1;j =final_profit) { temp[k]=0; if(k final_profit)&&(k==n)) { final_profit=cp; final_wt=cw; for(j=1;j OUTPUT ------------------------------------------------------- KNAPSACK PROBLEM USING BACKTRACKING -------------------------------------...

N-Queen Problem C Programming

#include #include #include int board[20]; int count; void print_board(int); void Queen(int,int); int place(int,int); void main() { int n,i,j; clrscr(); printf("\n-------------------------------------------------------"); printf("\n n-Queen problem using Backtracking"); printf("\n-------------------------------------------------------"); printf("\n Enter number of Queen:"); scanf("%d",&n); Queen(1,n); } void print_board(int n) { int i,j; printf("\n-------------Solution %d---------------\n ",++count); for(i=1;i OUTPUT ------------------------------------------------------- n-Queen problem using Backtracking ------------------------------------------------------- Enter number of Queen:4 -------------Solution 1--------------- 1 2 3 4 ------------------------------------------------------- 1 | - Q - - 2 | - - - Q 3 | Q - - - 4 | - - Q - --...

Breath First Search (BFS) in C Programming

#include #include #define MAX 20 #define TRUE 1 #define FALSE 0 int g[MAX][MAX]; int v[MAX]; int Q[MAX]; int n; int front,rear; void create(); void BFS(int); void main() { int i,j; char ans; clrscr(); printf("\n----------------------------------------------------"); printf("\n BREADTH FIRST SEARCH"); printf("\n----------------------------------------------------"); create(); getch(); printf("\n Adjacency Matrix for the graph is:"); printf("\n----------------------------------------------------"); for(i=0;i =MAX) printf("\n Invalid Vertex"); else { printf("\n The Depth First Search of the Graph is:"); printf("\n----------------------------------------------------\n"); BFS(i); printf("\n----------------------------------------------------\n"); } printf("\n Dou want to Traverse By other node?"); ans=getche(); }while(ans=='y' ||...

Depth First Search (DFS) in C Programming

#include #include #define MAX 20 #define TRUE 1 #define FALSE 0 int g[MAX][MAX]; int v[MAX]; int n; void create(); void DFS(); void main() { int i,j; char ans; clrscr(); printf("\n----------------------------------------------------"); printf("\n DEPTH FIRST SEARCH"); printf("\n----------------------------------------------------"); create(); getch(); printf("\n Adjacency Matrix for the graph is:"); printf("\n----------------------------------------------------"); for(i=0;i =MAX) printf("\n Invalid Vertex"); else { printf("\n The Depth First Search of the Graph is:"); printf("\n----------------------------------------------------\n"); DFS(i); printf("\n----------------------------------------------------\n"); } printf("\n Dou want to Traverse By other node?"); ans=getch(); }while(ans=='y' || ans=='Y'); } void create(...

Greatest Common Divisor.in C Programming

#include #include int GCD(int,int); void main() { int n1,n2; clrscr(); printf("\n Enter two numbers for GCD:"); scanf("%d %d",&n1,&n2); printf("\n Greatest common divisor of %d and %d is:%d",n1,n2,GCD(n1,n2)); getch(); } int GCD(int m,int n) { if(n==0) return m; else { if(n>m) { n=n+m; m=n-m; n=n-m; } return GCD(n,m%n); } } OUTPUT Enter two numbers for GCD:5 15 Greatest common divisor of 5 and 15 is:5

Tower Of Hanoi in C Programming

#include #include #include void tower_of_hanoi(int,char,char,char); void main() { int disk,move; clrscr(); printf("\n Enter number of disks:"); scanf("%d",&disk); move=pow(2,disk)-1; printf("\n No. of moves required is:%d",move); printf("\n A-->Source peg\n B-->Destination peg \n C-->Auxiliary peg"); tower_of_hanoi(disk,'A','B','C'); getch(); } void tower_of_hanoi(int disk,char from,char to,char aux) { if(disk==1) { printf("\n move disk %d from %c to %c",disk,from,to); } else { tower_of_hanoi(disk-1,from,aux,to); printf("\n move disk %d from %c to %c",disk,from,to); tower_of_hanoi(disk-1,aux,to,from); } } OUTPUT Enter number of disks:4 No. of moves required is:15 A-->Source peg B-->Destination peg C-->Auxiliary peg move disk 1 from A to C move disk 2 from A to B move disk 1 from C to B move disk 3 from A to C move disk 1 from B to A ...

Floyd’s Algorithm using dynamic Programming in C

#include< stdio.h > #include #include #define MAX 30 void floyd(int[MAX][MAX],int); int mix(int,int); void main() { int l[MAX][MAX],n,i,j; clrscr(); printf("\n Enter number of vertices you need:"); scanf("%d",&n); printf("\n[Enter 9999 as infinity value]"); for(i=1;i OUTPUT Enter number of vertices you need:4 [Enter 9999 as infinity value] l[1][1]:0 l[1][2]:5 l[1][3]:9999 l[1][4]:9999 l[2][1]:50 l[2][2]:0 l[2][3]:15 l[2][4]:5 l[3][1]:30 l[3][2]:9999 l[3][3]:0 l[3][4]:15 l[4][1]:30 l[4][2]:9999 l[4][3]:5 l[4][4]:0 l[4][3]:5 l[4][4]:0 --k=1-------D1--------- ---------P1------ 0 5 9999 9999 0 0 0 0 50 0 1 5 0 0 0 0 30 35 0 15 0 1 0 0 30 35 5 0 0 1 0 0 --k=2-------D2--------- ---------P2------ 0 5 20 10 0 0...

Find Longest Common Subsequence using Dynamic Programming in C

#include< stdio.h > #include #include #include #define MAX 50 int c[MAX][MAX]; char b[MAX][MAX]; char str1[MAX],str2[MAX]; char x[MAX],y[MAX],ans[MAX]; int m,n,ind; void LCS(char x[MAX],char y[MAX]); void printLCS(char[MAX][MAX],char[MAX],int,int); void main() { int i,j,ind1=1; clrscr(); printf("\n Enter string1:"); scanf("%s",&str1); printf("\n Enter string2:"); scanf("%s",&str2); LCS(str1,str2); printf("\n All the possible Longest Common Subsequence(LCS):"); printf("\n--------------------------------------------------------------"); for(i=n;i>0;i--) { if(c[m][i]==c[m][n]) { ind=0; printLCS(b,x,m,i); printf("\n solution %d: %s",ind1++,strrev(ans)); } else { break; } } printf("\n--------------------------------------------------------------"); getch(); } void LCS(char x1[MAX],char y1[MAX]) { int i,j; m=strlen(x1); n=strlen(y1); ...

0/1 knapsack problem using Dynamic programming in C

#include #include #define MAX 20 void knapsackDP(int,int); int max(int,int); void backtracking(); int weight[MAX],value[MAX],W,no,*x; int v[MAX][MAX]; void main() { int i,j; clrscr(); printf("\n Enter number of Object you want:"); scanf("%d",&no); printf("\n Enter weight and values in ascending order of vales");; for(i=1;i b)?a:b; } void backtracking() { int j1,i; j1=W; printf("\nIncluded Object \t weight \t value"); printf("\n-----------------------------------------------------------------------------"); for(i=no;i >=0;i--) { if(v[i][j1]!=v[i-1][j1] && (v[i][j1]==v[i-1][j1-weight[i]]+value[i])) { printf("\n%2d \t\t\t %2d \t\t %2d",i,weight[i],value[i]); j1=j1-weight[i]; } } } OUTPUT Enter number of Object you want:5 Enter weight and values in ascending order of values Enter Weight and Value for Object 1:1 1 Enter Weight and Value for Object 2:2 6 Enter Weigh...

Merge Sort using Divide and Conquer in C

#include #include #define MAX 50 void display(int[MAX],int); void Merge_sort(int[MAX],int,int); void Combine(int[MAX],int,int,int); void main() { int i,T[MAX],n; clrscr(); printf("\n Enter number of element you want:"); scanf("%d",&n); for(i=0;i low) { mid=(low+high)/2; Merge_sort(T,low,mid); Merge_sort(T,mid+1,high); Combine(T,low,mid,high); } } void Combine(int T[MAX],int low,int mid,int high) { int i,j,k,temp[MAX]; k=low; i=low; j=mid+1; while(i OUTPUT Enter number of element you want:7 Enter element[0]:77 Enter element[1]:55 Enter element[2]:44 Enter element[3]:66 Enter element[4]:44 Enter element[5]:22 Enter element[6]:99 ------------------------------------------------------------------------------------ Elements before sorting: 77 55 44 66 44 22 99 ------------------------------------------------------------------------------------ --------------------------------------------------------------------...

Quick Sort Using Divide an Conquer

#include #include #define MAX 50 //int pivotpoint; void display(int[MAX],int); void Quick_sort(int[MAX],int low,int high); int pivot(int[MAX],int,int); void main() { int i,T[MAX],n; clrscr(); printf("\n Enter number of element you want:"); scanf("%d",&n); for(i=0;i low) { pivotpoint=pivot(T,low,high); Quick_sort(T,low,pivotpoint-1); Quick_sort(T,pivotpoint+1,high); } } int pivot(int T[MAX],int low,int high) { int i,j; int pivotitem,temp; pivotitem=T[low]; i=low; j=high; while(i pivotitem) j--; if(i OUTPUT Enter number of element you want:10 Enter element[0]:56 Enter element[1]:33 Enter element[2]:2 Enter element[3]:90 Enter element[4]:67 Enter element[5]:45 Enter element[6]:43 Enter element[7]:77 Enter element[8]:56 Enter element[9]:2 ------------------------------------------------------------------------------------ Elements before sorting: 56 33 2 90 67 45 43 77 56 2 ---------------------...

Multiplication of Large Integer using Divide and Conquer

#include #include #include long prod(long,long); long noOfDigit(long,long); void main() { long m,n; clrscr(); printf("\n-----------------------------------------------"); printf("\nMULTIPLICATION USING DIVIDE & CONQUER"); printf("\n-----------------------------------------------"); printf("\n Enter number1:"); scanf("%ld",&m); printf("\n Enter number2:"); scanf("%ld",&n); printf("\n-----------------------------------------------"); printf("\n multiplication of %ld and %ld is:%ld",m,n,prod(m,n)); printf("\n-----------------------------------------------"); getch(); } long prod(long u,long v) { long x,y,w,z; long n,m,p,q,r; n=noOfDigit(u,v); if(u==0 || v==0) { return 0; } else if(n =n) max=m; else max=n; while(max>0) { max=max/10; b++; } return b; } OUTPUT ----------------------------------------------- MULTIPLICATION USING DIVI...

Heap sort using Divide & Conquer

#include #include #define MAX 30 struct heap{ int S[MAX]; int heapsize; }H; void siftdown(struct heap* H,int i) { int parent,largerchild; int siftkey; int spotfound; siftkey=H->S[i]; parent=i; spotfound=0; while(2*parent heapsize && spotfound==0) { if(2*parent heapsize && H->S[2*parent] S[2*parent+1]) largerchild=2*parent+1; else largerchild=2*parent; if(siftkey S[largerchild]) { H->S[parent]=H->S[largerchild]; parent=largerchild; } else spotfound=1; } H->S[parent]=siftkey; } int root(struct heap* H) { int keyout; keyout=H->S[1]; H->S[1]=H->S[H->heapsize]; H->heapsize=H->heapsize-1; siftdown(H,1); return keyout; } void removekeys(int n,struct heap* H) { int i; for(i=n;i>=1;i--) { H->S[i]=root(H); } } void makeheap(int n,struct heap* H) { int i; H->heapsize=n; for(i=n/2;i>=1;i--) siftdown(H,i); } void heapsort(int n,struct heap* H) { makeheap(n,H); removekeys(n,H...