Marker's comments on PS3 (Kaveh Ghasemloo)

Overall: Average Mark: 34.7/50
In question 1, defining the search problem had 3 points, the reduction had 7
points. For question 2-4, showing that the problem is in NP had 2 points, the
reduction part has 4 points, and the correctness argument had 4 points.

Q1. Ave: 6.9/10
Most students did well on this question. Note that you don't need to find the
optimal solution, and the search problem should return the indices not the
numbers.


Q2. Ave: 6.8/10
Most students did well on this question. There were some confusion about how the
input is given (i.e. the encoding of the input). The more elegant way of
representing input would be listing members of each S_i. A less efficient way is
representing each S_i by a bit-vector of size n. Note that n is not a polynomial
in the size of input if we are using the first representation. You should
specify the representation of the input that you are using and calculate the
size of the input. For an algorithm which receives an integer n as its input,
the size of input is log n, so don't assume that n to be the size of the input.

Q3. Ave: 8.9/10
Almost all students did well on this problem.

Q4. Ave: 5.3/10
Showing that the problem is NP (proving that there is polysize certificate if
there is a certificate) is difficult, no point is taken if you have noticed the
difficulty. (see
www.jstor.org/stable/2047041 or www.jstor.org/stable/2041711 for a proof).
Checking certificate need matrix multiplication. It is not known if matrix
multiplication can be down in quadratic time, the naive algorithm runs in cubic
time. (seehttp://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Algorithms_for_eff
icient_matrix_multiplication)

Q5. Ave: 6.8/10
Most students did well on this problem.



    [ Part 2, Text/PLAIN (Name: "CSC365-2011-PS3-info.txt") ~550 bytes. ]
    [ Unable to print this part. ]


    [ Part 3, Text/PLAIN (Name: "list3.txt") ~667 bytes. ]
    [ Unable to print this part. ]