# Announcements

## 20 last messages

עמוס

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:

- 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.
- Polynomiality of the reduction is not related in the answer.
- Clause (x1 v x2 v … v xk) has 2^k, not 2^k-1 satisfying assignments.
- 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.
- 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.- An algorithm for generating all subsets of U of size k is not provided. Nothing to say on its time analysis.
- k is considered be a constant. (If that would be so, then a polynomial algorithm would exist even for VC itself.)
- No explanation why the (correct) formula for the number of subsets of U of size k is polynomial.
- (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|}.
- Only subsets of U of size exactly k are related to.
- The algorithm for checking whether a vertex subset is a vertex cover of G is not described or referenced.

**final**grades, grade components are visible under "grader notes".

A 8 point grade correction has been applied to test grades.

Due to the consolidated administrative staff leave, scanned notebooks should only become available next Sunday.

We need your answers rewritten in a Word file. Contact prof. Dinitz for getting a scanned copy of your work.

Yefim

We need your answers rewritten in a Word file. Contact prof. Dinitz for getting a scanned copy of your work.

Yefim

I intend to hold the office hour on Sunday 16-17.

Phone 08-647-7867 before coming, to ensure that I am in the office.

Yefim

The final grades were computed using the formula detailed on the courses main page since the beginning of the semester.

We will hold special office hours during the week before the next exam date (Moed Bet). Please check back here as the list may be updated in the coming days. Here is the current list:

- Ohad Ben Baruch - Tuesday, 28.7, 10:00-12:00
- Gal Amram - Tuesday, 28.7, 12:00-14:00
- Ariel Sapir - Wednesday 29.7, 10:00-12:00
- Uri Stemmer - Wednesday, 29.7, 12:00-14:00
- Tomer Sidi - Thursday, 30.7, 12:00-14:00
- Yehonatan Cohen - Thursday, 30.7, 14:00-16:00
- Eden Chlamtáč - Sunday, 2.8, 12:00 - 14:00

גל

**final**grades, grade components are visible under "grader notes".

My office hours this week will be given on wednesday (July 29^{th}) at 10^{00} -12^{00} in room 226/37.

See ya there!

תומר

Students e-mailing the course mailbox asking "when will grades be published?" are unfortunately distracting course staff who are trying to grade papers :)

- עמיר רובין - יום שני 6.7 בשעות 12:00-14:00
- אוהד טרבלסי - יום חמישי 9.7 בשעות 11:30-15:30
- בועז ערד - יום חמישי 9.7 בשעות 10:00-12:00
- גל עמרם - יום ראשון 12.7 בשעות 10:00-12:00
- אורי שטמר - יום ראשון 12.7 בשעות 12:00-14:00
- אריאל ספיר - יום ראשון 12.7 בשעות 12:00-14:00
- מיכל שמש - יום שני 13.7
**בשעות 12:20-14:20**-**עדכון** - יונתן כהן - יום שני 13.7 בשעות 12:00-14:00
- אוהד בן ברוך - יום שני 13.7 בשעות 14:00-16:00
- אוהד טרבלסי - יום שני 13.7 בשעות 15:30-19:30