Marking scheme for Test 3

Section L0102
1.(a) 4 points
  (b) 12 points  (2 for diagrams, 2 for paths, 2 for $\Delta$)
  (c) 4 
  (d) 4 
2.    16 points
-------------
Total=40 points

+++++++++++++++++++++++++
Section L0101
1.    12 points
2.    12 points
3.(a) 12  (The same as 1.(b) of L0102 section)
  (b) 4 ponts
------------
Total=40 (again)


Note for section 1

Explanation for Q2 of Test 3

E2.1 means: Give specific example, or prove
that we may have a min cut of even number of edges.

For Q3(a)
cheating means: The point is to understand the
algorithm, not to solve an easy instance by
inspection.