CSE 540 Theory of Computation
Fall 2011

• Course Information
• Announcements
• Homework Assignments

Course Information

Time:

12:50-2:10, Mon, Fri

Place:

Harriman, Room 108

Professor:

Teaching Associate:

There is no TA this semester.

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.
If you did not take the undergraduate theory course, it is very likely that you will not be able to follow the pace of the lectures.

Textbook:

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)).

References:

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

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

Syllabus:

• Part I. Computability
  Turing Machines and Church-Turing Thesis (4 lectures)
  Partial recursive functions, r.e. sets (3 lectures)
  Halting problems, diagonalization (2 lectures)
  Reductions and undecidable problems (3 lectures)
• Part II. NP-Completeness
  Complexity classes and time/space hierarchies (2 lectures)
  Nondeterministic Turing Machines and NP (2 lectures)
  P-reducibility and NP-complete problems (4 lectures)
  Turing reducibility and Polynomial-time hierarchy (2 lectures)
  PSPACE-completeness (2 lectures)

Grading: ^{1, 2}

• Homeworks (34%)
  Homeworks are an important part of the class work. Each student must complete at least 70% of the homework assignment to get a passing grade. To demonstrate your understanding of your own solutions, each student is required to present to the class his/her solutions of at least one nontrivial problem. For a PhD student taking this class to fulfill the qualifier exam, it is expected that he/she will present at least two solutions.
• A midterm exam (33%; tentative date: 10/17, in class, open book)
• Final Exam (33%; date: 12/15. Thur, 2:15pm-4:45pm, open book)

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/26: Please note that this week we have a WEDNESDAY class (Sep. 28, same time), as Friday is a holiday and Wednesday follows the Friday schedule.
• Homework 1 presentations:
  Oct 7, Fri: Gutenko, 4.5.3(b)
  Oct 7, Fri: Niu, 4.2.4(e)
• Homework 1 presentations continue:
  Oct 10, Mon: S. Han, 4.5.3(d)
  Oct 10, Mon: J. Han, 4.6.1(g)
  Oct 10, Mon: Su: 4.6.7
  Oct 14, Fri: Malik: 4.6.6
  Oct 14, Fri: Ghasemiesfeh, 4.7.7
  Note: These are all presentations for Homework 1. Homework 2 has been posted. Those who did not get a chance to present solutions for homework 1 can select your presentations from Homework 2 problems.
• 10/11: We will have mid-term exam on Monday, Oct 24. It will be an open-book test. It covers the materials of Homeworks 1 and 2.
• 10/16: Homework 2 presentations:
  Oct 17, Mon: Jung, 5.2.3(b)
  Oct 17, Mon: L. Chen, 5.2.7(b)
  Oct 21, Fri: V. Ashok, 5.2.7(c)
  Oct 21, Fri: L. Niu, 5.3.4
  Oct 21, Fri: C. Xu, 5.3.6
• 10/25: We will have a special presentation
  Oct 28, Fri: F. Ji, 5.3.8.
• 11/19: We will have the following presentations of homework 3:
  Nov 21, Mon: Nampally, 5.4.9(c)
  Nov 21, Mon: Gukenko, 5.4.9(i)
  Nov 21, Mon: Ghasemiesfeh, 5.4.7
  Nov 21, Mon: Zheng, 5.4.9(f)
• 11/23: Homework presentations on Mon, Nov. 28:
  Nov 28, Mon: Zheng, 5.4.9(f) (continued)
  Nov 28, Mon: Yang, 5.6.1(a)
  Nov 28, Mon: S. Han: 5.4.4(a)
• More presentations have been scheduled:
  Dec 2, Fri: Vitas Ganjugunte, 5.6.1(c)
  Dec 2, Fri: Ni, 5.6.1(e)
• Presentations of Homework 4 questions:
  Dec 9, Fri: Tulshigiri, 7.1.7(a)
  Dec 9, Fri: Su, 7.2.3(b)
  Dec 9, Fri: C. Xu, 7.2.4 (first part)
  Dec 9, Fri: Ni, 7.5.1(c)
• 12/6: Fianl Exam Info: Final exam will be held on Dec. 15, Thur, from 2:15pm to 4:45pm, at the regular class room (Harriman 108). It will be an open-book, 150-min test. The detail of the exam will be discussed at Friday's class.
• 12/9: The final exam will have 3 problems: One on proving a set recursively enumerable or not recursively enumerable (Section 5.4); one on the concept of NP (Section 7.1); and one on proving a problem NP-complete (Sections 7.2 and 7.4).

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.
• Homeworks will have a due date. Presesntation of the solutions will begin after the due date. Late homworks (of an individual problem or the whole assignment) are accepted as long as the solution to that problem is not discussed in the classroom. Written solutions to the homework problems will not be posted.

Homework Set 1

• Due Oct. 5, Wed.
• Part 1
Section 4.1: 3(a), 3(b)
Section 4.2: One of the following problems: 3(b)*, 4(e)*
Section 4.3: 4(e)
Section 4.5: 2(a), 2(b), 3(b)*, 3(d)*, 3(h)*
• Part 2
Section 4.6: 1(b), 1(g)*, 6*, 7*
Section 4.7: 1(b); and one of the following:(5(a), 7*)
• The problems with * are considered nontrivial. We begin the presentation of these nontrivial problems on Fri., Oct. 7.

Homework Set 2

• Due Oct. 17, Mon (presentation of solutions begins on 10/17).
• Problems:
Section 5.2: 3(a), 3(b)*, 7(b)*, 7(c)*
Section 5.3: 2, 3(b)*, 4*, 6*
• The problems with * are suitable for presentation.

Homework Set 3

• Due Nov. 21, Mon (presentation of solutions begins on 11/21).
• Problems:
Section 5.4: 4(a), 7, 9(c), 9(f), 9(i)
Section 5.6: 1(a), 1(c), 1(e), 5(c), 5(d)
• Every assigned problem is suitable for presentation. In addition, you may propose to present exercise problems in the book that are not assigned here, e.g., problem 2 and 4 of Section 5.6.

Homework Set 4

• Due Dec. 5, Mon (presentation of solutions begins on 12/5).
• Problems:
Section 7.1: 1, 7(a)
Section 7.2: one of 3(a), 3(b), 3(c); and 4
Section 7,5: 1(c)
• Note: For problem 7.2.4, you need only prove two main reductions:
  3Sat ≤_m^P 3Sat-Exactly-One, and 3Sat ≤_m^P 3Sat-Not-All.