York University - Summer 2006
CSE 3101 Test 2 marking comments:

For 1b and 1d, you got 2 (out of 5) for a right answer.

Q1a:
Some students don't update the list of "remaining" activities.
(Indicated by [U]) -0.5

Some forgot the check for compatibility [C] -0.5

Q1b:
Several people gave counter example where the objective is to maximize
"total time" ! [B] -3

[A] means "not indicate output of the algorithm" -1
[O] means "not indicate optimal solution" - 1

Some gave counter example but obtain wrong output. The reason is mainly
that the activities should be sorted using the number of overlap
with the "remaining" activities. [U] -0.5


Q1c:
[C] means not check for compatibility -0.5
[S] means not sort the activities -1

=================================================================

Q2a:
Some argue that the number of edges in the MSP is |V| (-0.5)
It should be |V| - 1.
Many people didn't sort the edges. -2.

Q2b:
[X] Not clear/no description of the cut. -1.
[C] Not show that no edges in the partial solution crossing the cut. -1.
[S] Not show that the chosen edge has smallest weight. -1.

Some define the cut to be (T, E-T) !
Note that the cut is a partition of the vertices, not the edges.

=================================================================

Q3a:
Some define the array to hold the (partial) solution. -1.5.

Q3b:
The initialization is worth 1pt, and the recurrence is 4pt.

Q3c:
[I] for not having the "initialization" step. -1.

=================================================================

Q4
A number of people couldn't get this question.