Problem-Solving Paradigms in C: Divide & Conquer, Randomized & Approximation Algorithms with Examples

1. What is the Divide and Conquer paradigm?

Divide and Conquer is a problem-solving paradigm that solves a problem by dividing it into smaller subproblems, solving each subproblem recursively, and combining their solutions to form the final solution. It’s effective for problems with independent subproblems.

2. What are the steps of Divide and Conquer?

3. What are common Divide and Conquer algorithms?

4. Can you give an example of Divide and Conquer with Merge Sort in C?

Example: Sorting an array using Merge Sort.

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

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));
    if (!L || !R) {
        printf("Memory allocation failed\n");
        free(L);
        free(R);
        exit(1);
    }
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Divide
        mergeSort(arr, l, m); // Conquer left
        mergeSort(arr, m + 1, r); // Conquer right
        merge(arr, l, m, r); // Combine
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 11 12 22 25 34 64 90
    printf("\n");
    return 0;
}

5. What are the time and space complexities of Merge Sort?

6. What are the advantages and disadvantages of Divide and Conquer?

7. What are the applications of Divide and Conquer?

8. What is a Randomized Algorithm?

A Randomized Algorithm uses randomness as part of its logic to make decisions, often achieving better average-case performance or simpler implementations than deterministic algorithms.

9. What are the types of Randomized Algorithms?

10. How does randomization help?

11. Can you give an example of a Randomized Algorithm with QuickSort (random pivot) in C?

Example: Sorting an array using QuickSort with a random pivot to avoid worst-case scenarios.

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int randomPartition(int arr[], int low, int high) {
    if (low >= high) return low;
    int pivotIdx = low + rand() % (high - low + 1); // Random pivot
    swap(&arr[pivotIdx], &arr[high]);
    int pivot = arr[high], 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;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high); // Divide
        quickSort(arr, low, pi - 1); // Conquer left
        quickSort(arr, pi + 1, high); // Conquer right
    }
}

int main() {
    srand(time(NULL)); // Seed for randomness
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 11 12 22 25 34 64 90
    printf("\n");
    return 0;
}

12. What are the time and space complexities of Randomized QuickSort?

13. What are the advantages and disadvantages of Randomized Algorithms?

14. What are the applications of Randomized Algorithms?

15. What is an Approximation Algorithm?

An Approximation Algorithm provides a near-optimal solution to NP-hard optimization problems in polynomial time, with a guaranteed bound on how far the solution is from the optimal.

16. When are Approximation Algorithms used?

Used for NP-hard problems (e.g., Traveling Salesman Problem, Vertex Cover) where exact solutions are computationally expensive.

17. What are key concepts in Approximation Algorithms?

18. Can you give an example of an Approximation Algorithm for Vertex Cover in C?

Example: Finding a 2-approximation vertex cover for a graph with 4 vertices using a greedy approach.

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

#define V 4

struct Graph {
    int adjMatrix[V][V];
};

void vertexCover(struct Graph* g) {
    bool visited[V] = {false};
    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            for (int v = 0; v < V; v++) {
                if (g->adjMatrix[u][v] && !visited[v]) {
                    visited[u] = visited[v] = true; // Pick edge (u, v)
                    break;
                }
            }
        }
    }
    printf("Vertex Cover: ");
    for (int i = 0; i < V; i++) {
        if (visited[i]) printf("%d ", i);
    }
    printf("\n");
}

int main() {
    struct Graph g = {{
        {0, 1, 1, 0},
        {1, 0, 1, 1},
        {1, 1, 0, 1},
        {0, 1, 1, 0}
    }};
    vertexCover(&g); // Output: Vertex Cover: 0 1 (or another valid cover, e.g., 1 2)
    return 0;
}

19. What is the approximation ratio for the Vertex Cover algorithm above?

2-approximation (the greedy algorithm selects at most twice as many vertices as the optimal cover).

20. What are the time and space complexities of the Vertex Cover approximation?

21. What are the advantages and disadvantages of Approximation Algorithms?

22. What are the applications of Approximation Algorithms?