Comments on HW 5

General note: Always show your work!

A:  Some people got this, though others still confuse closed path
with cycle.  A few thought that a cycle having nonnegative weight means all
arcs in the cycle have nonnegative weight.
Some wrote a rough outline in words ("if the path P has a cycle, then remove
the cycle and the weight will not increase, etc.") but not in
enough detail to constitute a proof.

B:  many people got this, there were a few glitches with the interpretation of the results, so I recommend
people read this in the solutions.

C:  As with last week, there was some confusion on how to employ the log transformation and how to convert a
max to a min.  See the solutions if this applies to you.  Again, show your steps!

D:  Most people got these; for part a, pay attention to the order in which vertices are added.

E:  Most people got these.  There is a counter example for a, and if you struggled with b either in getting the
correct number (2^n) or in justifying it, see the solutions.

F:  Part a seemed pretty clear to everyone, most people struggled with at least part of b.  Remember that
Dijkstra's algorithm records d_v, the weight of the path to v from an initial node.  When discussing how you
modify the algorithm, you need to be specific about how d_v is updated.  It isn't enough to find the minimum of
all the w_uv; you also need to take into account the weight of d_u.  Rather than add them, this time you'll
take the max.

Another overall comment:  It may seem cumbersome to do the algorithms by hand (as opposed to just seeing the
answer).  It can be instructive, however--if ever you need to write code that runs these algorthims, you need
to be able to tell the computer exactly what it needs to do.  The computer won't have the intuition you have.
Being able to do simple ones by hand helps a lot with this.