1a.
#include <stdio.h>
#include <string.h>
void bruteForceStringMatch(char text[], char pattern[])
{
 int n = strlen(text);
 int m = strlen(pattern);
 int i, j;
 int found = 0;
 for (i = 0; i <= n - m; i++)
 {
 j = 0;
 while (j < m && text[i + j] == pattern[j])
 {
 j++;
 }
 if (j == m) {
 printf("Pattern found at position %d\n", i);
 found = 1;
 }
 }
 if (!found) {
 printf("Pattern not found in the text.\n");
 }
}
int main() {
 char text[200];
 char pattern[100];
 printf("Enter the text: ");
 fgets(text, sizeof(text), stdin);
 printf("Enter the pattern: ");
 fgets(pattern, sizeof(pattern), stdin);
 // Remove newline characters if present
 text[strcspn(text, "\n")] = '\0';
 pattern[strcspn(pattern, "\n")] = '\0';
 /*String Complement Span: Syntax: size_t strcspn(const char *str1, const char *str2);
 It returns:The index of the first character in str1 that matches any character in str2
 and replace the str2 in that returned index position
 i.e
text[strcspn(text, "\n")] = '\0';
 the above function returns the index of the first occurance of \n" in the text
 and replace the '\0' character in that place */
 bruteForceStringMatch(text, pattern);
 return 0;
}
1b.#include <stdio.h>
#include<stdlib.h>
#include<time.h>
int unique(int a[],int n)
{
 int i,j;
 for(i=0;i<n-2;i++)
 {

 for(j=i+1;j<n-1;j++)
 {
 if(a[i]==a[j+1])
 return 0;
 }
 }
 return 1;
}
int main()
{
 int a[30000],i,n;
 double time_taken;
 clock_t start,end;
 printf("Enter the size of N\n");
 scanf("%d",&n);
 printf("Enter %d array elements\n",n);
 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]);
 start=clock();
 int res=unique(a,n);
 end=clock();

 if(res==0)
 printf("Array is not unique\n");
 else
 printf("Array is unique\n");
 printf("------Time Analysis-----------\n\n");
 printf("Clock Ticks-start=%d\n",start);
 printf("Clock Ticks-End=%d\n",end);
 printf("Total Clock Ticks=%d\n",(end-start));

 time_taken=((double)(end-start))/CLOCKS_PER_SEC;
 printf("Time Taken for %d elements is %f seconds\n", n,time_taken);
 return 0;
}

2.
Lab Program 2:

// Online C compiler to run C program online
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int a[10000];

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

int main() {
    int i,n;
    clock_t start,end;
    
    printf("Enter the no of elements: ");
    scanf("%d",&n);
    
    for(i=0;i<n;i++)
        a[i] = rand()%1000;
        
    start = clock();
    
    quicksort(0,n-1);
    
    end = clock();
    
    printf("Sorted elements:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
        
    printf("\n\nTime taken = %f seconds",(double)(end - start)/CLOCKS_PER_SEC);

    return 0;
}
3.
Lab Program 3:

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

int a[10000];

void merge(int low,int mid,int high){
    int i,j,k;
    int b[10000];
    
    i=low;
    j=mid+1;
    k=low;
    
    while(i<=mid && j<=high){
        if(a[i]<a[j])
            b[k++]=a[i++];
        else
            b[k++]=a[j++];
    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=high)
        b[k++]=a[j++];
        
    for(i=low;i<=high;i++)
        a[i]=b[i];
}

void mergesort(int low,int high){
    int mid;
    if(low<high){
        mid = (low+high)/2;
        
        mergesort(low,mid);
        mergesort(mid+1,high);
        
        merge(low,mid,high);
    }
}

int main() {
    int i, n;
    clock_t start, end;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    // Generate random numbers
    for(i = 0; i < n; i++)
        a[i] = rand() % 1000;

    start = clock();

    mergesort(0, n - 1);

    end = clock();

    printf("\nSorted elements:\n");

    for(i = 0; i < n; i++)
        printf("%d ", a[i]);

    printf("\n\nTime taken = %f seconds",
           (double)(end - start) / CLOCKS_PER_SEC);


    return 0;
}
4.
Program 4:

// Online C compiler to run C program online
#include <stdio.h>

int visited[10], cost[10][10];

int main() {
    
    int i,j,a,b,u,v,n;
    int min, ne = 1, mincost = 0;
    
    printf("Enter no of vertices: ");
    scanf("%d",&n);
    
    printf("Enter cost 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;
    
    while(ne<n){
        min = 999;
        for(i=1;i<=n;i++){
            if(visited[i]!=0){
                for(j=1;j<=n;j++){
                    if(visited[j]==0 && cost[i][j]<min){
                        min = cost[i][j];
                        a=u=i;
                        b=v=j;
                    }
                }
            }
        }
        
        printf("\nEdge %d: (%d %d) = %d",ne++,a,b,min);
        
        mincost+=min;
        visited[b]=1;
        
        cost[a][b] = cost[b][a] = 999;
    }
    
    printf("\nMinimum Cost = %d\n",mincost);

    return 0;
}
5.
#include <stdio.h>

int main()
{
    int n, cost[10][10], visited[10]={0};
    int i, j, min, a, b, total=0;

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&cost[i][j]);

            if(cost[i][j]==0)
                cost[i][j]=999;
        }
    }

    visited[0]=1;

    printf("Edges:\n");

    for(int k=0;k<n-1;k++)
    {
        min=999;

        for(i=0;i<n;i++)
        {
            if(visited[i])
            {
                for(j=0;j<n;j++)
                {
                    if(!visited[j] && cost[i][j]<min)
                    {
                        min=cost[i][j];
                        a=i;
                        b=j;
                    }
                }
            }
        }

        printf("%d -> %d = %d\n",a,b,min);

        total += min;
        visited[b]=1;
    }

    printf("Minimum cost = %d",total);

    return 0;
6.
#include<stdio.h>

#define MAX 10
#define INF 9999

int graph[MAX][MAX], dist[MAX], visited[MAX], n;

int min()
{
    int m = INF, pos = -1;

    for(int i = 0; i < n; i++)
    {
        if(!visited[i] && dist[i] < m)
        {
            m = dist[i];
            pos = i;
        }
    }

    return pos;
}

void dijkstra(int start)
{
    for(int i = 0; i < n; i++)
    {
        dist[i] = INF;
        visited[i] = 0;
    }

    dist[start] = 0;

    for(int i = 0; i < n - 1; i++)
    {
        int u = min();

        visited[u] = 1;

        for(int v = 0; v < n; v++)
        {
            if(graph[u][v] &&
               !visited[v] &&
               dist[u] + graph[u][v] < dist[v])
            {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

int main()
{
    int start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    printf("Enter adjacency matrix:\n");

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

    printf("Enter start vertex: ");
    scanf("%d", &start);

    dijkstra(start);

    printf("\nShortest distances:\n");

    for(int i = 0; i < n; i++)
    {
        printf("%d -> %d = %d\n",
               start, i, dist[i]);
    }

    return 0;
}
7.
#include <stdio.h>
#define MAX 100

int adj[MAX][MAX];
int visited[MAX];
int n;
int order[MAX], index;

void DFS(int v) 
{
    visited[v] = 1;
    int i;
    for(i=0; i<n; i++) 
      {
        if(adj[v][i] && !visited[i]) 
          {
            DFS(i);
          }
      }
    order[--index] = v;
}

void topological_sort() 
{
    int i;
    index = n;
    for(i=0; i<n; i++) 
     {
        visited[i] = 0;
     }

    for(i=0; i<n; i++)
    {
        if(!visited[i]) 
          {
            DFS(i);
          }
     }
}

int main() 
{
    int i, j, x, y;
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("Enter the adjacency matrix:\n");
    for(i=0; i<n; i++)
   {
        for(j=0; j<n; j++)
       {
            scanf("%d", &adj[i][j]);
        }
    }
    topological_sort();
    printf("Topological ordering of vertices:\n");
    for(i=0; i<n; i++) 
   {
        printf("%d ", order[i]);
    }
    printf("\n");
    return 0;
}
8.
#include <stdio.h>

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int n,W;

    scanf("%d",&n);

    int wt[10],val[10],dp[10][10];

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

    scanf("%d",&W);

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(i==0||j==0)
                dp[i][j]=0;

            else if(wt[i-1]<=j)
                dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j]);

            else
                dp[i][j]=dp[i-1][j];
        }
    }

    printf("%d",dp[n][W]);

    return 0;
}
9.
#include <stdio.h>

void findSubset(int S[], int n, int d, int subset[], int size, int sum);

int main () {
    int S [] = {1, 2, 5, 6, 8};
    int n = sizeof(S) / sizeof(S [0]);
    int d = 9;
    int subset[n];
    int size = 0;
    int sum = 0;
    
    findSubset(S, n, d, subset, size, sum);
    
    if (size == 0) {
        printf("No other subset found.\n");
    }
    
    return 0;
}

void findSubset(int S[], int n, int d, int subset[], int size, int sum) {
    if (sum == d) {
        printf("{");
        for (int i = 0; i < size; i++) {
            printf("%d", subset[i]);
            if (i < size - 1) {	
                printf(",");
            }
        }
        printf(“} \n");
        return;
    }
    
    if (sum > d || n == 0) {
        return;
    }
    subset[size] = S[0];
    findSubset(S + 1, n - 1, d, subset, size + 1, sum + S[0]);
    findSubset(S + 1, n - 1, d, subset, size, sum);
}
10.
#include <stdio.h>
int board[10], n;
int safe(int row, int col)
{
    for(int i = 1; i < row; i++)
    {
        if(board[i] == col ||
           (board[i] - i == col - row) ||
           (board[i] + i == col + row))
            return 0;
    }
    return 1;
}
void queen(int row)
{
    if(row > n)
    {
        printf("\nSolution:\n");

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(board[i] == j)
                    printf("Q ");
                else
                    printf(". ");
            }
            printf("\n");
        }
        return;
    }
    for(int col = 1; col <= n; col++)
    {
        if(safe(row, col))
        {
            board[row] = col;
            queen(row + 1);
        }
    }
}
int main()
{
    printf("Enter number of queens: ");
    scanf("%d", &n);
    queen(1);
    return 0;
}

