Comments on HW 5


Max: 6
Min: 1.3
Average: 3.91
Median: 4.35
 
Comments:

A. Some didn't show that if a path is not
simple, then it has a cycle (i.e., u_i, u_{i+1}, ..., u_j=u_i  with no vertex repeating except 
at u_i).  Some simply argued that
there exists a simple path from s to v, but didn't show the weight of this
simple path is less than or equal to that of the original path from s to v.
 
B. Misuse of Dijkstra algorithm, as described in D below.
 
C. Some tried to modify the Dijkstra algorithm instead of taking log, but then the initial d has to be
1 instead of 0.
 
D. A lot of students are not really using the Dijkstra algorithm. Instead of finding the next vertex to
be added in by considering the minimum of d_u+w_{uv} for u in W and v outside W, students just consider
all paths coming from the source to a next vertex they name. Some students, when using the
SP-Bellman-Ford algorithm, instead of following an ordering of vertex and update the d's one by one,
they chose only to update some subset of it (keeping some infinity); which again is really not using
the algorithm.
 
F. Many do not understand the meaning of minimum max-weight path, seemingly mixing up the min and max.