6.046 randomization
randomization¶
随机算法有很多种，比较有趣的三类是：
- Probably correct(determined fast) : Monte Carlo algorithm
- Probably fast(determined correct): Las Vegas algorithm
- not guaranteed to be fast or correct: Atlantic City algorithms
Matrix multiply¶
problem: Matrix product checker
Given n × n matrices A, B, C, the goal is to check if A × B = C or not.
Question: a such matrix multiplication would take O(n**3) time. We want a checker algorithm to take less time than that, or else the checker doesn’t make sense.
We will see an O(n**2) algorithm that:
- if A × B = C, then Pr[output=YES] = 1.
- if A × B = C, then Pr[output=YES] ≤ 1/2
Frievald’s algorithm: Choose a random binary vector r[1…n] such that Pr[ri = 1] = 1 /2 independently for r = 1 , …, n. The algorithm will output ’YES’ if A(Br) = Cr and ’NO’ otherwise.
Analysis of correctness if AB != C
Claim: If AB != C, then Pr[ABr != Cr] ≥ 1/2.
want to show: ABr != Cr => Dr != 0 where D=AB-C. The goal is to show that there are many r such that Dr != 0.(many >= 1/2)
Proof:
-
Dr != 0 case, we would output ‘No’, done
-
Dr = 0 case(specifically, it means that find r’ s.t. Dr’ != 0)
Set a binary vector v is 0 in all coordinates except for v_j = 1: (Dv)_i = d_ij !=0 implies Dv != 0
Take any r where Dr = 0, set r’ = r + v.
- Dr’ = D(r + v) = 0 + Dv != 0
- r to r’ is 1 to 1
Therefore # r’ for which Dr’ != 0 >= # r for which Dr=0
we can conclude that Pr[ABr != Cr] ≥ 1/2.
quicksort¶
Quick sort is in-place sort, which need not require auxiliary space as merge sort. Divide and conquer algorithm doesn’t work well in the combine step.
We can use median finding in pivot selection. It takes theta(n*logn) time. However, it is slow in practice and loses to merge sort.
randomized quicksort comes to solution.
“paranoid” quicksort analysis and expected runtime analysis
R4: Randomized median¶
Quick find, quick sort
expected runtime, amoritized runtime are just fancier way saying average runtime.
skip lists¶
With high probability bound