Randomized Algorithm Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Randomized quicksort: always correct; running time is a random variable.
5
// Expected time: O(n log n); Space: O(log n) recursion depth (expected).
6
7
static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
8
9
int partition_random(vector<int>& a, int l, int r) {
10
    uniform_int_distribution<int> dist(l, r);
11
    int pivotIndex = dist(rng);           // choose pivot uniformly at random
12
    int pivot = a[pivotIndex];
13
    swap(a[pivotIndex], a[r]);            // move pivot to end
14
    int i = l;
15
    for (int j = l; j < r; ++j) {
16
        if (a[j] <= pivot) {
17
            swap(a[i++], a[j]);
18
        }
19
    }
20
    swap(a[i], a[r]);                     // place pivot in final position
21
    return i;
22
}
23
24
void quicksort(vector<int>& a, int l, int r) {
25
    if (l >= r) return;
26
    int p = partition_random(a, l, r);
27
    // Recurse on smaller side first to keep recursion depth small in practice
28
    if (p - 1 - l < r - (p + 1)) {
29
        quicksort(a, l, p - 1);
30
        quicksort(a, p + 1, r);
31
    } else {
32
        quicksort(a, p + 1, r);
33
        quicksort(a, l, p - 1);
34
    }
35
}
36
37
int main() {
38
    ios::sync_with_stdio(false);
39
    cin.tie(nullptr);
40
41
    vector<int> a = {9, 1, 5, 3, 7, 2, 8, 6, 4, 0};
42
    quicksort(a, 0, (int)a.size() - 1);
43
44
    for (int x : a) cout << x << ' ';
45
    cout << "\n";
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Miller–Rabin primality test with random bases.
5
// One-sided error: never declares a prime composite; may label a composite as "probably prime" with probability <= 4^{-k}.
6
// Works for 64-bit integers as a demo using __int128 for safe modular multiplication.
7
8
static mt19937_64 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
9
10
using u128 = unsigned __int128;
11
using u64 = uint64_t;
12
13
u64 mul_mod(u64 a, u64 b, u64 mod) {
14
    return (u128)a * b % mod; // relies on 128-bit intermediate
15
}
16
17
u64 pow_mod(u64 a, u64 d, u64 mod) {
18
    u64 res = 1 % mod;
19
    u64 base = a % mod;
20
    while (d) {
21
        if (d & 1) res = mul_mod(res, base, mod);
22
        base = mul_mod(base, base, mod);
23
        d >>= 1;
24
    }
25
    return res;
26
}
27
28
bool miller_rabin_check(u64 n, u64 a, u64 d, int s) {
29
    // Check a^d mod n; then square s times looking for nontrivial square roots of 1
30
    u64 x = pow_mod(a, d, n);
31
    if (x == 1 || x == n - 1) return false; // probably prime for this base
32
    for (int r = 1; r < s; ++r) {
33
        x = mul_mod(x, x, n);
34
        if (x == n - 1) return false; // probably prime for this base
35
    }
36
    return true; // definitely composite for this base
37
}
38
39
bool is_probable_prime(u64 n, int k = 8) {
40
    if (n < 2) return false;
41
    for (u64 p : {2ull,3ull,5ull,7ull,11ull,13ull,17ull,19ull,23ull,29ull,31ull,37ull}) {
42
        if (n % p == 0) return n == p;
43
    }
44
    // write n-1 = 2^s * d with d odd
45
    u64 d = n - 1; int s = 0;
46
    while ((d & 1) == 0) { d >>= 1; ++s; }
47
48
    uniform_int_distribution<u64> dist(2, n - 2);
49
    for (int i = 0; i < k; ++i) {
50
        u64 a = dist(rng);
51
        if (miller_rabin_check(n, a, d, s)) return false; // composite
52
    }
53
    return true; // probably prime
54
}
55
56
int main() {
57
    ios::sync_with_stdio(false);
58
    cin.tie(nullptr);
59
60
    vector<uint64_t> tests = {2, 3, 4, 17, 561, 1'000'000'007ull, 18'446'744'073'709'551'557ull};
61
    for (auto n : tests) {
62
        bool prime = is_probable_prime(n, 10); // 10 random bases => error <= 4^{-10}
63
        cout << n << ": " << (prime ? "probably prime" : "composite") << '\n';
64
    }
65
    return 0;
66
}
67

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Reservoir sampling maintains a uniform random sample of k items from a stream of unknown length.
5
// Each item seen so far is included with probability k/t after seeing t items.
6
7
static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
8
9
vector<int> reservoir_sample(istream& in, int k) {
10
    vector<int> R; R.reserve(k);
11
    int x; long long t = 0; // t = items seen so far
12
    // Fill the reservoir with the first k items
13
    while ((int)R.size() < k && (in >> x)) {
14
        R.push_back(x);
15
        ++t;
16
    }
17
    // For each subsequent item, keep it with probability k/t and evict a random old one
18
    while (in >> x) {
19
        ++t;
20
        uniform_real_distribution<double> prob(0.0, 1.0);
21
        if (prob(rng) < (double)k / (double)t) {
22
            uniform_int_distribution<int> idx(0, k - 1);
23
            R[idx(rng)] = x;
24
        }
25
    }
26
    return R;
27
}
28
29
int main() {
30
    ios::sync_with_stdio(false);
31
    cin.tie(nullptr);
32
33
    // Demo: sample 5 numbers from stdin stream
34
    // Example usage: echo "1 2 3 4 5 6 7 8 9 10" | ./a.out
35
    auto sample = reservoir_sample(cin, 5);
36
    cout << "Reservoir sample (size=" << sample.size() << "): ";
37
    for (int v : sample) cout << v << ' ';
38
    cout << '\n';
39
    return 0;
40
}
41