CSE540 Theory of Computation (Fall 2014)

Course Description

The purpose of the course is to study the capabilities and limitations of computers by formulating mathematically various models of idealized computers and establishing rigorously for these models what kinds of problems can and cannot be solved, as well as what kinds of problems can and cannot be solved with a reasonable amount of computing resources.

Topics include but not limited to:

Computability theory: Turing machines, Church-Turing thesis, halting problem and undecidability, universal Turing machine, introductory recursion theory;

Complexity theory: complexity measures, time and space hierarchy, NP-complete problems, intractability;

Advanced topics: probabilistic algorithms, interactive proofs, cryptography, computational game theory. (Exact topics covered depend on the class progress.)

An introductory treatment of Turing machines would typically be part of an undergraduate course in the theory of computation, which is a prerequisite for this course. Though I will cover this topic, the treatment will be fairly speedy, so as to leave enough time for other topics.

Staff

Instructor: Jing Chen

Office: 1416 Computer Science Building

Fall 2014 Office Hour: Tuesday 4:00-5:00pm

Grader: Shikha Singh

Logistics

Prerequisite: CSE303 or equivalent ones

Lecture: TuTh 2:30-3:50pm, Computer Science 2129

Textbook: Introduction to the Theory of Computation, M. Sipser, 2nd or 3rd edition.

Recommended reading: Computational Complexity, S. Arora and B. Barak.

Announcements

· Please fill out the sign-up and background questionnaire and bring it back to me if you haven’t already done so. You can also get a hard copy in class on Aug. 25.

· Please login to http://blackboard.stonybrook.edu/ to access board photos.

· Please email Jing directly about any enrollment problem.

· Please type all your homework solutions using LaTeX. Template will be provided later.

· The first exam will be on Oct. 21 in class.

Grading Policy

The grade will be based on four parts.

· Homework (30%)

Homework assignments will be bi-weekly or tri-weekly. You can discuss the problems with other students taking this class, and actually you are encouraged to do so. But I suggest you not discuss a problem with others until you have made serious effort trying to solve it by yourself.

You must write up and submit your solution individually, and you must acknowledge for each problem with whom you have discussed. If more than one student submits substantially the same writeup for a particular problem, or if there is some other evidence that the writeup you submit is not your own work, I will regard this as evidence that you are trying to get a higher grade without actually doing the required work and may choose either to make a corresponding deduction from your homework score or (in egregious cases) to pursue the matter as a case of academic dishonesty.

Note! If you really don’t know how to solve a problem after making serious effort, write “I honestly don’t know how to solve this problem” and you’ll get 25% of it. While if you “make up” a solution by putting together some random sentences, you may get lower than that. Indeed, I believe that to realize that you don’t understand something is an important step towards understanding it.

· Two in-class exams. The first is on Oct. 21 and counts for 25%; and the second is in the last lecture and counts for 40%.

· Class participation (5%)

I encourage you to answer questions and to ask questions in class, as I believe that interaction is an efficient way of learning.

Students with Disabilities

"If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disability Support Services office (DSS), ECC Building (behind SAC), 632-6748/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential."

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 this web site and search Fire Safety and Evacuation and Disabilities.

Critical Incident Management

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn.