CSE540 Theory of Computation (Fall 2013)
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 unsolvability,
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, quantum computation. (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 complexity theory and advanced topics.
Instructor: Jing Chen
Office: 1416 Computer
Science Building
Fall 2013 Office Hour:
Tuesday 2:00-3:00pm and Wednesday 4:00-5:00pm
TA: Roozbeh E. Soorchaei as a
quarter-TA for grading psets and exams.
Prerequisite: CSE303 or
equivalent ones
Lecture: MW
2:30-3:50pm, Melville Library E4330
Textbook: Introduction
to the Theory of Computation, M. Sipser, 2nd or 3rd edition.
Recommended reading:
Computational Complexity, S. Arora and B. Barak.
·
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. 28.
·
Please login to http://blackboard.stonybrook.edu/
to access board photos.
·
Problem Set 1 is here (also at Blackboard),
due by Wednesday, September 25 at 2:30pm.
·
Problem Set 2 is here (also at Blackboard),
due by Wednesday, October 9 at 2:30pm.
·
Midterm will be
on Wednesday, October 16 in class, covering materials till the end of Chapter
7.
·
Midterm
statistics: total score 60, max 53, min 9, median 38, mean 34.9, standard dev.
12.1.
·
Problem Set 3 is here (also at Blackboard),
due by Wednesday, November 13 at 2:30pm.
·
Office hour on
Monday, Dec. 9, 2pm-4pm.
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.
·
Midterm (25%)
October
16th in class.
·
Final (40%)
December
10th (Tuesday), 5:30pm-8:00pm, the same classroom.
·
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.
"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.