.Q1)

5 pts for recognizing it's a SSSP
5 pts algorithm

Common problems:

- For whatever reason, people tried to use to maximize 1-r(u,v) as opposed
to r(u,v) over the path.  If you read the question, r(u,v) is the
probability the path will NOT fail.  Thus, 1-r(u,v) is the probability
that the path WILL fail.  You needed to either maximize r(u,v) or minimize
1-r(u,v), not a combination of the two
- If you were using a modified Dijkstra algorithm to maximize, you needed
to change the init-gss function as well as relax.

Q2)

a.  5 pts (2 pts recognizing Prim/Kruskal, 3 pts modifying existing algorithm)
b.  3 pts algorithm, 2 pts reasoning
ec. 3 pts algorithm, 2 pts reasoning

Common problems:
- For part a, trying to use Dijkstra was not applicable, since Dijkstra is
an algoirhtm based on find the shortest path in a DIRECTED graph from one
point to another.  
- For part b, many people tried using a maximum spanning tree (going
against the hint), by splitting up vertices between two sets of points, in
some sort of order.  Generally, this order entailed starting at one point,
following an edge to its neighbor, putting them in separate sets, and then
repeating with a new point.  If you read the problem, the Split(p,q) of
two sets p and q is the minimum distance between two points within the
sets p and q.  To maximize this value, you wanted to make sure that you
chose from the set of all minimum edges (ie: MST) and then maximized your
next selection from that group.  Thus, the solution.
- For part c, this is where you wanted to split up points based on
neighbors.  Thus, you would two-color the tree.


Q3)

2 pts "non-crossing" lemma
1 pts sort the skis, skiers
4 pts recurrence
1 pt why recurrence works
1 pt how to trace back the solution
1 pt runtime

ec.  2 pts runtime, 6 pts recurrence relation, 2 pts reasoning

Common problems:
-Many people just sated the recurrence, neglecting to prove it.  This lost
you points.
-The first thing you should have done is prove the non-crossing lemma.
Note that proving this lemma does not lead you to derive the recurrence.
They are, to a certain degree, unrelated.
-If you used a matrix, which many of you did, you needed to explain why
tracing the optimal solution from A[i,j] backwards was a good approach.


Q4)

2 pts for realizing only 3n blocks.
6 pts graph
2 pts shortest path (runtime)

Common problems:
- Students lose points if they didn't metion there are 3n of vertices.
- Some students solution missing runtime.

Q5)

a.  2 pts recurrence, 2 pts table, 2 pts running time
b.  2 pts graph, 2 pts explanation

Common problems:
- Most students got this quesiton right.
- For part b, simply showing a graph is not enough.  You also need to
  have an explanation.
  
Q6) 

6 pts modifying relaxation, 2 pts path length, 2 pts runtime

ec.  10 points for correct algorithm

Common problems:
- A lot of students didn't methion the runtime, which is needed in
  order to get full credit.
- For extra credit, you need to prove that your algorithm will yield 
  exactly k edges for k < |V|.  A solution that gives the shortest path
  with maximum k edges wouldn't get any credit.

Q7)  

4 pts transformation
4 pts algorithm
2 pts runtime

Common problems:
- Some students didn't transform the graph.  Instead, they modified the Dijkstra's 
  algorithm.  If students did so, they need to explain their algothom in great 
  detail to get full credit.
- If student transformed the graph to a direct graph, they need to double the number 
  of edges.