Experiment Objectives

• Deepen the understanding of the divide-and-conquer design paradigm, including its core ideas, steps, and methodologies.
• Enhance the ability to apply theoretical knowledge to solve practical computing problems.
• Improve comprehensive skills in integrating various algorithmic concepts to resolve complex tasks.

Task Overview

1. Closest Pair Problem: Given a set S of n points p1=(x1, y1), ..., pn=(xn, yn) on a plane, design an algorithm to find the pair with the smallest Euclidean distance.
   • Implement both a Brute Force approach and a Divide-and-Conquer approach.
   • Analyze time complexity and verify through experimentation.
2. Tournament Scheduling: For n = 2^k players, generate a schedule where:
   • Each player competes against every other player exactly once.
   • Each player plays at most once per day.
3. Sorting Algorithms: Implement and compare various sorting methods (Bubble, Selection, Inesrtion, Binary Insertion, Shell, Merge, Heap, Quick). Analyze time complexity and satbility.
4. Chessboard Covering: Use a divide-and-conquer strategy to cover a 2^k x 2^k chessboard with a missing square using L-shaped trominoes.

Algorithm Design and Implementation

1. Closest Pair Problem

Concept

Brute Force: Calculate the distance between every unique pair of points (i < j) and track the minimum. Complexity is O(n²).

Divide-and-Conquer: Split the points into left and right halves. The closest pair is either within the left, within the right, or straddling the dividing line. Recursively solve subproblems and check a "strip" around the division line for cross-pairs.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

struct Coordinate {
    double x_coord;
    double y_coord;
};

double calc_dist(const Coordinate& a, const Coordinate& b) {
    return hypot(a.x_coord - b.x_coord, a.y_coord - b.y_coord);
}

bool sort_by_x(const Coordinate& a, const Coordinate& b) { return a.x_coord < b.x_coord; }
bool sort_by_y(const Coordinate& a, const Coordinate& b) { return a.y_coord < b.y_coord; }

// Brute Force Approach
double brute_force_closest(const std::vector<Coordinate>& pts) {
    double min_d = std::numeric_limits<double>::max();
    int n = pts.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            min_d = std::min(min_d, calc_dist(pts[i], pts[j]));
        }
    }
    return min_d;
}

// Divide and Conquer Recursive Helper
double dc_recursive(const std::vector<Coordinate>& pts_x, int l, int r) {
    if (r - l <= 1) return calc_dist(pts_x[l], pts_x[r]);
    
    int mid = l + (r - l) / 2;
    double left_min = dc_recursive(pts_x, l, mid);
    double right_min = dc_recursive(pts_x, mid + 1, r);
    double d = std::min(left_min, right_min);

    // Check strip
    std::vector<Coordinate> strip;
    for (int i = l; i <= r; ++i) {
        if (std::abs(pts_x[i].x_coord - pts_x[mid].x_coord) < d) {
            strip.push_back(pts_x[i]);
        }
    }
    std::sort(strip.begin(), strip.end(), sort_by_y);

    for (size_t i = 0; i < strip.size(); ++i) {
        for (size_t j = i + 1; j < strip.size() && (strip[j].y_coord - strip[i].y_coord) < d; ++j) {
            d = std::min(d, calc_dist(strip[i], strip[j]));
        }
    }
    return d;
}

int main() {
    int count;
    std::cout << "Enter number of points: ";
    std::cin >> count;

    std::vector<Coordinate> points(count);
    for (int i = 0; i < count; ++i) {
        std::cout << "Enter x y for point " << i + 1 << ": ";
        std::cin >> points[i].x_coord >> points[i].y_coord;
    }

    std::sort(points.begin(), points.end(), sort_by_x);

    std::cout << "Brute Force Result: " << brute_force_closest(points) << std::endl;
    std::cout << "Divide & Conquer Result: " << dc_recursive(points, 0, count - 1) << std::endl;

    return 0;
}

2. Round-Robin Tournament Schedule

Concept

Use a recursive filling method. For 2^k players, divide the table into quadrants. Copy the top-left quadrant to the others, adjusting indices to ensure every player meets every other player exactly once.

Implementation

#include <iostream>
#include <vector>
#include <cmath>

void build_schedule(int k, std::vector<std::vector<int>>& table) {
    int n = 1 << k; // 2^k
    table.resize(n, std::vector<int>(n));

    // Base case: 2 players
    table[0][0] = 1; table[0][1] = 2;
    table[1][0] = 2; table[1][1] = 1;

    for (int size = 2; size <= k; ++size) {
        int block = 1 << size; // Current block size
        int half = block / 2;

        for (int i = 0; i < n; i += block) {
            for (int j = 0; j < n; j += block) {
                // Copy Top-Left to Bottom-Right
                for (int r = 0; r < half; ++r) {
                    for (int c = 0; c < half; ++c) {
                        table[i + r + half][j + c + half] = table[i + r][j + c];
                    }
                }
                // Copy Top-Right to Bottom-Left
                for (int r = 0; r < half; ++r) {
                    for (int c = 0; c < half; ++c) {
                        table[i + r + half][j + c] = table[i + r][j + c + half] + half;
                    }
                }
                // Copy Bottom-Left to Top-Right
                for (int r = 0; r < half; ++r) {
                    for (int c = 0; c < half; ++c) {
                        table[i + r][j + c + half] = table[i + r + half][j + c] + half;
                    }
                }
            }
        }
    }
}

int main() {
    int k_val;
    std::cout << "Enter k (n=2^k): ";
    std::cin >> k_val;

    std::vector<std::vector<int>> schedule;
    build_schedule(k_val, schedule);

    int total = 1 << k_val;
    std::cout << "Schedule for " << total << " players:\n";
    for (int i = 0; i < total; ++i) {
        for (int j = 0; j < total; ++j) {
            std::cout << schedule[i][j] << "\t";
        }
        std::cout << std::endl;
    }
    return 0;
}

3. Sorting Algorithms

Insertion Sort

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Shell Sort

void shell_sort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Selection Sort

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) min_idx = j;
        }
        std::swap(arr[min_idx], arr[i]);
    }
}

Bubble Sort

void bubble_sort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Heap Sort

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heap_sort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Merge Sort

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Quick Sort

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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

4. Chessboard Covering Problem

Concept

Given a 2^k x 2^k board with one missing square, cover the rest with L-shaped trominoes. Recursively divide the board into 4 quadrants. If the missing square is in a quadrant, recurse there. Otherwise, place a tromino in the center to create a "missing" square in the other three quadrants.

Implementation

#include <iostream>
#include <vector>

int tile_id = 1;
void cover_board(std::vector<std::vector<int>>& board, int tr, int tc, int dr, int dc, int size) {
    if (size == 1) return;
    int t = tile_id++;
    int half = size / 2;

    // Top-Left Quadrant
    if (dr < tr + half && dc < tc + half) {
        cover_board(board, tr, tc, dr, dc, half);
    } else {
        board[tr + half - 1][tc + half - 1] = t;
        cover_board(board, tr, tc, tr + half - 1, tc + half - 1, half);
    }

    // Top-Right Quadrant
    if (dr < tr + half && dc >= tc + half) {
        cover_board(board, tr, tc + half, dr, dc, half);
    } else {
        board[tr + half - 1][tc + half] = t;
        cover_board(board, tr, tc + half, tr + half - 1, tc + half, half);
    }

    // Bottom-Left Quadrant
    if (dr >= tr + half && dc < tc + half) {
        cover_board(board, tr + half, tc, dr, dc, half);
    } else {
        board[tr + half][tc + half - 1] = t;
        cover_board(board, tr + half, tc, tr + half, tc + half - 1, half);
    }

    // Bottom-Right Quadrant
    if (dr >= tr + half && dc >= tc + half) {
        cover_board(board, tr + half, tc + half, dr, dc, half);
    } else {
        board[tr + half][tc + half] = t;
        cover_board(board, tr + half, tc + half, tr + half, tc + half, half);
    }
}

int main() {
    int k_size;
    std::cout << "Enter k (Board size 2^k): ";
    std::cin >> k_size;
    int dim = 1 << k_size;

    std::vector<std::vector<int>> board(dim, std::vector<int>(dim, -1));
    
    int miss_x, miss_y;
    std::cout << "Enter missing square (x y): ";
    std::cin >> miss_x >> miss_y;
    
    board[miss_x][miss_y] = 0;
    cover_board(board, 0, 0, miss_x, miss_y, dim);

    for (int i = 0; i < dim; ++i) {
        for (int j = 0; j < dim; ++j) {
            std::cout << board[i][j] << "\t";
        }
        std::cout << std::endl;
    }
    return 0;
}

Complexity Analysis

• Closest Pair: Brute Force O(n²); Divide & Conquer O(n log n).
• Tournament Schedule: O(n²) where n = 2^k.
• Sorting:
  • Insertion, Selection, Bubble, Shell: O(n²) average/worst case.
  • Heap, Merge, Quick (average): O(n log n).
• Chessboard Covering: O(4^k) or O(n²) where n is the side length.