**CSE540 Theory of Computation (Fall 2016)**

**Course Description**

In a nutshell, this course is about “sequencing the DNA of
computation”. You will see a lot of fancy stuff that you do not get to see
elsewhere, and you should be prepared for some hard work. Students who are
motivated to understand the theoretical foundations of computation, have a
solid math background, and enjoy reading and writing rigorous mathematical
arguments are particularly encouraged to take this course.

More specifically, 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.

Instructor: Jing Chen

Office: 247 Computer
Science

Fall 2016 Office Hour:
Monday 4:00-5:00pm or by appointment

Prerequisite: CSE303 or
equivalent ones

Lecture: MW 2:30-3:50pm,
Room 2120, old CS building

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

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

Course website: http://www3.cs.stonybrook.edu/~cse540/

·
We will use
Blackboard (http://blackboard.stonybrook.edu/)
for future announcements and course materials. Course Calendar can be found in
Course Tools.

·
Syllabus from 2015. Materials covered this year may
be adjusted.

·
Please type your
homework solutions using LaTeX. Template
is here.

·
Problem Set 0: Academic Honesty Review. Due in class by
Sep. 7, 2:30pm.

The grade will be based
on the following parts.

·
Homework (20
points in total)

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

**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, to realize that you
don’t understand something is an important step towards understanding it.

·
Two in-class exams
(60 points in total)

·
Course project (15
pts)

You’ll
form groups (group size depending on class size). Each group will choose
1 paper and present to the class. The paper must be published in the last
5 years in major theory conferences and the topic must be related to the
materials covered in class.

·
Class
participation (5 pts)

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

·
Bonus (5 pts)

For
homework and exam problems, I may need students to prepare detailed solutions to be distributed to the class. You can
claim the 5 bonus points by preparing solutions for problems that I assign to
you.

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

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.