Skip to main content
Mapagam

Using Randomized Algorithms

1. Implementing Las Vegas Algorithms

Las Vegas algorithms are randomized algorithms that always produce correct results but have a random runtime. They are named after the city of Las Vegas due to their unpredictable nature.

Algorithm Type Description Key Characteristics Examples
Monte Carlo Randomized algorithm that may produce incorrect results Always terminates, but can be wrong with some probability Randomized quicksort, primality testing
Las Vegas Randomized algorithm that always produces correct results Runtime is random, but correctness is guaranteed Randomized quicksort (with pivot selection), randomized MST

Example: Randomized QuickSort (Las Vegas)

function randomizedPartition(arr, low, high) {
    const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    return partition(arr, low, high);
}

function randomizedQuickSort(arr, low, high) {
    if (low < high) {
        const pi = randomizedPartition(arr, low, high);
        randomizedQuickSort(arr, low, pi - 1);
        randomizedQuickSort(arr, pi + 1, high);
    }
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

// Example usage:
const arr = [3, 5, 2, 8, 1];
randomizedQuickSort(arr, 0, arr.length - 1);
console.log(arr); // Output: [1, 2, 3, 5, 8]
Note: The randomized quicksort uses a random pivot to avoid worst-case performance on already sorted arrays.

Key Properties of Las Vegas Algorithms

  • Correctness: Always returns the correct result
  • Randomness: Runtime varies based on random choices
  • Expected Performance: Often better than deterministic algorithms in average case
  • Use Cases: When correctness is more important than runtime predictability

2. Implementing Monte Carlo Algorithms

Algorithm Description Use Case Complexity
Monte Carlo Integration Estimates the value of an integral using random sampling. Numerical integration for complex functions O(n)
Randomized QuickSort Variant of quicksort that picks a random pivot to avoid worst-case performance. Sorting large datasets with unknown distribution O(n log n) average, O(n²) worst-case
Randomized Primality Test Determines if a number is prime using random sampling. Cryptographic key generation O(k log³ n)

Example: Monte Carlo Integration

// Estimate integral of f(x) = x^2 from 0 to 1
function monteCarloIntegration(n) {
    let underCurve = 0;
    for (let i = 0; i < n; i++) {
        const x = Math.random();
        const y = Math.random();
        if (y <= x * x) underCurve++;
    }
    return underCurve / n;
}
console.log(monteCarloIntegration(10000)); // Approximates 1/3

Example: Randomized QuickSort

// Randomized pivot selection
function randomizedQuickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const pivotIndex = partitionRandom(arr, low, high);
        randomizedQuickSort(arr, low, pivotIndex - 1);
        randomizedQuickSort(arr, pivotIndex + 1, high);
    }
}

function partitionRandom(arr, low, high) {
    const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    return partition(arr, low, high);
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}
Note: Monte Carlo methods are probabilistic and may not always produce the exact result, but they provide a good approximation with known error bounds.

3. Implementing Randomized Quick Sort

Property Description Example
Algorithm Randomized Quick Sort uses random pivot selection to improve average-case performance randomizedQuickSort(arr, low, high)
Time Complexity Average case: O(n log n), Worst case: O(n²) Best for randomized input
Space Complexity O(log n) due to recursion stack More efficient than deterministic quicksort in practice

Example: Randomized Quick Sort Implementation

function randomizedQuickSort(arr, low, high) {
  if (low < high) {
    let pi = randomizedPartition(arr, low, high);
    randomizedQuickSort(arr, low, pi - 1);
    randomizedQuickSort(arr, pi + 1, high);
  }
}

function randomizedPartition(arr, low, high) {
  let randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
  [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
  return partition(arr, low, high);
}

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Example usage:
let arr = [3, 5, 2, 8, 1];
randomizedQuickSort(arr, 0, arr.length - 1);
console.log(arr); // [1, 2, 3, 5, 8]
Note: Randomized Quick Sort reduces the chance of hitting worst-case performance by randomly choosing the pivot element.

4. Implementing Randomized Quick Select

Property Description Example
Algorithm Finds the kth smallest element in an unsorted array quickSelect(arr, 0, arr.length - 1, k)
Time Complexity Average case: O(n), Worst case: O(n²) On average, linear time
Space Complexity O(log n) due to recursion stack Recursive implementation

Example: Randomized Quick Select Implementation

function randomizedQuickSelect(arr, left, right, k) {
    if (left === right) return arr[left];

    const pivotIndex = randomizedPartition(arr, left, right);
    const rank = pivotIndex - left + 1;

    if (k === rank) {
        return arr[pivotIndex];
    } else if (k < rank) {
        return randomizedQuickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return randomizedQuickSelect(arr, pivotIndex + 1, right, k - rank);
    }
}

function randomizedPartition(arr, left, right) {
    const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
    swap(arr, randomIndex, right);
    return partition(arr, left, right);
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left - 1;

    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

// Example usage:
const arr = [3, 2, 1, 5, 4];
const k = 3;
console.log(randomizedQuickSelect(arr, 0, arr.length - 1, k)); // Output: 3
Note: The randomized pivot selection helps avoid worst-case performance by reducing the chance of consistently choosing poor pivots.

5. Solving Reservoir Sampling

Reservoir sampling is a family of algorithms for randomly selecting k items from a stream or large dataset of unknown size. The most common variant is reservoir sampling with k=1, which selects one item at random from a stream.

Property Description Notes
Algorithm Type Streaming Algorithm Works with unknown input size
Time Complexity O(n) Where n is the number of items in stream
Space Complexity O(k) Where k is the number of items to sample
Use Case Random selection from large or streaming data Useful in systems where full dataset is not available

Example: Reservoir Sampling with k=1

function reservoirSample(stream) {
  let result = null;
  let count = 0;

  for (let item of stream) {
    count++;
    if (Math.random() < 1 / count) {
      result = item;
    }
  }

  return result;
}

// Example usage:
const dataStream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const sampledItem = reservoirSample(dataStream);
console.log(sampledItem); // Random item from stream
Note: The probability of selecting any item is 1/n, where n is the total number of items seen so far. This ensures uniform randomness.

Key Points

  • Each item in the stream has an equal probability of being selected.
  • Works with streams or datasets of unknown size.
  • Space-efficient: only stores k items at any time.

6. Implementing Skip List

Operation Description Time Complexity Space Complexity
Search Find an element in the skip list O(log n) O(n)
Insert Insert a new element into the skip list O(log n) O(n)
Delete Remove an element from the skip list O(log n) O(n)

Example: Skip List Implementation in JavaScript

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

class SkipList {
  constructor() {
    this.header = new SkipListNode(-Infinity, 0);
    this.level = 0;
  }

  randomLevel() {
    let level = 0;
    while (Math.random() < 0.5) {
      level++;
    }
    return level;
  }

  insert(value) {
    const update = new Array(this.level + 1).fill(this.header);
    let current = this.header;

    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null &&
             current.forward[i].value < value) {
        current = current.forward[i];
      }
      update[i] = current;
    }

    const newLevel = this.randomLevel();
    if (newLevel > this.level) {
      this.level = newLevel;
      update[this.level] = this.header;
    }

    const newNode = new SkipListNode(value, newLevel);
    for (let i = 0; i <= newLevel; i++) {
      newNode.forward[i] = update[i].forward[i];
      update[i].forward[i] = newNode;
    }
  }

  search(value) {
    let current = this.header;

    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] !== null &&
             current.forward[i].value < value) {
        current = current.forward[i];
      }
    }

    current = current.forward[0];
    return current !== null && current.value === value;
  }
}

// Example usage:
const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
console.log(skipList.search(6)); // true

7. Solving Bloom Filter

A Bloom filter is a probabilistic data structure that tests whether an element is a member of a set. It can return false positives but never false negatives.

Property Description Values
hash_functions Number of hash functions used 3
bit_array_size Size of the bit array in bits 1024
false_positive_rate Probability of false positives 0.01

Example: Bloom Filter Implementation

class BloomFilter {
  constructor(size, hashCount) {
    this.bitArray = new Array(size).fill(0);
    this.size = size;
    this.hashCount = hashCount;
  }

  hash(str, seed) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      const char = str.charCodeAt(i);
      hash = (hash * 31 + char) % this.size;
    }
    return hash;
  }

  add(item) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i) % this.size;
      this.bitArray[index] = 1;
    }
  }

  contains(item) {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i) % this.size;
      if (this.bitArray[index] === 0) {
        return false;
      }
    }
    return true;
  }
}

const bf = new BloomFilter(1024, 3);
bf.add("example");
console.log(bf.contains("example")); // true
console.log(bf.contains("nonexistent")); // might be true (false positive)
Note: Bloom filters are useful for reducing database lookups and caching, but they can produce false positives. They are commonly used in systems like Redis or Apache Cassandra.

8. Implementing Treap

A treap is a randomized binary search tree that combines the properties of a binary search tree (BST) and a heap. Each node has a key and a priority, where the keys follow BST rules and priorities follow min-heap rules.

Operation Description Time Complexity
Insert Insert a new key with a random priority. Rotate to maintain heap property. O(log n)
Search Search for a key in the BST structure. O(log n)
Delete Remove a key and restructure to maintain heap property. O(log n)

Example: Treap Node Structure

class TreapNode {
  constructor(key, priority) {
    this.key = key;
    this.priority = priority;
    this.left = null;
    this.right = null;
  }
}

Example: Insert Operation

function insert(root, key) {
  if (root === null) {
    return new TreapNode(key, Math.random());
  }

  if (key < root.key) {
    root.left = insert(root.left, key);
    if (root.left.priority < root.priority) {
      root = rotateRight(root);
    }
  } else {
    root.right = insert(root.right, key);
    if (root.right.priority < root.priority) {
      root = rotateLeft(root);
    }
  }

  return root;
}

Example: Search Operation

function search(root, key) {
  if (root === null || root.key === key) {
    return root;
  }

  if (key < root.key) {
    return search(root.left, key);
  } else {
    return search(root.right, key);
  }
}

9. Finding Miller-Rabin Primality

The Miller-Rabin primality test is a probabilistic algorithm used to determine if a number is likely to be prime. It's based on the property that for a prime n, if we write n - 1 = d * 2^r where d is odd, then for any integer a such that 1 < a < n - 1, either:

  • a^d ≡ 1 (mod n), or
  • a^(d * 2^j) ≡ -1 (mod n) for some j in [0, r).

If neither condition holds, then n is composite.

Property Description Notes
n int - the number to test for primality Must be greater than 2 and odd
k int - number of iterations to perform Higher values increase accuracy; typically 10-20 is sufficient
a int - random base for the test Chosen uniformly at random from [2, n - 2]

Example: Miller-Rabin Test Implementation

function millerRabin(n, k = 5) {
  if (n <= 1) return false;
  if (n === 2 || n === 3) return true;
  if (n % 2 === 0) return false;

  // Write n - 1 as d * 2^r
  let r = 0;
  let d = n - 1;
  while (d % 2 === 0) {
    d /= 2;
    r++;
  }

  // Perform k rounds of testing
  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (n - 4));
    let x = modPow(a, d, n);

    if (x === 1 || x === n - 1) continue;

    let composite = true;
    for (let j = 0; j < r - 1; j++) {
      x = (x * x) % n;
      if (x === n - 1) {
        composite = false;
        break;
      }
    }

    if (composite) return false;
  }

  return true;
}

function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

// Example usage:
console.log(millerRabin(17)); // true
console.log(millerRabin(15)); // false
Note: The Miller-Rabin test is probabilistic, meaning it can return a false positive (indicating that a composite number is prime). However, the probability of error decreases exponentially with more iterations.

Miller-Rabin Test Summary

  • Time Complexity: O(k log³ n)
  • Space Complexity: O(1)
  • Accuracy: For a composite n, the probability of failure is at most 1/4^k
  • Use Cases: Large number primality testing, cryptographic key generation

10. Implementing Randomized Min Cut

Operation Description Complexity Notes
Randomized Min Cut Algorithm to find the minimum cut in a graph by repeatedly contracting edges until only two nodes remain. O(n2 log n) Expected runtime for Karger's algorithm with random edge selection.

Example: Randomized Min Cut Implementation

class Graph {
  constructor() {
    this.edges = [];
    this.nodes = new Set();
  }

  addEdge(u, v) {
    this.edges.push([u, v]);
    this.nodes.add(u);
    this.nodes.add(v);
  }

  contractEdge(u, v) {
    const newEdges = [];
    for (const [a, b] of this.edges) {
      if (a === u && b === v) continue;
      if (a === v) newEdges.push([u, b]);
      else if (b === v) newEdges.push([a, u]);
      else newEdges.push([a, b]);
    }
    this.edges = newEdges;
    this.nodes.delete(v);
  }

  minCut() {
    const nodes = Array.from(this.nodes);
    while (nodes.length > 2) {
      const randomEdge = this.edges[Math.floor(Math.random() * this.edges.length)];
      this.contractEdge(randomEdge[0], randomEdge[1]);
    }
    return this.edges.length;
  }
}

const g = new Graph();
g.addEdge('a', 'b');
g.addEdge('b', 'c');
g.addEdge('a', 'c');
g.addEdge('c', 'd');
g.addEdge('b', 'd');

console.log(g.minCut()); // Random result between 1 and 2
Note: The randomized min cut algorithm is probabilistic and may not always return the optimal solution. It's typically used for approximate solutions or in randomized algorithms where a good approximation is acceptable.

11. Solving Load Balancing

Algorithm Description Use Case Complexity
Random Load Balancing Assigns incoming requests to servers randomly Simple distribution, no server state tracking O(1) average
Round Robin Cycles through servers in order Even distribution, simple to implement O(1) per request
Weighted Round Robin Assigns weights to servers based on capacity Handles servers with different capacities O(1) per request
Least Connections Assigns to server with fewest active connections Optimizes for server load O(1) average
Least Time Chooses server with lowest response time Improves user experience O(1) average

Example: Random Load Balancing Implementation

const servers = ["server1", "server2", "server3"];

function getRandomServer() {
  const randomIndex = Math.floor(Math.random() * servers.length);
  return servers[randomIndex];
}

// Simulate request distribution
for (let i = 0; i < 10; i++) {
  console.log("Request " + i + " assigned to: " + getRandomServer());
}

Example: Least Connections Implementation

let serverLoads = {
  "server1": 0,
  "server2": 2,
  "server3": 1
};

function getServerWithLeastConnections() {
  let minLoad = Infinity;
  let selectedServer = null;

  for (const [server, load] of Object.entries(serverLoads)) {
    if (load < minLoad) {
      minLoad = load;
      selectedServer = server;
    }
  }

  return selectedServer;
}

// Simulate assigning a new request
const nextServer = getServerWithLeastConnections();
serverLoads[nextServer] += 1;
console.log("Assigned to " + nextServer + " with load " + serverLoads[nextServer]);
Note: Randomized algorithms can provide good load distribution in systems where detailed server state tracking is not feasible or desired.

Was this article helpful?

Related Cheat Sheets