Message No. 116
Notes on Q2 - Moed B
Due to an error, the attached comment index for Q2 was not published along with your test notebooks. When you will find number k=1,2,… enveloped in a square at the margins of your answer to q.2, find the text of comment number k in the following lists.

If you feel your appeal has been wrongfully denied due to unclear comments for Q2, please contact the course mailbox with your details.

Your request for reconsideration must include the relevant comment #, and an explanation detailing why you believe it does not apply. Your may not include requests for reconsideration of other questions and/or of comments on Q2 already detailed in the grader comments.

All requests must be submitted by midnight, 30/8/15.

2a:

  1. The condition of Multi-SAT is related to the number of variables (n) in the original formula phi, not to the number of variables in the formula f(phi) of Multi-SAT.
  2. Polynomiality of the reduction is not related in the answer.
  3. Clause (x1 v x2 v … v xk) has 2^k, not 2^k-1 satisfying assignments.
  4. The explanation goes as if satisfying assignments for the original formula phi and for f(phi) are the same. That is, it is not mentioned that the former are restrictions of the latter, and the latter are extensions of the former.
  5. Assignments to the old and the new variables at f(phi) are considered separately, and their numbers are summed.

2a:

General miss: Only a minority of the students paid attention that the number of ALL subsets of U is |V|, and hence, listing of all the subsets is polynomial in |V| and is easy to execute.
  1. An algorithm for generating all subsets of U of size k is not provided. Nothing to say on its time analysis.
  2. k is considered be a constant. (If that would be so, then a polynomial algorithm would exist even for VC itself.)
  3. No explanation why the (correct) formula for the number of subsets of U of size k is polynomial.
  4. (log|V|)^{log|V|} is NOT O(|V|), and even is not polynomial in |V|. It is (2^ {loglog|V|})^{log|V|}, that is (2^ {log|V|})^{loglog|V|}, that is |V|^{loglog|V|}.
  5. Only subsets of U of size exactly k are related to.
  6. The algorithm for checking whether a vertex subset is a vertex cover of G is not described or referenced.
published on 27/08/2015 19:46:05 by Boaz Arad