Vincec's Dimension

Algorithm Review Notes - Randomized Algorithms

Word count: 347 / Reading time: 2 min
2018/11/26 Share

Deterministic vs Randomized

Deterministic

  • Tworst(n) = max|x|=n T(x)
  • Tbest(n) = min|x|=n T(x)

Randomized

  • T(n) = max|x|=n Expect[T(x)]

Advantage

  • May faster than deterministic alg
  • May have smaller space complexity
  • May simpler
  • We can solve those question cannot designed efficient deterministic alg directly

Probability

Events

A subset of a sample space is called a event

Fair die - each have sample prob

Indicator Ramdom Variables - {0, 1}

Expectation

E[X] = ∑k∈OmegaPr(X = k) * X(k) #sum of possible outcomes, each weighted by its prob

Rolling a die

  • E[X] = 1/6 1 + 1/6 2 + … 1/6 + 6 = 3.5
  • Expectation is not real data may appear in your case, Pr(X = 3.5) is wrong

Expectation of an Indicator

E[x] = Pr(E)

Linearity of Expectation

E[X + Y] = E[X] + E[Y]

Quick Sort

Deterministic Pivot

Random Pivot

Runtime

O(nlogn)

Global Min-Cut problem

Randomized

  • Ramdom pick an edge and contract
  • Remove self loops
  • repeat until one edge left

Complexity

  • Edge contraction requires O(V)
  • Total Time O(V2)
  • To get the min-cut, we need to run O(V2)
  • Final Total is O(V4)

Las Vegas Alg

Always return the correct answer but may run for longer than you expect. E.g. Quick sort

Monte Carlo Alg

May fail or return incorrect answer but runtime is independent of input randomness(fast). E.g. Global min-cut

Skip Lists

A linked list of size N with k shortcuts - K k√N, when K = log2N, total search time is O(logN)

Treap (Tree Heap)

Ramdomized binary search tree - A binary search tree with the heap ordering property, assign x.key and x.priority to the node by randomzied.

Insert

  • Insert 10
  • generate [10, 3]
  • insert to BST
  • Check the priority
  • rotate the order to get heap proterty, but keep the BST ordering structure

Delete

  • Delete by following BST proporty
  • Rotate by following heap proporty

Runtime

  • expected depth of any node is O(logn)
  • total insertion is same O(logn) (On average, expectation is the depth)

Reference

  • Slides
CATALOG
  1. 1. Deterministic vs Randomized
    1. 1.1. Advantage
      1. 1.1.1. Probability
      2. 1.1.2. Events
      3. 1.1.3. Indicator Ramdom Variables - {0, 1}
      4. 1.1.4. Expectation
      5. 1.1.5. Expectation of an Indicator
      6. 1.1.6. Linearity of Expectation
  2. 2. Quick Sort
    1. 2.1. Deterministic Pivot
    2. 2.2. Random Pivot
    3. 2.3. Runtime
  3. 3. Global Min-Cut problem
  4. 4. Las Vegas Alg
  5. 5. Monte Carlo Alg
  6. 6. Skip Lists
  7. 7. Treap (Tree Heap)
    1. 7.1. Insert
    2. 7.2. Delete
    3. 7.3. Runtime
  8. 8. Reference