CSE 540 Theory of Computation
Fall 2009

• Course Information
• Announcements
• Homework Assignments

Course Information

Time:

12:50-2:10, Mon, Fri

Place:

Note: Room has changed. The new room is Stony Brook Union Room 236 (effective Friday, Sept. 4)

Professor:

Teaching Associate:

Dzejla Medjedovic
e-mail: dzejlam@gmail.com
office hour: 4-5pm, Tues., Rm 2110 CS building

Prerequisites:

An undergraduate course in Theory of Automata or Theory of Algorithms (equivalent to CSE 303) is required.

A student is expected to be able to read and write formal mathematical proofs.

Textbook:

D.-Z. Du and K. Ko, Theory of Computational Complexity, Wiley, 2000; ISBN 0-471-34506-7. (download errata (in PDF)). (This is the main textbook.)

(Optional) D.-Z. Du and K. Ko, Problem Solving in Automata, Languages, and Complexity, Wiley, New York, 2001; ISBN 0-471-43960-6. (download errata (in PDF)). (We will use part of Chapters 4 and 5 of this book in the first few weeks.)

References:

M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide tp the Theory of NP-Completeness, W.H. Freeman, 1979.

C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

Syllabus:

• Part I. Computability
  Turing Machines and Church-Turing Thesis (2 classes)
  Partial recursive functions, r.e. sets (2 classes)
  Halting problems, diagonalization (2 classes)
  Reductions and noncomputable problems (3 classes)
• Part II. Computational Complexity
  Complexity classes and time/space hierarchies (2 classes)
  Nondeterministic Turing Machines and NP (1 classes)
  P-reducibility and NP-complete problems (2 classes)
  Polynomial-time hierarchy (2 classes)
  PSPACE-completeness (2 classes)
• Part III. Probabilistic Computation
  Randomized algorithms and Probabilistic Turing machines (2 classes)
  Probabilistic complexity classes RP and BPP (2 classes)
  Counting classes (2 class)
  PCP and NP-hard approximation problems (2 classes)

Grading: ^{1, 2}

• Homeworks (50%)
  Homework questions are divided into three categories: Basic, Medium, and Hard. To get a passing grade, you must complete at least 50% of Basic problems, and 50% Medium problems. For students who take this course as part of the PhD qualifier, you must complete at least 70% of Basic problems, 70% Medium problems, and at least one Hard problem.
  To demonstrate your understanding of your own solutions, each student is required to present to the class his/her solutions of at least one Medium and at least one Hard problems.
• Two midterm tests (25% each; tentative dates: 10/19, 12/4; in class, open book)
• Final Exam: There is no written final exam. The presentation of solutions to medium/hard problems is part of the final oral exam.

2. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to Disability Support Service.

3. Because one of the main goals of this course is to teach professionalism, any academic dishonesty will be viewed as the evidence that this goal has not been achieved and will be grounds for receiving a grade of F. (See CEAS Procedures and Guidelines Governing Academic Dishonesty, 1/81)

Announcements

• The million-dollar problem P vs. NP can be found here
• 9/1: Right after we talked about the persecution of Turing yesterday, here is this news about Turing
• 9/11: Now, British government offered apology to Turing
• 9/21: There are some questions concerning homework problem set 1; please see the remarks in the homework section below).
• 9/21: Please note that I have changed the homework policy. In particular, I have reduced required solutions for hard problems. Instead, I put most problems in the Medium part.
• 9/28: Here is the writeup for Post Correspondence Problem.
• 10/13: We will have test 1 on next Monday, 10/19. It will cover the materials of Homeworks 1 and 2. The details will be discussed in Friday's (10/16) class.
• 10/14: I just found out that I uploaded a wrong file yesterday. If you downloaded homework 2 on 10/13, please redo it now.
• 10/15: You might find this report on the current status of the P vs. NP problem interesting.
• 11/6: To avoid confusion, I am adjusting the homework policy for homeworks 3 and 4 as follows:
  For each question, a student can only submit solution to the question once. He/she can still submit it anytime before its solution is discussed in class, but once the solution is submitted, he/she cannot re-submit or modify his/her solution.

Homework Assignments

Homework Policy

• Discussion of homeworks is encouraged, but direct copying (from a classmate's homework or from a textbook or from a webpage) is prohibited. When a homework solution is suspected of copying, the student will be asked to present his solution.
  If a student cannot explain clearly how his/her solution works, it will be considered as cheating.

Homework Set 1

• Due Sep. 29
• Download problem set 1 (typos corrected on 9/16)
• Remarks about Homework problem set 1:
  (1) Problem B3 is not covered yet. The due date for B3 will be delayed to later date.
  (2) For problem 1.2(b), you do not need to prove properties (ii) or (iii). Instead, just prove that the function and its inverse are computable.

Homework Set 2

• Due Oct. 9
• Download problem set 2 (errors corrected on 10/2, an error of H2 corrected on 10/14)

Homework Set 3

• Due Nov 9, Mon. (discussion is open on Nov 13, Fri)
• New policy: see the Announcement Section above for the new policy for homework submission.
• Download problem set 3