Complexity (89-320)

(2013)


       Home | Recitation Notes | Exercises | Grades | Quizes | Exam | Announcements

General Information


Semester A

Lecturer: Yair Dombb
Tuesday, 12:00-14:00, Building: 605, 11

Teaching Assistant: Gilad Asharov
Tuesday, 14:00-15:00, Building: 505, 61


Grades: 90% final exam,
               5% Quiz I
               5% Quiz II
What if I cannot attend one (or both) of the quizzes?


Important dates: 19.11 Quiz I
                             24.12 Quiz II



Recitation Notes


Rec1 (23/10 - self reducibility)
Rec2 (30/10 - P, NP, NPC, coNP)
Rec3 (06/11 - Integer Programming. Thanks to Hila Zarosim!)
Rec4 (13/11 - The Polynomial Hierarchy (I))
Rec5 (20/11 - The Polynomial Hierarchy (II))
Rec6 (27/11 - Space Complexity (I))
Rec7 (04/12 - Space Complexity (II))
Rec8 (11/12 - P/Poly)
Rec9 (18/12 - Randomized Algorithms)
rec10 (25/12 - Randomized Computation(I))
Rec11 (01/01 - Randomized Computation(II))
Rec12 (08/01 - PCP and Hardness of Approximation(I))
Rec13 (15/01 - PCP(II))



Exercises

(not for submission)

Exercise 1 (sol)   additional question (sol)
Exercise 2 (soladditional questions (sol)
Exercise 3 (sol)
Exercise 4 (sol)
Exercise 5 (sol)
Exercise 6 (sol)
Exercise 7 (sol)
Exercise 8 (sol)
Exercise 9 (sol)
Exercise 10 (sol)
Exercise 11 (sol)
Exercise 12 (sol)


Grades


Quiz 1 + 2


Quizes


Quiz1
Quiz2



Exam


Exam A (sol)



Announcements


10.02 : Please look at the followig file regarding the exam here