Common mistakes made in the Midterm:

1.1: When showing that

[delta^OUT(X) not= 0 for all (s,t)-separators X] => there is an
(s,t)-dipath,

many students tried to build an (s,t)-dipath by considering successive
(s,t)-separators obtained by taking X = {s}, then X = {s,v}, etc.,
where there is an arc uv in delta^OUT(X).  The set of arcs you pick 
this way do not always form an st-dipath. This way, what we get is an
arborescence rooted at s, and therefore the set of all nodes reachable
from s. The set contains t, and therefore there is an st-dipath.

1.2: Many didn't know what was to be shown here (that for all
arcs, y_v <= y_u + w_uv).

1.3: Done well by most.

2: Details of the algorithm were missing or wrong. E.g., which arcs are
considered in calculating the increase in potential, which potential
values are updated.


3: Most knew how to run the algorithm here, but several people did not
get the equality arcs right (and missed some of the updates). Some
stopped when they found an st-dipath.

Several students drew out the equality subgraphs at every step. This
was asked for, and took time that you could have spent answering other
questions. A table as shown in class or in the HW solutions is sufficient.

4.1: Very well done.

4.2: Almost as well done as 4.1.  A few students mistakenly used
SHORTEST paths.

5: Most knew how to run the algorithm, but missed the violated arcs that
revealed a negative dicycle. Some students drew out the arborescence at
every step of the algorithm. Again unnecessary. A table as shown in
class or in the HW solutions is sufficient.

6: Some students didn't know exactly what an arborescence is.
A few only showed that there is a unique path in T' from s to v, but
not to the other vertices.  A few did show that there is a directed
path in T' from s to any vertex, but they didn't show uniqueness.
Some forgot about acyclic-ness.  Some made a random combination of
these errors.

7.1: Very well done, a couple students forgot to consider NON-SINGULAR
submatrices.

7.2: A couple students made the (minor) mistake of forgetting the
sign of the cofactor in the determinant expansion.

7.3: Some students quoted the result proven in class that every
non-singular submatrix of the node-arc incidence matrix has a column
with exactly one non-zero entry.  This is a major step
in the proof, so 2 marks were taken off if you didn't prove this claim.

8.1: Easy.

8.2: Most students did not prove, or failed to prove that the LP was
bounded.  For example, one such mistake was to only consider feasible
solutions that come from perfect matchings, and since there are only a
finite number of them, to erroneously conclude that the LP is bounded.

8.3: Primal variables appearing in the dual.

8.4: Usually blank.  Otherwise correct if 8.3 was correct.

8.5: Probably only one student tried to show that the constraint matrix
was TU.  Other attempts were just plain futile.