Introduction to the Theory of Computation

 

Instructor:  Vadim Lyubashevsky   vlyubash@cs.ucsd.edu

                    Office Hours: Monday 2-3pm; in EBU3 Room B250A

TA: Scott Yilek   

                    Office Hours: Wednesday 2-3pm  in EBU3 Room B250A

        

Class meetings:  Monday, Wednesday, Friday  4-5:50pm in Center Hall 218

Discussions:  Tuesday, Thursday  4-4:50pm in Center Hall 218

Textbook: Introduction to the Theory of Computation, Second Edition by Michael Sipser

Class lectures:  http://up.ucsd.edu/   (Sign up for an account, then enroll in VadimCSE105. There is no password.)

                      Go to http://up.ucsd.edu/about/StudentWelcome.html for a short tutorial

Homeworks (due at the beginning of class):

HW1 (Due Wednesday, July 2)

0.3, 0.12, 1.6abcfgh, 1.7bd, 1.16, 1.22a, 1.31, 1.32, 1.34

(If you only have access to the first edition of the book, do the following problems:

0.3,1.4abcfgh,1.5bd,1.12,1.24,1.25,1.27 and the two problems from this link)

HW2 (Due Monday, July 7)

1.8a,1.9a,1.10a,1.18cdfgj, 1.19, 1.38, 1.40b, 1.48

(If you only have access to the first edition of the book, do the following problems:

1.6a,1.7a,1.8a,1.13cdfgj, 1.14, 1.31, 1.32b, 1.41)

HW3 (Due Wednesday, July 9)

1.39,1.46acd, 1.47, 1.49, 1.53, 1.54

HW4 (Due Monday, July 14)

2.1, 2.2, 2.6bd, 2.13, 2.15, 2.16, 2.17, 2.30ad, 2.31, 2.32, 2.43

HW5 (Due Monday, July 21)

3.6, 3.7, 4.3, 4.12, 4.19

HW6 (Due Wednesday, July 23)

4.6, 4.7, 4.28

HW7 part 1(Due Friday, July 25)

5.9

HW7 part 2(Due Monday, July 28)

5.12, 5.22, 5.23, 5.33

HW8 (Due Wednesday, July 30)

7.5, 7.6, 7.7, 7.9, 7.21

HW9 (Due Friday, August 1st)

7.30, 7.34

(Hint for 7.30: Reduce from 3SAT)

 

Grading breakdown:

Homework - 20%

Midterm (July 16th) - 30% or 0%

Final (August 2nd) - 50% or 80% 

 

Re-grade Policy: There are no re-grades for homework.  For the midterm, the re-grade request must be made in writing (unless we added up the points wrong) no later than the class immediately following the one in which the midterm has been returned.  The entire disputed question will be re-graded, thus the total grade may go either up or down.