跳转至

13 Randomized Algorithms

说明

  1. 本文档仅涉及部分内容，仅可用于复习重点知识
  2. 本文档部分图片来源于教学课件

1 Hiring Problem

Img 1
Img 2
Img 3

Online Hiring Algorithm

Img 4
Img 5
Img 6

让上述概率最大的 k 值取 \(\dfrac{N}{e} \approx \dfrac{N}{3}\)

PTA 13.4

The Online Hiring Algorithm ( hire only once ) is described as the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = -INFINITY ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;
}

Assume that the quality input C[ ] is uniformly random. When N = 271 and k = 90, the probability of hiring the Nth candidate is__.

A. 1/e
B. 1/N
C. \(1/3\)
D. 1/k

答案

C

如果要求第 271 个人被 hired，那么需要前 270 个人中的最好的那个人在前 90 人中。所以为 \(\dfrac{90}{270} = \dfrac{1}{3}\)

2 Randomized quicksort

Img 7
Img 8
PTA 13.1

Let \(a = (a_1, a_2, \cdots, a_i, \cdots, a_l, \cdots, a_n)\) denote the list of elements we want to sort. In the quicksort algorithm, if the pivot is selected uniformly at random. Then any two elements get compared at most once and the probability of \(a_i\) and \(a_j\) being compared is 2/(j−i+1) for j>i, given that \(a_i\) or \(a_j\) is selected as the pivot.

T
F

答案

F

并不是所有的 \(a_i\)，\(a_j\) 都会被比较，如果 pivot 的值在这两个之间，那么这两个就不会被比较

PTA 13.2

Reviewing the randomized QuickSort in our course, we always select a central splitter as a pivot before recursions, make sure that each side contains at least n/4 elements. Hence, differing from the deterministic QuickSort, the worst case expected running time of the randomized QuickSort is Θ(NlogN).

T
F

答案

T

不知道为什么对

3 Cut Problem

3.1 Min-Cut

Contraction:

Img 9
Img 10

3.2 Max-Cut

PTA 13.3

Given a linked list containg N nodes. Our task is to remove all the nodes. At each step, we randomly choose one node in the current list, then delete the selected node together with all the nodes after it. Here we assume that each time we choose one node uniformly among all the remaining nodes. What is the expected number of steps to remove all the nodes?

A. Θ(logN)
B. N/e
C. N/2
D. N

答案

A

删除当前节点需要 1 步，删除之后的节点有 n 种情况（删除 0 个或 1 个或 2 个或 3 个 ...... 或 n - 1 个），每种情况出现的概率为 \(\dfrac{1}{n}\)，所以有：

\(T(n) = \dfrac{1}{n} (T(1) + T(2) + \cdots T(n - 1)) + 1\ (T(0) = 0，省略)\)

将选项中的答案带入上式，A 选项能够满足上式

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问