CS214, Winter 2022, Midterm Exam
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS214, Winter 2022, Midterm Exam
1 Things you need to know
Time and policy. This is an open book exam. You have 48 hours to take this exam (14:00 02/25/2022 - 13:59:59 02/27/2022). You can arrange your time based on your own schedule and time zone. You are free to use any sources or references including course slides, books, wikipedia pages, or material you find online, but again you must cite all of them. You must not communicate with anyone else other than the course instructor during the exam. You will type your answers via GradeScope. You can also attach any pictures or pdf file as an illustration for certain problems (but you don’t need to). The pictures should only contain important illustration of your solution. It cannot be your entire solution and cannot just be the texts.
Grading. There are 120+40 points in this exam. You don’t need to finish all of the problems (you could, of course). Your final score will be
min(your basic score , 100) + your bonus score
That means the maximum score you could get is 115 points. Although we have a cutoff at 100 for the basic score, you could earn an extra candy every 5 points you earn above 100 points.
Plagiarism Warning. Cheating or plagiarism will NOT be tolerated. As mentioned, any external sources has to be cited. You cannot discuss anything related to this exam during the 48 hours, except for the course instructor (and only for clarifications). If your answer indicates that you cheated in the exam, it is likely that you will fail the course immediately and will be reported to the university. As a short conclusion, don’t cheat.
Answer v.s. Explanation. In the system, if you see a small textbox, it means that you can directly present your answer (no explanation needed). If you see a large textbox, you’ll need to present a long answer, e.g., to describe an algorithm, proof, or explanation. For all algorithms you designed, please explain in natural language, instead of just showing code (you can show code to help illustrate your ideas, but not just code).
Others. For all algorithms and conclusions we learned in class, you can directly use them and their cost bounds (i.e., you don’t need to prove them again).
Please make sure you understand the policy above.
Problem Overview
|
Number |
Problem |
Basic points |
Bonus points |
Candies |
|
1 |
Things you need to know |
0 |
0 |
0 |
|
2 |
Multiple choice |
15 |
0 |
0 |
|
3 |
Short answers |
30 |
2 |
1 |
|
4 |
The Best Chocolate Bar |
20 |
4 |
2 |
|
5 |
Rainy Day |
20 |
0 |
0 |
|
6 |
Vote for your favorite food! |
20 |
6 |
2 |
|
7 |
How long do you need to finish your program? |
20 |
3 |
1 |
|
8 |
Sorting with BST |
0 |
25 |
3 |
|
Total |
|
120 |
40 |
9 |
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 old = 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.
3 (25pts) Short answers
(9pts) Work and Span
1. (3pts) For a computation under binary fork-join on P processors, with work W and span D, using a greedy scheduler, the running time is bounded by O( ) (You only need to fill in the answer, no explanations or proofs needed).
2. (6pts) Based on your answer above, briefly explain how work and span affect running time, given different values of P (the number of processors).
(8pts) Augmented Trees
In class we learned augmented trees, which can be used to solve range-sum-value queries. Now we want to use augmented trees to solve the “range-average-value” query: given kL and kR , please return the average value of all entries within key range [kL , kR ] (inclusive). Assume both keys and values are integers.
We can solve this query by directly use our augmented tree framework. Let’s just instantiate such an augmented tree by specifying its map and reduce functions. Recall that map means to get the augmented value of a single key-value pair, and reduce means to “combine” two augmented values. For example, if the queries are asking about the sum of all values in the given key range, we can define map and reduce functions as:
|
struct aug_tree { // return the augmented value for a single entry with key k and value v int map(int k, int v) { return v; } // given two augmented values a1 and a2, combine them into one augmented value int reduce(int a1, int a2) { return a1+a2; } int identity = 0; // basic fields and functions, same as described in class // functions use map(), reduce() and identity to deal with augmented values ...
double range_sum_value(int kL, int kR) { return aug_range(kL, kR); } } |
Based on the similar idea, let’s design the functions for range-average-value queries.
|
struct aug_tree { // return the augmented value for a single entry with key k and value v int map(int k, int v) { |
|
return <__3__ , __4__>; } // given two augmented values a1=<x1,y1> and a2=<x2,y2>, // combine them into one augmented value int reduce(pair<int,int> a1, pair<int,int> a2) { let <x1,y1> be the pair of a1, and <x2,y2> |
2023-02-28