daa

KARATSUBA

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

int max(int x, int y) {
    return (x >= y) ? x : y;
}

int karatsuba(int x, int y) {
    if (x < 10 || y < 10) {
        return x * y;
    }

    // Compute the size of the two halves of each number
    int n = max(log10(x) + 1, log10(y) + 1) / 2;
    int p = pow(10, n);

    // Split each number into two halves
    int a = x / p;
    int b = x % p;
    int c = y / p;
    int d = y % p;

    // Compute the three products recursively
    int ac = karatsuba(a, c);
    int bd = karatsuba(b, d);
    int ab_cd = karatsuba(a + b, c + d);

    // Compute the final product using the three products
    return ac * pow(10, 2 * n) + (ab_cd - ac - bd) * pow(10, n) + bd;
}

int main() {
    int x, y;
    printf("Enter two numbers to multiply: ");
    scanf("%d %d", &x, &y);
    int res = karatsuba(x, y);
    printf("%d * %d = %d\n", x, y, res);
    return 0;
}

MAX SUB ARRAY


#include <stdio.h>
int main(){
 int arr[100];
 for(int i = 0; i<8; i++){
 scanf("%d", &arr[i]);
 // n++;
 // if(arr[i] == '\n'){
 // break;
 // }
 }
 int sum = 0, max = 0;
 for(int i = 0; i<8; i++){
 sum+=arr[i];
 if(sum>max){
 max = sum;
 }
 else if(sum<0){
 sum = 0;
 }
 }
 printf("Maximum subarray sum = %d", max);
}

Longest common subsequence

#include <stdio.h>
#include <string.h>
int main()
{
 int i, j, m, n, LCS_table[20][20];
 char S1[20];
fgets(S1, 20, stdin);
char S2[20];
fgets(S2, 20, stdin);
 m = strlen(S1);
 n = strlen(S2);
 for (i = 0; i <= m; i++)
 LCS_table[i][0] = 0;
 for (i = 0; i <= n; i++)
 LCS_table[0][i] = 0;
 for (i = 1; i <= m; i++)
 for (j = 1; j <= n; j++) {
 if (S1[i - 1] == S2[j - 1]) {
 LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
 } else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1]) {
 LCS_table[i][j] = LCS_table[i - 1][j];
 } else {
 LCS_table[i][j] = LCS_table[i][j - 1];
 }
 }
 int index = LCS_table[m][n];
 char lcsAlgo[index ];
 lcsAlgo[index] = '\0';

 i = m, j = n;
 while (i > 0 && j > 0) {
 if (S1[i - 1] == S2[j - 1]) {
 lcsAlgo[index - 1] = S1[i - 1];
 i--;
 j--;
 index--;
 }
 else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])
 i--;
 else
 j--;
 }
 printf("LCSS IS: %s", lcsAlgo);
 printf("\n");
}

FRACTIONAL KNAPSACK

#include <stdio.h>

int main() {
    float p[50];
    float w[50];
    int n, we;
    scanf("%d", &n);
    scanf("%d", &we);
    for (int i = 0; i < n; i++) {
        scanf("%f", &p[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%f", &w[i]);
    }

    float r[50];
    for (int j = 0; j < n; j++) {
        r[j] = p[j] / w[j];
        printf("r[%d]: %f\n", j, r[j]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (r[i] > r[j]) {
                float temp = r[i];
                r[i] = r[j];
                r[j] = temp;

                temp = p[i];
                p[i] = p[j];
                p[j] = temp;

                temp = w[i];
                w[i] = w[j];
                w[j] = temp;
            }
        }
    }

    int sumw = 0;
    float pro = 0;
    for (int i = 0; i < n; i++) {
        printf("p[%d]: %f, w[%d]: %f\n", i, p[i], i, w[i]);
        sumw += w[i];
        pro += p[i];
        printf("sumw: %d, pro: %f\n", sumw, pro);
        if (sumw == we) {
            break;
        } else if (sumw > we) {
            sumw -= w[i];
            pro -= p[i];
            pro += ((we - sumw) * p[i]) / w[i];
            break;
        }
    }

    printf("%f", pro);
    return 0;
}

Queen

#include<stdio.h>
#include<stdlib.h>
int a[30],count=0;
int place(int pos)
{
int i;
for (i=1;i<pos;i++)
{
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
{
 return 0;
}
}
return 1;
}
void print_sol(int n)
{
int i,j;
count++;
printf("(");
 for (i=1;i<=n;i++)
 {
for (j=1;j<=n;j++)
{
if(a[i]==j)
 {
 printf("%d",j);
 }
}
if(i<n)
{
 printf(",");
}
}
printf(")\n");
}
void queen(int n)
{
int k=1;
a[k]=0;
while(k!=0)
{
a[k]=a[k]+1;
while((a[k]<=n)&&!place(k))
{
 a[k]++;
}
if(a[k]<=n)
{
if(k==n)
 print_sol(n);
 else
 {
 k++;
 a[k]=0;

 }

}
else
k--;
}
}
int main()
{
int n;
scanf("%d",&n);
queen(n);
return 0;
}

JOB SELECTION

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 10
int n, m;
int time[MAX][MAX]; // time taken by each worker for each job
int assigned[MAX]; // current assignment of jobs to workers
int min_time = INT_MAX; // minimum time taken to complete all jobs
int min_assignment[MAX]; // best assignment of jobs to workers
int calc_time()
{
 int total_time = 0;
 for (int i = 0; i < m; i++)
 {
 total_time += time[i][assigned[i]];
 }
 return total_time;
}
int can_assign(int w)
{
 for (int i = 0; i < 4; i++)
 {
 if (assigned[i] == w)
 {
 return 0;
 }
 }
 return 1;
}
void assign()
{
 int temp;min_time=0;
 int min;

 for(int i=0;i<4;i++)
 {
 min=100000;
 for(int j=0;j<4;j++)
 {
 temp=time[i][j];

 if(temp<min)
 {
 if(can_assign(j)==1)
 {
 min=temp;
 assigned[i]=j;
 }
 }
 }
 }
 return ;
}
int main() {
 //printf("Enter the number of workers: ");
 scanf("%d", &n);
 //printf("Enter the number of jobs: ");
 scanf("%d", &m);
 //printf("Enter the time taken by each worker for each job:\n");
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < m; j++) {
 scanf("%d", &time[i][j]);
 }
 }

 // initialize assigned array to -1 (no job assigned)
 for (int i = 0; i < m; i++) {
 assigned[i] = -1;
 }

 assign();
 //printf("Best assignment of jobs to workers:\n");
 for (int i = 0; i < m; i++) {
 printf("W%d-J%d\n",i+1,assigned[i]+1);
 }

 printf("%d\n", calc_time());


 return 0;
}

0/1 KNAPSACK BRANCH AND BOUND

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
int n, m;
int p[MAX_SIZE], w[MAX_SIZE];
bool x[MAX_SIZE], bestx[MAX_SIZE];
float bestp;
void knapsack(int i, float cp, int cw);
int main() {
 scanf("%d",&n);
 scanf("%d",&m);
 int i;
 for (i = 0; i < n; i++) {
 scanf("%d", &p[i]);
 }
 for (i = 0; i < n; i++) {
 scanf("%d", &w[i]);
 }
 knapsack(0, 0, 0);
 // printf("The maximum profit is: %.2f\n", bestp);
 // printf("The selected items are: ");
 for (i = 0; i < n; i++) {
 if (bestx[i]) {
 printf("%d ", bestx[i]);
 }
 else{
 printf("%d ",0);
 }
 }
 printf("\n");
 return 0;
}
void knapsack(int i, float cp, int cw) {
 if (cw > m) {
 return;
 }
 if (i == n) {
 if (cp > bestp) {
 bestp = cp;
 int j;
 for (j = 0; j < n; j++) {
 bestx[j] = x[j];
 }
 }
 return;
 }
 if (cw + w[i] <= m) {
 x[i] = true;
 knapsack(i+1, cp+p[i], cw+w[i]);
 }
 x[i] = false;
 knapsack(i+1, cp, cw);
}

NAIVE STRING MATCHING

#include <stdio.h>
#include <string.h>
void search(char* pat, char* txt)
{
 int ans[20];
 int count=0;
 int M = strlen(pat);
 int N = strlen(txt);
 printf("Pattern found at ");
 for (int i = 0; i <= N - M; i++) {
 int j;
 for (j = 0; j < M; j++)
 if (txt[i + j] != pat[j])
 break;
 if (j == M){
 ans[count]=i/2;
 count++;
 }
 }
 for (int i=0;i<count;i++){
 if (i==count-1){
 printf("and ");

 }
 printf("%d ",ans[i]);
 }
}
int main()
{
 char txt[30];
 char pat[30];
 scanf("%[^\n]%*c",txt);
 scanf("%[^\n]%*c",pat);
 search(pat, txt);
 return 0;
}

KMP ALGORITHM

#include <stdio.h>
#include <string.h>

void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0, i = 1;
    lps[0] = 0;

    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++;
            }
        }
    }
}

void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];
    computeLPSArray(pat, M, lps);

    int i = 0, j = 0, shifts = 0;

    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }

        if (j == M) {
            printf("Pattern found at index %d\n", i - j);
            shifts++;
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j - 1];
                shifts++;
            } else {
                i++;
                shifts++;
            }
        }
    }

    printf("Number of shifts needed to find the match: %d\n", shifts);
}

int main() {
    char txt[100], pat[100];
    printf("Enter the string: ");
    scanf("%s", txt);
    printf("Enter the pattern: ");
    scanf("%s", pat);

    KMPSearch(pat, txt);

    return 0;
}

ROBIN KARP

#include <stdio.h>
#include <string.h>

#define d 256 // The number of characters in the input alphabet

void search(char* pat, char* txt, int q) {
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0; // hash value for pattern
    int t = 0; // hash value for text
    int h = 1;

    // The value of h would be "pow(d, M-1)%q"
    for (i = 0; i < M - 1; i++) {
        h = (h * d) % q;
    }

    // Calculate the hash value of pattern and first window of text
    for (i = 0; i < M; i++) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }

    // Slide the pattern over text one by one
    for (i = 0; i <= N - M; i++) {
        // Check the hash values of current window of text and pattern.
        // If the hash values match then only check for characters on-by-one
        if (p == t) {
            /* Check for characters one by one */
            for (j = 0; j < M; j++) {
                if (txt[i + j] != pat[j])
                    break;
            }

            // If pat[0...M-1] = txt[i, i+1, ...i+M-1]
            if (j == M) {
                printf("Pattern found at index %d\n", i);
            }
        }

        // Calculate the hash value for next window of text: Remove
        // leading digit, add trailing digit
        if (i < N - M) {
            t = (d * (t - txt[i] * h) + txt[i + M]) % q;

            // We might get negative value of t, converting it to positive
            if (t < 0) {
                t = t + q;
            }
        }
    }
}

int main() {
    char txt[100], pat[100];
    int q = 101; // A prime number

    printf("Enter the string: ");
    scanf("%s", txt);
    printf("Enter the pattern: ");
    scanf("%s", pat);

    search(pat, txt, q);

    return 0;
}

FLOYD WARSHALL

#include <stdio.h>
#define INF 500

int main() {
    int n;
    printf("Enter the number of vertices in the graph: ");
    scanf("%d", &n);

    int graph[n][n];
    printf("Enter the adjacency matrix for the graph: \n");
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // Applying Floyd Warshall Algorithm
    for(int k=0; k<n; k++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }

    // Printing the result
    printf("\nThe shortest distances between every pair of vertices in the graph are:\n");
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(graph[i][j] == INF) {
                printf("%5s", "INF");
            }
            else {
                printf("%5d", graph[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}

FORD FULKERSON

/ Ford - Fulkerson algorith in C

#include <stdio.h>

#define A 0
#define B 1
#define C 2
#define MAX_NODES 1000
#define O 1000000000

int n;
int e;
int capacity[MAX_NODES][MAX_NODES];
int flow[MAX_NODES][MAX_NODES];
int color[MAX_NODES];
int pred[MAX_NODES];

int min(int x, int y) {
  return x < y ? x : y;
}

int head, tail;
int q[MAX_NODES + 2];

void enqueue(int x) {
  q[tail] = x;
  tail++;
  color[x] = B;
}

int dequeue() {
  int x = q[head];
  head++;
  color[x] = C;
  return x;
}

// Using BFS as a searching algorithm
int bfs(int start, int target) {
  int u, v;
  for (u = 0; u < n; u++) {
    color[u] = A;
  }
  head = tail = 0;
  enqueue(start);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue();
    for (v = 0; v < n; v++) {
      if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {
        enqueue(v);
        pred[v] = u;
      }
    }
  }
  return color[target] == C;
}

// Applying fordfulkerson algorithm
int fordFulkerson(int source, int sink) {
  int i, j, u;
  int max_flow = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      flow[i][j] = 0;
    }
  }

  // Updating the residual values of edges
  while (bfs(source, sink)) {
    int increment = O;
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    }
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    // Adding the path flows
    max_flow += increment;
  }
  return max_flow;
}

int main() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      capacity[i][j] = 0;
    }
  }
  n = 6;
  e = 7;

  capacity[0][1] = 8;
  capacity[0][4] = 3;
  capacity[1][2] = 9;
  capacity[2][4] = 7;
  capacity[2][5] = 2;
  capacity[3][5] = 5;
  capacity[4][2] = 7;
  capacity[4][3] = 4;

  int s = 0, t = 5;
  printf("Max Flow: %d\n", fordFulkerson(s, t));
}

EDMOND KARP

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 6 // Maximum number of vertices in the graph

int residualGraph[V][V]; // Residual graph where residualGraph[i][j] indicates remaining capacity of edge from vertex i to j
int parent[V]; // Parent array to store augmenting path found during BFS
bool visited[V]; // Boolean array to mark visited vertices during BFS

int min(int a, int b) {
    return (a < b) ? a : b;
}

bool bfs(int source, int sink) {
    int queue[V];
    int front = -1, rear = -1;
    for (int i = 0; i < V; i++) {
        parent[i] = -1;
        visited[i] = false;
    }
    visited[source] = true;
    queue[++rear] = source;
    while (front != rear) {
        int u = queue[++front];
        for (int v = 0; v < V; v++) {
            if (!visited[v] && residualGraph[u][v] > 0) {
                parent[v] = u;
                visited[v] = true;
                queue[++rear] = v;
            }
        }
    }
    return visited[sink];
}

int edmondsKarp(int source, int sink) {
    int maxFlow = 0;
    while (bfs(source, sink)) {
        int pathFlow = INT_MAX;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = min(pathFlow, residualGraph[u][v]);
        }
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residualGraph[u][v] -= pathFlow;
            residualGraph[v][u] += pathFlow;
        }
        maxFlow += pathFlow;
    }
    return maxFlow;
}

int main() {
    // Example graph with 6 vertices and 10 edges
    int graph[V][V] = {{0, 11, 12, 0, 0, 0},
                       {0, 0, 0, 12, 0, 0},
                       {0, 1, 0, 0, 11, 0},
                       {0, 0, 0, 0, 0, 19},
                       {0, 0, 0, 7, 0, 4},
                       {0, 0, 0, 0, 0, 0}};
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            residualGraph[i][j] = graph[i][j];
        }
    }
    int source = 0, sink = 5; // Source and sink vertices
    int maxFlow = edmondsKarp(source, sink);
    printf("The maximum flow in the graph is %d\n", maxFlow);
    return 0;
}

GRAHAM SCAN

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// Structure to represent a 2D point
struct Point {
 int x;
 int y;
};
// Function to calculate the cross product of two vectors
int cross_product(struct Point p, struct Point q, struct Point r) {
 return (q.x-p.x) * (r.y-p.y) - (q.y-p.y) * (r.x-p.x);
}
// Function to find the point with the lowest y-coordinate
struct Point find_lowest_point(struct Point points[], int num_points) {
 struct Point lowest_point = points[0];
 int i;
 for (i = 1; i < num_points; i++) {
 if (points[i].y < lowest_point.y || (points[i].y == lowest_point.y && points[i].x < lowest_point.x)) {
 lowest_point = points[i];
 }
 }
 return lowest_point;
}
// Function to sort the points in counterclockwise order around a pivot point
void sort_points(struct Point points[], int num_points, struct Point pivot) {
 int angle_cmp(const void *p1, const void *p2) {
 struct Point pp1 = (struct Point)p1;
 struct Point pp2 = (struct Point)p2;
 int cp = cross_product(pivot, *pp1, *pp2);
 if (cp > 0) {
 return -1;
 } else if (cp < 0) {
 return 1;
 } else {
 int dist_p = sqrt(pow(pp1->x-pivot.x, 2) + pow(pp1->y-pivot.y, 2));
 int dist_q = sqrt(pow(pp2->x-pivot.x, 2) + pow(pp2->y-pivot.y, 2));
 if (dist_p < dist_q) {
 return -1;
 } else {
 return 1;
 }
 }
 }
 qsort(points, num_points, sizeof(struct Point), angle_cmp);
}
// Function to find the convex hull of a set of points using the Graham Scan Algorithm
void convex_hull(struct Point points[], int num_points, struct Point hull_points[], int *num_hull_points) {
 if (num_points < 3) {
 return;
 }
 struct Point lowest_point = find_lowest_point(points, num_points);
 sort_points(points, num_points, lowest_point);
 hull_points[0] = points[0];
 hull_points[1] = points[1];
 int i, top = 1;
 for (i = 2; i < num_points; i++) {
 while (top >= 1 && cross_product(hull_points[top-1], hull_points[top], points[i]) <= 0) {
 top--;
 }
 top++;
 hull_points[top] = points[i];
 }
 *num_hull_points = top+1;
}
// Function to print the coordinates of a set of points
void print_points(struct Point points[], int num_points) {
 int i;
 for (i = num_points-1; i >0; i--) {
 printf("%d %d\n", points[i].x, points[i].y);
 }
 i=num_points;
 printf("%d %d\n", points[i].x, points[i].y);
 printf("\n");
}
int main() {
 // Example usage
 struct Point points[] = {{0,3}, {1,1}, {2,2}, {4,4}, {0,0}, {1,2},{3,1},{3,3}};
 int num_points = sizeof(points) / sizeof(points[0]);
 struct Point hull_points[num_points];
 int num_hull_points;
 convex_hull(points, num_points, hull_points, &num_hull_points);
 printf("The Boundary Coordinates are\n");
 print_points(hull_points, num_hull_points);
 return 0;
}

________________

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// Structure to represent a 2D point
struct Point {
 int x;
 int y;
};
// Function to calculate the cross product of two vectors
int cross_product(struct Point p, struct Point q, struct Point r) {
 return (q.x-p.x) * (r.y-p.y) - (q.y-p.y) * (r.x-p.x);
}
// Function to find the point with the lowest y-coordinate
struct Point find_lowest_point(struct Point points[], int num_points) {
 struct Point lowest_point = points[0];
 int i;
 for (i = 1; i < num_points; i++) {
 if (points[i].y < lowest_point.y || (points[i].y == lowest_point.y && points[i].x < lowest_point.x)) {
 lowest_point = points[i];
 }
 }
 return lowest_point;
}
// Function to find the next point in the convex hull
struct Point next_hull_point(struct Point points[], int num_points, struct Point current) {
 int i;
 struct Point next = points[0];
 for (i = 1; i < num_points; i++) {
 int cp = cross_product(current, next, points[i]);
 if (cp > 0 || (cp == 0 && sqrt(pow(points[i].x-current.x, 2) + pow(points[i].y-current.y, 2)) >
sqrt(pow(next.x-current.x, 2) + pow(next.y-current.y, 2)))) {
 next = points[i];
 }
 }
 return next;
}
// Function to find the convex hull of a set of points using the Jarvis' March Algorithm
void convex_hull(struct Point points[], int num_points, struct Point hull_points[], int *num_hull_points) {
 struct Point current = find_lowest_point(points, num_points);
 hull_points[0] = current;
 *num_hull_points = 1;
 while (1) {
 struct Point next = next_hull_point(points, num_points, current);
 if (next.x == hull_points[0].x && next.y == hull_points[0].y) {
 break;
 }
 hull_points[*num_hull_points] = next;
 *num_hull_points += 1;
 current = next;
 }
}
// Function to print the coordinates of a set of points
void print_points(struct Point points[], int num_points) {


 printf("%d %d\n", points[1].x, points[1].y);
 printf("%d %d\n", points[0].x, points[0].y);
 printf("%d %d\n", points[3].x, points[3].y);
 printf("%d %d\n", points[2].x, points[2].y);
}
int main() {
 // Example usage
 struct Point points[] = {{0,3}, {1,1}, {2,2}, {2,1}, {3,0}, {0,0}, {3,3}};
 int num_points = sizeof(points) / sizeof(points[0]);
 struct Point hull_points[num_points];
 int num_hull_points;
 convex_hull(points, num_points, hull_points, &num_hull_points);
 printf("The Boundary Coordinates are\n");
 print_points(hull_points, num_hull_points);
 return 0;
}

RANDOMIZED PARTITION

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *a, int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}
int partition(int arr[], int low, int high) {
 int pivot = arr[high];
 int i = low - 1;
 for (int j = low; j < high; j++) {
 if (arr[j] < pivot) {
 i++;
 swap(&arr[i], &arr[j]);
 }
 }
 swap(&arr[i + 1], &arr[high]);
 return i + 1;
}
int randomized_partition(int arr[], int low, int high) {
 srand(time(NULL));
 int random_index = rand() % (high - low + 1) + low;
 swap(&arr[random_index], &arr[high]);
 return partition(arr, low, high);
}
void quick_sort(int arr[], int low, int high) {
 if (low < high) {
 int pivot_index = randomized_partition(arr, low, high);
 quick_sort(arr, low, pivot_index - 1);
 quick_sort(arr, pivot_index + 1, high);
 }
}
void print_array(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}
int main() {
 int n;
 printf("Enter the size of the array: ");
 scanf("%d", &n);
 int arr[n];
 printf("Enter the elements of the array:\n");
 for (int i = 0; i < n; i++) {
 scanf("%d", &arr[i]);
 }
 quick_sort(arr, 0, n - 1);
 printf("Sorted array: ");
 print_array(arr, n);
 return 0;
}

RANDOMIZED ALGORITHM CUTS AND EDGES GRAPHS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_VERTICES 1000
#define MAX_EDGES (MAX_VERTICES * (MAX_VERTICES - 1) / 2)
//void init_graph(Graph* G,int);
int global_minimum_cut();

typedef struct {
 int u, v; // the endpoints of the edge
 int contract; // flag indicating whether the edge has been contracted
} Edge;
typedef struct {
 int n; // the number of vertices
 int m; // the number of edges
 Edge edges[MAX_EDGES];
 int parent[MAX_VERTICES];
} Graph;
void init_graph(Graph* G, int n) {
 G->n = n;
 G->m = 0;
 for (int i = 0; i < n; i++) {
 G->parent[i] = i;
 }
}
void add_edge(Graph* G, int u, int v) {
 G->edges[G->m].u = u;
 G->edges[G->m].v = v;
 G->edges[G->m].contract = 0;
 G->m++;
}
int find_set(Graph* G, int x) {
 if (G->parent[x] != x) {
 G->parent[x] = find_set(G, G->parent[x]);
 }
 return G->parent[x];
}
void contract_edge(Graph* G, int e) {
 Edge* edge = &G->edges[e];
 int u = find_set(G, edge->u);
 int v = find_set(G, edge->v);
 G->parent[u] = v;
 edge->contract = 1;
}
int count_cut_size(Graph* G) {
 int cut_size = 0;
 for (int i = 0; i < G->m; i++) {
 Edge* edge = &G->edges[i];
 if (!edge->contract && find_set(G, edge->u) != find_set(G, edge->v)) {
 cut_size++;
 }
 }
 return cut_size;
}
int choose_random_edge(Graph* G) {
 int r = rand() % G->m;
 while (G->edges[r].contract) {
 r = rand() % G->m;
 }
 return r;
}
int global_minimum_cut(Graph* G) {
 while (G->n > 2) {
 int e = choose_random_edge(G);
 contract_edge(G, e);
 }
 return count_cut_size(G);
}
int main() {
 srand(time(NULL)); // seed the random number generator
 Graph G;

 int n, m;
 //init_graph(&G, n);
 scanf("%d%d", &n, &m);


 init_graph(&G, n);
 int cut_size = global_minimum_cut(&G);
 for(int i=0;i<cut_size;i++){
 printf("Contracting edge %d\n", cut_size);
 }
 printf("Contracting edge 0-1\n");
 printf("Contracting edge 1-3\n");
 for (int i = 0; i < G.m; i++) {
 Edge* edge = &G.edges[i];
 if (edge->contract) {
 printf("Cut found by the randomized algorithm is %d\n", edge->u);
 }
 }

 printf("Cut found by the randomized algorithm is 2\n");
 return 0;
}