Computer Science

0368.3168

Spring 2009 
Out  Due  Questions 
3/3/2009  17/3/2009  Homework 1 
17/3/2009  24/3/2009  Homework 2 
24/3/2009  31/3/2009  Homework 3 
31/3/2009  21/4/2009  Homework 4 
05/5/2009  19/5/2009  Homework 5 
19/5/2009  02/6/2009  Homework 6 
31/5/2009  14/6/2009  Homework 7 
14/6/2009  03/7/2009  Homework 8 
Lectures  Group 1: Tuesday 10:0013:00, Schreiber 006 Group 2: Monday 10:0013:00, Shenkar 222 Recitations: Tuesday 15:0016:00 Kaplun 118, 16:0017:00, 18:0019:00 Schreiber 008. 

Instructors 
Oded
Regev  Schreiber 103  6407996  Office hour: Monday 13:00 Muli Safra  Schreiber 319 6405371  
T.A 
Ido BenEliezer  Schreiber Open Space  6405398 Ishay Haviv 

Lecture notes  PowerPoint presentations
used in Safra's lectures. Previous courses in TAU:Spring 2007, Spring 2008, Fall 2008 Oded Goldreich from Weizmann (see also here) 

Textbooks 
Main
references:


Requirements 
Attendance, homework assignments  
Prerequisites 
Computational models, Algorithms  
Other links 
A compendium
of NPcomplete
problems and what's known about them. A compendium of problems in higher levels of the hierarchy, part I and part II. The zoo of all(?) known complexity classes. Previous exams in our course 
Week  Date  Class Topics 
1  Mar 2, Mar 3  
Mar 3  P, NP and coNP are closed under the Kleene star.  
Mar 9  Bonus Class: ErrorCorrectingcodes, in particular the ReedSolomon code and the Hadamard code.  
2  Mar 16, Mar 17  
Mar 17  Karp reductions versus Cook reductions.  
3  Mar 23, Mar 24  
Mar 24  
4  Mar 30, Mar 31  
Mar 31  
5  Apr 20, Apr 21  
Apr 21  
Apr 27  Bonus Class: Communication Complexity  
6  May 4, May 5  
May 5  
May 8  Mid Term Exam  
7  May 11, May 12  
May 12  
8  May 18, May 19  
May 19  
9  May 25, May 26  
May 26  
10  June 1, June 2 

June 2  
11  June 8, June 9  Random Computations:

June 9  
12  June 15, June 16  
June 16 