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)]

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

### Events

A subset of a sample space is called a event

Fair die - each have sample prob

### 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

E[x] = Pr(E)

### Linearity of Expectation

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

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)

• Slides

Author: VINCEC