Please make sure that the email you send us with the summary of your chores has the following subject:

compecon: summary of chores


A hint

1. A hint was added to q.2 in ex.3.

2. In part (e) of q.3, the time of the algorithm should be $n^{O((log n)/\epsilon^2)}$ rather than $O(n^{(log n)/\epsilon^2})$.

Course Requirements

We are starting to “close up” the course administrative leftovers, so here it goes:

  1. There will be no fourth exercise.  (Hooray?)
  2. Handing in EX3 is postponed by a week – to the 17th.  No more.
  3. Those that did not finish the three (3) course duties (wikipedia-entry + 2 of {lecture-notes, grading-a-question, writing-solution-to-question}) have to complete an additional requirement from the following list:
    • Read a paper of your choice in the area and extract from it the simplest interesting result and write it up.  The idea is to write a full and formal exposition (including definitions and proofs) of one small thing in the paper.  Can be done in pairs.  Expected length 1-2 pages.  No more.
    • Suggest an application of game-theory to something related to computer science or computer systems that you have not seen anywhere yet.  Write up the basic model and questions that seem interesting.  Can be done in pairs.  Expected length 1-2 pages.  No more.
    • An additional wikipedia entry.
    • Suggest an interesting chore of your own choice — and let us approve it.  Can be done in any group size – but we have to approve before hand also the group size.
  4. In order to get a grade in the course you must send us an (michal&noam) an email with the following pieces of information:
    • name & id number
    • The list of the 3 chores that you did, including the names of your partners in each
    • The URLs of the wikipedia entries as well as the URLs to the lecture-notes or ex-solutions (which of course you have already previously sent us and we uploaded to the site.)
    • A statement of how many classes you have missed during the semester.  If the number is greater than 3 then you must speak with one of us in person.
  5. The deadline for completing all chores as well as sending us the email above is one week after classes end: 31/1.  Delays of up to one additional week will be penalized in the grade.


The drawings that I projected in class today are from: http://www.csc.liv.ac.uk/~pwg/PPADintro/PPADintro.html

Question 2 correction

In question 2, all the functions need to be to {-1,1} rather than to {0,1}.


A (partial) list of grades for Ex 1 appears here.

We ask all the graders (including those of questions 2&3 in EX 1) to please submit the grades in this Excel sheet.