Posted by: atri | December 20, 2011

First of all, I think I mis-calculated the hardness of the final exam (among other things, this year there were very few joke submissions as compared to last couple of years): sorry about that!

Here are the stats:

• Mean: 46.31
• Median: 45.5
• Std Deviation: 19.81

The final exam score will be up on UBLearns by 12:30pm today (Tue, Dec 20). Also you can pick up your final between 1-5 pm today from my office (Davis 319).

Below is the grading rubric that was used to score the final (along with the name of the grader). If you have any regrade request(s), please contact whoever graded the question you want regraded. Please note, as always, the rubric is a guideline– there might be some variations based on a case by case basis.

1. (Jiun-Jie) 2 for a correct T/F answer, 0 otherwise
2. (Atri) 2 points for a correct T/F answer; 4 for correct justification for a correct answer. Up to 2 points for a partially correct justification for a correct answer. No points if the answer is wrong.
3. (Jiun-Jie)  20 for the algorithm, 3 for Correctness and 2 for time analysis. There are two common wrong answers for this problem. If your answer is one of them, you will get partial credits as follows. (1) For each edge, set $c_e = 1/(p_e)$ and run Dijkstra’s algorithm. In this case, you get– Algorithm: 7/20. Correctness: 0/3. Time Analysis: 2/2 (if your algorithm takes $O(m \log{n})$. (2) Use Prim’s algorithm or Kruskal’s algorithm to find maximum spanning tree T. Output the path from s to t in the spanning tree T. Algorithm: 2/20. Correctness 0/3. Time Analysis: 2/2 (if your algorithm takes $O(m \log{n})$.
4. (Jesse) 12 for the algorithm, 3 for correctness argument, 2 for run time analysis and 3 points for temporary space argument.  5 points for cases as mentioned in the final. 2 points if run a sorting algorithm in the values (and mentioned $O(n\log{n})$ runtime).
5. (Atri) 12 points for example and 3 points for correctness argument. 3 points, if you got the idea behind the example but did not give any specific example.  3 points for presenting an example as mentioned in the question or presenting an example with $O(n)$ fresh entries.