这是一个美国的并行算法限时测试
2 Multiple Choices (15pts)
For each problem, there is only one correct answer.
1. Which of the following algorithms we learned in class is race-free
A. Parallel BFS
B. Parallel Knuth Shuffle
C. Parallel Tree union
D. Parallel Bellman-Ford
2. Which of the following statement about parallel SSSP is true
A. Parallel Bellman-Ford is always faster than Dijkstra in practice because it has better parallelism.
B. We can combine parallel Bellman-Ford and Dijkstra to get a parallel SSSP algorithm that is
work-efficient with polylogarithmic span.
C. Parallel -stepping has a better span (asymptotically lower) than parallel Bellman-Ford.
D. Parallel Bellman-Ford can have reasonably good performance on low-diameter graphs. However,
it can be expensive on large-diameter graphs.
3. In the quicksort, if we choose each pivot uniformly at random, then, each element is involved in O(log n)
comparisons with high probability. This statement is .
A. True B. False
4. We learned the reachability-based SCC algorithm in class. Given a directed graph below, assume we
first run reachability searches on both the blue and orange vertices in parallel. After that, we
will remove some edges based on the reachability search results. How many edges will we remove
