Randomized Algorithms

Determinisme tidak selalu menguntungkan. Untuk beberapa persoalan, algoritma deterministik terbaik punya kompleksitas buruk (mis. quicksort O(n²) worst case pada input sorted), sementara algoritma yang menggunakan keacakan bisa mencapai expected O(n log n) dengan sangat tinggi probabilitas. Randomized algorithms memanfaatkan generator angka acak untuk membuat keputusan (mis. pilih pivot, pilih sampel) sehingga kasus terburuk deterministik menjadi sangat tidak mungkin. Dua kategori utama: Las Vegas (selalu benar, waktu acak — mis. randomized quicksort) dan Monte Carlo (waktu deterministik, mungkin salah dengan probabilitas kecil — mis. primality test Fermat). Pada Chapter ini kita mengimplementasikan keduanya dalam C++.

Aturan: Las Vegas vs Monte Carlo #

Untuk Las Vegas, expected time dihitung via analisis probabilitas. Untuk Monte Carlo, probabilitas error dapat dikecilkan dengan mengulang algoritma (mis. Fermat test 20 putaran → error probability < 2^-20).

Mekanisme: Randomized Quicksort #

Quicksort deterministik dengan pivot selalu elemen pertama (atau terakhir) memiliki worst case O(n²) bila input sudah sorted. Randomized quicksort memilih pivot acak dari range [lo, hi]:

1. Pilih pivot index acak di [lo, hi].
2. Swap pivot ke posisi hi (konvensi Lomuto).
3. Partition standar: elemen < pivot di kiri, >= pivot di kanan.
4. Rekursi ke kedua sisi.

Karena pivot acak, probabilitas pivot selalu minimum/maximum = 1/n per level. Expected number of comparisons = O(n log n). Lebih penting: tidak ada input yang konsisten menghasilkan worst case — setiap kali kita menjalankan algoritma pada input yang sama, pivot berbeda, sehingga runtime bervariasi tetapi expected tetap O(n log n).

Mekanisme: Fermat Primality Test (Monte Carlo) #

Fermat’s Little Theorem: bila p prima dan gcd(a, p) = 1, maka a^(p-1) ≡ 1 (mod p).

Algoritma Fermat test: untuk n yang akan diperiksa, pilih a acak di [2, n-2]. Bila a^(n-1) mod n ≠ 1, pasti komposit. Bila = 1, mungkin prima (atau pseudoprime).

Masalah: ada Carmichael numbers (n komposit yang memenuhi Fermat untuk semua a coprime to n), mis. 561 = 3 × 11 × 17. Untuk Carmichael, Fermat bisa lolos banyak kali. Namun bila gcd(a, n) > 1 (yaitu a adalah faktor dari n), Fermat akan mendeteksi komposit. Probabilitas terambil a dengan gcd(a, n) > 1 cukup signifikan. Untuk 561: ada 561 - 320 = 241 dari 559 a yang tidak coprime, sehingga ~43% per round mendeteksi komposit. Dengan 20 rounds, probability salah ≈ (4/7)^20 ≈ 10^-4.

Lebih aman: Miller-Rabin test yang tidak tertipu Carmichael. Untuk demo, kita pakai Fermat.

Implementasi C++ #

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

// Randomized quicksort dengan random pivot
// Las Vegas: always correct, expected O(n log n)

std::mt19937 rng(42);

int partition(std::vector<int>& arr, int lo, int hi) {
    // Pilih pivot acak dari [lo, hi]
    int pivot_idx = std::uniform_int_distribution<int>(lo, hi)(rng);
    int pivot_val = arr[pivot_idx];
    std::swap(arr[pivot_idx], arr[hi]);
    int i = lo;
    for (int j = lo; j < hi; ++j) {
        if (arr[j] < pivot_val) {
            std::swap(arr[i], arr[j]);
            ++i;
        }
    }
    std::swap(arr[i], arr[hi]);
    return i;
}

void randomized_quicksort(std::vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    randomized_quicksort(arr, lo, p - 1);
    randomized_quicksort(arr, p + 1, hi);
}

// Monte Carlo: primality test via Fermat's little theorem
// Could give wrong answer with probability <= 1/2 per round
long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

bool fermat_test(long long n, int rounds = 20) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    std::uniform_int_distribution<long long> dist(2, n - 2);
    for (int i = 0; i < rounds; ++i) {
        long long a = dist(rng);
        if (power_mod(a, n - 1, n) != 1) return false;
    }
    return true;  // probably prime
}

int main() {
    std::vector<int> arr = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0, 5, 8, 2, 3, 1};
    std::cout << "Sebelum sort: ";
    for (int x : arr) std::cout << x << ' ';
    std::cout << '\n';

    randomized_quicksort(arr, 0, (int)arr.size() - 1);
    std::cout << "Setelah randomized quicksort: ";
    for (int x : arr) std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "\nFermat primality test (Monte Carlo):\n";
    long long nums[] = {2, 7, 15, 17, 19, 561, 1000003, 1000000007};
    for (long long n : nums) {
        std::cout << "  " << n << " is " << (fermat_test(n) ? "probably prime" : "composite") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Sebelum sort: 5 2 8 1 9 3 7 4 6 0 5 8 2 3 1 
Setelah randomized quicksort: 0 1 1 2 2 3 3 4 5 5 6 7 8 8 9 

Fermat primality test (Monte Carlo):
  2 is probably prime
  7 is probably prime
  15 is composite
  17 is probably prime
  19 is probably prime
  561 is composite
  1000003 is probably prime
  1000000007 is probably prime

Bedah Kode Baris-per-Baris #

1. std::mt19937 rng(42): Mersenne Twister, PRNG berkualitas tinggi. Seed 42 agar reproducible (untuk demo). Pada produksi, gunakan std::random_device() sebagai seed untuk keacakan sebenarnya.
2. std::uniform_int_distribution<int>(lo, hi)(rng): menghasilkan integer uniform di [lo, hi]. Pakai ini, bukan rand() % (hi - lo + 1), karena rand() distribusinya tidak uniform dan rentan bias.
3. pivot_idx = uniform_int_distribution(lo, hi)(rng): pilih pivot acak. Inilah inti randomized quicksort — pivot tidak deterministik, sehingga tidak ada input yang konsisten menghasilkan worst case.
4. std::swap(arr[pivot_idx], arr[hi]): pindahkan pivot ke posisi hi (konvensi Lomuto). Sisanya partition standar: scan j di [lo, hi-1], bila arr[j] < pivot_val, swap ke posisi i dan increment i. Akhirnya swap pivot dari hi ke i (posisi final).
5. randomized_quicksort rekursif: identik quicksort biasa, hanya partition yang random. Expected time O(n log n) (analisis via probability bahwa pivot balance).
6. power_mod(base, exp, mod): modular exponentiation cepat via binary exponentiation. O(log exp) per pangkat. __int128 dipakai untuk menghindari overflow saat multiply dua long long mod 10^18.
7. fermat_test(n, rounds=20): untuk setiap round, pilih a acak, cek a^(n-1) mod n == 1. Bila tidak, return false (pasti komposit). Bila semua round lolos, return true (mungkin prima).
8. std::uniform_int_distribution<long long> dist(2, n-2): distribusi long long. Perlu long long karena n bisa 10^18.
9. Verifikasi quicksort: input {5,2,8,1,9,3,7,4,6,0,5,8,2,3,1} sorted menjadi {0,1,1,2,2,3,3,4,5,5,6,7,8,8,9}. ✓
10. Verifikasi Fermat:
    • 2, 7, 17, 19, 1000003, 1000000007 semua prima → “probably prime”. ✓
    • 15 = 3 × 5 komposit → “composite”. ✓
    • 561 = 3 × 11 × 17 adalah Carmichael number. Fermat test dengan 20 round acak mendeteksi komposit (karena ~43% per round memilih a dengan gcd(a, 561) > 1). ✓

Kompleksitas dan Perbandingan #

Aplikasi #

1. Hashing randomized (Rabin-Karp, rolling hash dengan random base): menghindari adversarial collision.
2. Randomized bipartite matching: pilih order node acak, jalankan augmenting path. Expected O(VE) tetapi konstanta kecil.
3. Karger’s min-cut algorithm: random edge contraction. Dengan iterasi O(n² log n), probability menemukan min cut mendekati 1.
4. Skip list: linked list probabilistik dengan expected O(log n) search.
5. Bloom filter: probabilistic membership test, false positive dengan probabilitas dapat diatur.
6. Randomized load balancing: distribusi beban server dengan hash acak.

Ringkasan #

• Randomized algorithm memakai keacakan untuk membuat keputusan.
• Las Vegas: selalu benar, expected time (mis. randomized quicksort O(n log n) expected).
• Monte Carlo: waktu deterministik, mungkin salah dengan probabilitas kecil (mis. Fermat test,Miller-Rabin).
• Randomized quicksort: pilih pivot acak → tidak ada input yang konsisten menghasilkan worst case O(n²).
• Fermat primality test: a^(n-1) ≡ 1 (mod n). Tertipu Carmichael number. Miller-Rabin lebih aman.
• std::mt19937 + std::uniform_int_distribution adalah pilihan PRNG yang tepat (bukan rand()).
• Aplikasi: hashing, Karger min-cut, Bloom filter, skip list, randomized load balancing.