THE DESIGN AND ANALYSIS OF ALGORITHMS

-

 THE DESIGN AND ANALYSIS OF ALGORITHMS LAB PROGRAMS

Program 1. Write a program to implement linear search algorithm Repeat the experiment for different values of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function prototypes
int linearSearch(int arr[], int n, int key);
void generateRandomArray(int arr[], int n);

int main() {
    int arraySizes[] = {100, 500, 1000, 5000, 10000}; // Different values of n
    clock_t start, end;
    double cpu_time_used;

    // Perform experiment for each array size
    for (int i = 0; i < sizeof(arraySizes) / sizeof(arraySizes[0]); i++) {
        int n = arraySizes[i];
        int arr[n];
        generateRandomArray(arr, n); // Generate a random array of size n

        int key = arr[n - 1]; // Searching for the last element in the array

        // Measure time taken for linear search
        start = clock();
        int index = linearSearch(arr, n, key);
        end = clock();

        // Calculate time taken in milliseconds
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC * 1000.0;

        // Output the result
        printf("Linear Search for n = %d: Found at index %d. Time taken: %f ms\n", n, index, cpu_time_used);
    }

    return 0;
}

// Function to perform linear search
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i; // Return index if element found
        }
    }
    return -1; // Return -1 if element not found
}

// Function to generate a random array of given size
void generateRandomArray(int arr[], int n) {
    srand(time(NULL)); // Seed for random number generation
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100; // Random integers between 0 to 99
    }
}


Program 2. Write a program to implement binary search algorithm. Repeat the experiment for differentvalues of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.

#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
int pos;
int binsearch(int ,int[],int,int,int);
void main()
{
int n,i,a[100],k,low,high;
clock_t B,E;
clrscr();
printf("Enter the value of n");
scanf("%d",&n);
printf("Enter the array values\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the search element");
scanf("%d",&k);
low=0;
high=n-1;
B=clock();
pos = binsearch(n,a,k,low,high);
E=clock();
if(pos==-1)
printf("\n Unsuccesfull search");
else
Printf("\n element %d is found at position %d",k,pos+1);
printf("\n time taken is %lf cpu cycle\n",(E-B)/CLK_TCK);
getch();
}
int binsearch(int n,int a[],int k,int low,int high)
{
int mid;
delay(100);
mid=(low+high)/2;
if(low>high)
return -1;
if(k==a[mid])
return(mid);
else
if(k<a[mid])
return binsearch(n,a,k,low,mid-1);
else
return binsearch(n,a,k,high,mid+1);
}


Program 3. Write a program to solve towers of honai problem and execute it for different number of disks 

#include<stdio.h>
#include<conio.h>
void TOH(int n,char rodA,char rodC, char rodB)
{
if(n==1)
{ printf("\nMove Disk 1 from rod %c to rod %c",rodA,rodC);
return;
}
TOH(n-1,rodA,rodB,rodC);
printf("\nMove Disk %d from rod %c to rod %c",n,rodA,rodC);
TOH(n-1,rodB,rodC,rodA);
}
void main()
{
int n;
clrscr();
printf("Enter the number of Disk\n");
scanf("%d",&n);
TOH(n,'A','C','B');
getch();
}


Program 4. Write a Program to Sort a given set of numbers using selection sort algorithm. Repeat the
experiment for different values of n, the number of elements in the list to be sorted and plot a graph
of the time taken versus n. The elements can be read from a file or can be generated using the
random number generator

#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
int min,i,j,temp;
void selection(int a[],int n)
{
delay(100);
for (i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[min]>a[j])
{
min=j;
}
}
if(min!=i)
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
printf("\n Sorted array \n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
void main()
{
int a[50],n;
clock_t B,E;
clrscr();
printf("Enter the value of n");
scanf("%d",&n);
randomize();
for(i=0;i<n;i++)
{
a[i]=rand()%100;
}
printf("The array elements are \n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
B=clock();
selection(a,n);
E=clock();
printf("\n time taken is %lf cpu cycles\n",(E-B)/CLK_TCK);
getch();
}

Program 5. Write a program to find the value of an (where a and n are integers) using both brute-force based algorithm and divide and conquer based algorithm

#include<stdio.h>
#include<conio.h>
void main()
{
int a,n,result,ch;
clrscr();
printf(" Enter the base");
scanf("%d", &a);
printf("Enter the power");
scanf("%d",&n);
printf("1--Brute -Force Based Algorithm\n");
printf("2--Divide and Conquer Based Algorithm\n");
printf("Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
result=power(a,n);
break;
case 2:
result=power1(a,n);
break;
default:
printf("invalid choice");
}
printf("\nResult: %d^%d=%d",a,n,result);
getch();
}
int power(int a,int n)
{
if(n==0)
return 1;
else
return(a*power(a,n-1));
}
int power1(int a,int n)
{
if(n==0)
return 1;
if(n%2==0)
return power1(a*a,n/2);
else
return a*power1(a*a,n/2);
}



Program 6. Write a Program to Sort a given set of elements using quick sort algorithm. Repeat the
experiment for different values of n, the number of elements in the list to be sorted and plot a graph
of the time taken versus n

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
void quicksort(int a[],int low,int high)
{
int j;
delay(100);
if(low<high)
{
j=partition(a,low,high);
quicksort(a,low,j-1);
quicksort(a,j+1,high);
}
}
int partition(int a[],int low,int high)
{
int pivot,j,temp,i;
pivot=low;
i=low;
j=high;
while(i<j)
{
while(a[pivot]>=a[i] && i<high)
i++;
while(a[pivot]<a[j])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
return j;
}

void main()
{
int a[50],n,i;
clock_t B,E;
clrscr();
printf("Enter the value of n");
scanf("%d",&n);
randomize();
for(i=0;i<n;i++)
{ a[i]=rand()%100;
}
printf("The array elements are\n");
for(i=0;i<n;i++)
{
printf( "%d \t",a[i]);
}
B=clock();
quicksort(a,0,n-1);
E=clock();
printf("\n sorted array\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
printf("\nTime taken is %lf cpu cycles\n",(E-B)/CLK_TCK);
getch();
}

Program 7. Write a Program to find the binomial co-efficient C(n, k), [where n and k are integers and n > k] using brute force based algorithm and also dynamic programming based algorithm

Brute-Force Recursive Algorithm

#include <stdio.h>

// Brute-force recursive approach to compute C(n, k)
int binomialCoefficientRecursive(int n, int k) {
    // Base cases
    if (k == 0 || k == n)
        return 1;
    // Recursive calls
    return binomialCoefficientRecursive(n - 1, k - 1) + binomialCoefficientRecursive(n - 1, k);
}

int main() {
    int n = 5;  // Example values for n and k
    int k = 2;

    if (n >= k) {
        int result = binomialCoefficientRecursive(n, k);
        printf("C(%d, %d) = %d\n", n, k, result);
    } else {
        printf("Invalid input: n must be greater than or equal to k\n");
    }

    return 0;
}


Dynamic Programming Algorithm

#include <stdio.h>

// Dynamic programming approach to compute C(n, k)
int binomialCoefficientDP(int n, int k) {
    int dp[n + 1][k + 1];
    int i, j;

    // Fill dp[][] table using bottom-up approach
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= i && j <= k; j++) {
            // Base cases
            if (j == 0 || j == i)
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][k];
}

int main() {
    int n = 5;  // Example values for n and k
    int k = 2;

    if (n >= k) {
        int result = binomialCoefficientDP(n, k);
        printf("C(%d, %d) = %d\n", n, k, result);
    } else {
        printf("Invalid input: n must be greater than or equal to k\n");
    }

    return 0;
}


Program 8. Write a Program to implement Floyd’s algorithm and find the lengths of the shortest paths from every pairs of vertices in a given weighted graph

#include<stdio.h>
#include<conio.h>
int D[10][10],n;
void main()
{
int n,e,u,v,w,i,j;
D[10][10]=0;
clrscr();
printf(" Enter the number of vertices");
scanf("%d",&n);
printf("Enter the number of edges");
scanf("%d",&e);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
D[i][j]=999;
for(i=1;i<=e;i++)
{
printf("Enter the end vertices of edge with weight %d:",i);
scanf("%d%d%d",&u,&v,&w);
D[u][v]=w;
}
printf("\nAdjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",D[i][j]);
}
printf("\n");
}
Floyds(D,n);
printf("\nTransitive closure\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",D[i][j]);
}
printf("\n");
}
printf("\n The shortest Paths are\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("\n <%d,%d>=%d",i,j,D[i][j]);
}
getch();
}
Floyds(int D[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
D[i][j]=0;
else
D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
return;
}
int min(int a,int b)
{
return (a<b) ? a: b;
}

Program 9. Write a program to evaluate a polynomial using brute-force based algorithm and using Horner’s rule and compare their performances

#include<stdio.h>
#include<conio.h>
int i,j,sum,power,n;
int poly[5];
void main()
{
int ch,x;
clrscr();
printf("Enter the order of the polynomial \n");
scanf("%d",&n);
printf("Enter the value of x");
scanf("%d",&x);
printf("Enter %d coefficient \n",n+1);
for(i=0;i<=n;i++)
scanf("%d",&poly[i]);
Horners(poly,n,x);
print();
getch();
}
Horners(int poly[],int n,int x)
{
sum=poly[0];
for(i=1;i<=n;i++)
{
sum=sum*x+poly[i];
}
return;
}
print()
{
power=n;
printf("The given polynomial is \n");
for(i=0;i<=n;i++)
{
if(power<0)
{
break;
}
if(poly[i]>0)
printf("+");
else if(poly[i]<0)
printf("-");
else
printf(" ");
printf("\%dx^%d",abs(poly[i]),power--);
}
printf("\n sum of the polynomial =%d\n",sum);
return;
}


Program 10. Write a Program to solve the string matching problem using Boyer-Moore approach.

#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX_CHARS 256
int max(int a, int b)
{
return(a>b)? a:b;
}
void badCharHeuristic(char *str,int size, int badChar[MAX_CHARS])
{
int i;
for(i=0;i<size;i++)
badChar[i]=-1;
for(i=0;i<size;i++)
badChar[(int) str[i]]=i;
}
void patternsearch(char *text,char *pat)
{
int m=strlen(pat);
int n=strlen(text);
int badChar[MAX_CHARS];
int s=0;
badCharHeuristic(pat,m,badChar);
while(s<=(n-m))
{
int j=m-1;
while(j>=0&&pat[j]==text[s+j])
j--;
if(j<0)
{
printf("\n pattern occurs at position=%d",s);
s+=(s+m<n)?m-badChar[text[s+m]]:1;
}
else
s+=max(1,j-badChar[text[s+j]]);
}
}
void main()
{
char text[100];
char pat[100];
clrscr();
printf("Enter the text:");
gets(text);
text[strlen(text)-1]='\0';
printf("Enter the pattern:");
gets(pat);
pat[strlen(pat)-1]='\0';
patternsearch(text,pat);
getch();
}

Program 11. Write a Program to solve the string matching problem using KMP algorithm

#include<stdio.h>
#include<conio.h>
#include<string.h>
void compute(char* pat,int M,int* lps);
void KMPS(char *pat,char *txt)
{
int i,j;
int M = strlen(pat);
int N = strlen(txt);
int lps[100];
compute(pat,M,lps);
i=0;
j=0;
while(i<N)
{
if(pat[j]==txt[i])
{
j++;
i++;
}
if(j==M)
{
printf("found pattern at index %",i-j);
j=lps[j-1];
}
else if(i<N && pat[j]!=txt[i])
{
if(j!=0)
j=lps[j-1];
else
i=i+1;
}
}
}
void compute(char* pat, int M,int* lps)
{
int i;
int len=0;
lps[0]=0;
i=1;
while(i<M)
{
if(pat[i]==pat[len])
{
len++;
lps[i]=len;
i++;
}
else
{
if(len!=0)
{
len=lps[len-1];
}
else
{
lps[i]=0;
i++;
}
}
}
}
int main()
{
char txt[100];
char pat[100];
clrscr();
printf("Enter the text:");
gets(txt);
txt[strlen(txt)-1]='\0';
printf("Enter the pattern:");
gets(pat);
pat[strlen(pat)-1]='\0';
KMPS(pat,txt);
return 0;
}


Program 12. Write a program to implement BFS traversal algorithm

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v) {
for (i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r) {
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main() {
int v;
clrscr();
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++) {
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i); else
printf("\n Bfs is not possible");
getch();
}

Program 13. Write a program to find the minimum spanning tree of a given graph using Prim’s algorithm

#include<stdio.h>
int a,b,u,v,i,j,n,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf("Enter the no of Vertices\n");
scanf("%d",&n);
printf("Enter the adjacency Matrix");
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[i]=0;
printf("The edges of spanning tree are");
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 Edges %d \t : (%d %d) cost =%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\nMinimum cost=%d",mincost);
getch();
}



Program 14. Write a Program to obtain the topological ordering of vertices in a given digraph. Compute the transitive closure of a given directed graph using Warshall's algorithm.

#include<stdio.h>
#include<conio.h>
int R[10][10],n;
void main()
{
int n,e,u,v,i,j;
R[10][10]=0;
clrscr();
printf(" Enter the number of vertices:");
scanf("%d",&n);
printf("Enter the number of edges:");
scanf("%d",&e);
for(i=1;i<=e;i++)
{
printf("Enter the end vertices of edge%d:",i);
scanf("%d%d",&u,&v);
R[u][v]=1;
}
printf("\nAdjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",R[i][j]);
}
printf("\n");
}
warshall(R,n);
printf("\nTransitive closure\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d\t",R[i][j]);
}
printf("\n");
}
getch();
}
warshall(int R[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
R[i][j]=max(R[i][j],R[i][k]&&R[k][j]);
return;
}
int max(int a,int b)
{
return (a>b) ? a: b;
}

Program 15. Write a Program to Find a subset of a given set S = {s1,s2, ,sn} of n positive integers whose .....
sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two
solutions {1,2,6} and {1,8}.A suitable message is to be displayed if the given problem instance
doesn't have a solution

#include<stdio.h>
int w[10],d,n,count,x[10],i;
void sum_of_subsets(int s, int k,int r)
{
x[k]=1;
if(s+w[k]==d)
{
printf("\n Subset%d=",++count);
for(i=0;i<=k;i++)
{
if(x[i])
printf("%d",w[i]);
}
}
else if(s+w[k]+w[k+1]<=d)
{
sum_of_subsets(s+w[k],k+1,r-w[k]);
}
if((s+r-w[k]>=d)&&(s+w[k+1])<=d)
{
x[k]=0;
sum_of_subsets(s,k+1,r-w[k]);
}
}
void main()
{
int sum=0,k;
clrscr();
printf("Enter the number of elements:");
scanf("%d",&n);
printf("Enter the elements in ascending order:");
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
}
printf("Enter the sum:");
scanf("%d",&d);
for(i=0;i<n;i++)
{
x[i]=0;
sum=sum+w[i];
}
if(sum<d||w[0]>d)
{
printf("\n No subset possible\n");
}
else
{
count = 0;
sum_of_subsets(0,0,sum);
}
getch();
}

Comments

  1. Anonymous29 June 2024 at 21:40

    kindly upload DAA
    Program 1
    Program 7
    so it will be helpful for us

    ReplyDelete

Post a Comment

Popular posts from this blog

Mobile Application Development Lab

-
GITHUBLINK 1.Creating “Hello world” Application 1. Click Start →Android Studio, a Welcome to Android Studio dialog box will appear. Click New Project, the New Project Dialog box appears.  2. Choose Empty Views Activity then click Next.  3. Specify the Name of your project, Select the Language as Java, and Select the Minimum SDK as API 16 (“Jelly Bean”, Android 4.1). Click Finish Button.  4. Create a Button resource in activity_main.xml and update the following code <? xml version ="1.0" encoding ="utf-8" ?> <androidx.constraintlayout.widget.ConstraintLayout xmlns: android ="http://schemas.android.com/apk/res/android" xmlns: app ="http://schemas.android.com/apk/res-auto" xmlns: tools ="http://schemas.android.com/tools" android :layout_width ="match_parent" android :layout_height ="match_parent" tools :context =".MainActivity" > <Button android :id ="@+i...
Read more

WEB PROGRAMMING LAB (html&php)

-
 WEB PROGRAMMING LAB(NEP) 1.Create a form with the elements of Textboxes, Radio buttons, Checkboxes, and so on. Write JavaScript code to validate the format in email, and mobile number in 10 characters, If a textbox has been left empty, popup an alert indicating when email, mobile number and textbox has been left empty code: < html > < head > < title > Black Eye Form </ title > < script > function Form () { var name = document . forms [ "myForm" ][ "name" ]. value ; var email = document . forms [ "myForm" ][ "email" ]. value ; var password = document . forms [ "myForm" ][ "password" ]. value ; var phone = document . forms [ "myForm" ][ "phone" ]. value ; if ( name == "" ) { alert ( " name must be filled out" ); return false ; } if ( email == ""...
Read more

Python Programming

-
Image
 Python Programming  Introduction to python programming Python is a high-level, interpreted programming language known for its simplicity and versatility. It is widely used in various fields, from web development to data science, machine learning, automation, and more. This introduction will cover the basics of Python programming, including its features, installation, and core concepts. Program 1: write  a python program to demonstrate basic data types in python (here we have many other data types) sol:                  print ( "----int----" ) print ( "possible integer values" ) print ( 15 ) print (- 25 ) print ( 0o 15 ) print ( 0x 12a ) x = 2 x = int ( 2 ) print ( x ) print ( int ( 25.5 )) print ( int ( "25" )) print ( "operations on integers" ) print ( "arithmetic operatons" ) print ( 2 ** 3 ) print ( 2 * 3 ) print ( 20 / 3 ) print ( 10 // 3 ) print ( 10 + 3 ) print ( 10 - 3 ) print ( "mathematical function" ) print ( pow ( ...
Read more