Posted by: atri | December 18, 2012

The final exam has been graded. There is a fair amount of information in this post, so please read through carefully.

1. Your total score on the final exam has been uploaded to UBLearns.
2. You can pick up your final from Diane in the CSE main office. You will need to show her your UB card to pick up the final. (In case you do not know where Diane sits, you can get to her desk as follows: if you are going towards Jaynee’s office in the long corridor from the elevators, then Jaynee office is the last door on the left. Diane’s is the door on the left just before Jaynee’s.) You can pick up your final during normal office hours starting tomorrow, Wednesday, Dec 19.
3. I will be in my office from 2-5pm on Thursday, Dec 20 in case you have any questions on the final grading. (However, please go through the rubric below first.) In case you cannot make it during that time, you can email me a scanned copy of the part of the final that you have a question with. Please note: Re-grading requests will only be entertained if there is some obvious mistake (e.g. a totaling mistake)– please do not quarrel about the rubric: it was the same for everyone.
4. My plan is to get the rest of the grading (mini project, piazza, overall letter grade) done by tomorrow, Wed, Dec 19. I’ll put up  blog post(s) once I have done so.
5. The graded finals have solution sketches written on them in case you’re interested in the solutions.

The rest of the post is specific to grading.

The stats are as follows:

• Mean: 48.1
• Median: 53

Below is the grading rubric that was used for the different questions. As usual these are general guidelines. Things might change slightly for specific cases.

2. 0/6 if the T/F answer is incorrect (irrespective of the justification). As mentioned in the exam: 2 points were for the T/F answer and 4 points were for justification. As a general rule: a justification that was incorrect/had no real information would get 0/4; a half-way correct justification would get 2/4. Below are more details for the specific parts:
1. Mention GS algorithm runs in $O(N)$ or $O(n^2)$ or it’s linear are fine. Fail to mention or fail to distinguish $n$ and $N$ will lead a deduction of 4 points.
2. Mention linear scan or $O(n)$ scan will get full points. Listing the procedure but not mention what kind of scan will get a deduction of 1 point.
3. You should clearly state how long it takes to shift and do summation, otherwise you will get a deduction of 2 points each for not correctly stating shift and summation time.
4. All 4 points deducted if answers says binary search without specifying how one gets an upper bound on $n$.
5. This question a easy if you know what $M[s,n-1]$ is. If you state the meaning of it, you will get full points. If you state nothing about $M[s,n-1]$ but something else that is not wrong, you will get a deduction of 3 points. In other cases, your points depend on how much your statement related to the meaning of $M[s,n-1]$.
• 15/25 is for algorithm.
• 7/25 is for correctness.
• 3/25 is for running time.

There are two common approaches to solve Q3.The first one is greedy strategy by picking golds as large as possible.

The other one is that by expressing $n$ into a binary representation. Then, pick the corresponding gold weights in the binary representation of $n$. For example, $n=11$, binary representation is $1011$. So, you should include gold weights  $2^3, 2^1, 2^0$ into your bag. For this approach, you should deal with two cases: $n < 2^{k+1}$ and $n\ge 2^{k+1}$. For $n\ge 2^{k+1}$, you must include all gold bars. If you don’t deal with this case specifically, you will lose 5 points. For correctness of greedy strategy, you should use the property below
$2^i> 2^i - 1 = 2^{i-1} + 2^{i-2} + ...+ 2 +1$  to prove your greedy strategy works. If you don’t do this, you will lose 3~4 points.

3. For both parts, 8/10 for the algorithm and 1 each for correctness and query bound
1. -2 if you do not take care of pairs that never boxed
2. -1 if you do not take care of pairs that never boxed and -1 if you do not verify at the end whether your candidate champion is indeed the undisputed champion.
4. This one had three parts: (If you just got part (c) correct then the points for part (a) and (b) were moved to part (c)).
1. binary: 0 or 1 depending on whether the algorithm was correct or not.
2. 7/9 for the algorithm and 1 each for correctness and run time. -7 if your algorithm runs in time $\Omega(n^2)$ and -4 if your algorithm runs in time $\Omega(n\log{n})$.
3. 4 points for the algorithm and 0.5 each for correctness and run time. -1 if you do not sort $U$ before applying part (b).