CSC 373 Fall 2006
Test 1 comments by the marker.

Q1a: Most people get the right answer for this question,
although some try to argue (vaguely) instead of coming with
a concrete counterexample.


Q1b: A number of algorithms first sort the edges by the weights.
These do not run in time O(n) because the sorting requires
time Omega(nlogn).

Another common error is to run Prim or Kruskal algorithms.
These also require sorting and do not run in time O(n).


Q1c:  Again this this part, some people sort the edges, and
thus the running time is not O(n).

A few people only compute the total weight of one path
from s to each vertex. This is not enough, since there are
two paths from s to each vertex, and we need to find the smaller
total weight.



Q2a: Most people get this part right.


Q2b: Some people give the algorithm as if g_i is the distance
from station (i-1) to station i.


Q2c: A popular failure is to not define the notion of a promising
partial solution, or not define it precisely. (Marked by (P) in
the marking comment.) As a result, almost all are not aware of
a kind of "exchange lemma". Only a handfull people define the
right notion and give a complete proof.



Q3a: A common mistake is to take the most weighted edge. (It is not
hard to come up with an example where this algorithm fails.)

Only a few people who choose to do this question give the right
proof. In many case, the proof of the correctness only try to
show that the algorithm correctly selects the most weighted edge
in T!

Q3b: Almost all who choose this question get the right answer.