Comments on HW 4


A--many people did not apply the tie breaking rule stated in the problem.
Also, a handful of people resequenced at inappropriate times (i.e. when the
path wasn't closed).

B--People did well for the most part.  I encourage them to look at the
algorithms again to see if they're correctly applying the.  There were a few
glitches in a, b and c.  Also, they should show work for d.

C--A lot of people struggled with parts a and b.  Most people understood c.
They didn't understand that to pose the minimization/maximization problem,
they had to use the same graph, but different weights.  A lot of people
wanted to minimize the product in b instead of maximize it.  Also, a lot of
people didn't understand the point of the log was to convert the product
into a sum.  Definitely look a the solutions for this.

D--A lot of people struggled with this, particularly c.  Many people who
correctly negated c did not use the result in p 17, alluded to in the
statement of the problem.

E and F--there seems to be confusion about what the "if" direction is and
the "only if" direction, which means some people, in E, proved the wrong
direction.  For F, this mean they applied the hint in a place where it
wasn't intended.  The statement "A if B" means that A holds if B holds, so B
=> A (read "B implies A").  Rearranging this, "A if B" is the same as "A <=
B".  The statement "A only if B" means that if B is not true, then A isn't
either.  That is, "not B => not A".  Negating this, we have "A => B".

Also, if you're going to do a proof by contradiction, say so at the
beginning of that portion of the proof.  Be clear about what you're
assuming.
If you want to prove "A => B" by contradiction, you assume A is true and
suppose that B isn't true, and derive a contradiction.  Say clearly why it
is a contradiction.  Conclude with "therefore, A => B."

Finally, when proof writing--use complete sentences!  Be clear!  You may
actually want to edit what you write, to make sure it is clear.  Sometimes
the process of figuring out a proof is messy, especially before you
understand it, so I like to use scratch paper and then organize my thoughts
for the write-up.

That's all!