CSE 482 BigData Analysis Homework 2
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?
A. 5
B. 6
C. 7
D. 8
E. 9
F. 10
5. Yihan wanted to design an algorithm to atomically increment a shared variable s by 1, and
return the new value set by this atomic increment. For example, consider the current value of
s is 5, and two invocations of atomic inc are called. Then they should add 1 to s, respectively, so the
value of s will be 7 after they both finish. Also, one of these to invocations should return 6 (the one
linearized earlier), and the other should return 7 (the one linearized later). She wrote the following
pseudocode. \CAS” means compare and swap, which is defined as we mentioned in class.
shared variable int s = 0;
int atomic_inc() {
int ld = s;
while (!CAS(&s, old, old+1)) {
old = s;
}
return s;
}
Does this algorithm above work as expected?
A. It does not work as expected – it is not atomic.
B. It does not work as expected – It does not always add 1 to s.
C. It does not work as expected – the return value does not match the specification (i.e., not the
desired return value).
D. It does not work as expected – there can be ABA problem.
E. It works as expected.