CSE 555 is an
advanced (second) course in the theory of computation.
It assumes knowledge of a standard first course covering finite automata, regular expressions, and regular languages;
pushdown automata, context-free grammars, and context-free languages;
Turing machines, Turing-recognizable (recursively enumerable) languages, and Turing-decidable (recursive) languages; the Church-Turing thesis;
and undecidability.
With this background, CSE 555 covers reducibility for computable problems; the recursion theorem; time complexity (including P, NP, NP-complete, PSPACE, PSPACE-complete, EXPTIME); and space complexity.
Office Hours Office Hours
Students are expected to have
formal (mathematical) background in
the introduction to the theory of computation (CSE 355 at ASU).
Course
InformationCSE 555: Theory of Computation
http://www.public.asu.edu/~ccolbou/src/cse555s16.html
Class Meeting Time
F 7:30-10:00 a.m.
BYAC 270
Instructor
Charlie Colbourn
Office: Brickyard 444
Charles.Colbourn@asu.edu
Thurs 9:00-10:00, Fri 10:15-11:15
on 02/04/16 changed to 1:00-2:00 rather than 9:00-10:00
TA
Ryan Dougherty
Office: Centerpoint 114 (for office hour)
ryan.dougherty@asu.edu
Weds 1:00-3:00
Prerequisites
Introduction to the Theory of Computation (CSE355 at ASU or equivalent)
Special Needs
If you are entitled to extra accommodation for any reason (such
as a disability), we make every reasonable attempt to accommodate you.
However, it is your responsibility to discuss this with the instructor
at the beginning of the course.
Academic Honesty
Work in this course, unless explicitly stated in writing to the contrary, is to be an effort by the individual student. It is not acceptable to use work other than your own without full attribution and acknowledgment. While you are welcome to discuss
problems with others, it is not acceptable to discuss solutions with them.
Depending on the severity of the infraction, penalties may include a grade of zero on the offending item, a grade of zero on the offending item and a reduction of the final grade by one full letter grade, a failing grade in the course with an indication of academic dishonesty. Such penalties might result in a requirement to withdraw from the university.
If in doubt about anything related to academic integrity, see the instructor.
TextBooks
Required Text
Michael Sipser, Introduction to the Theory of Computation, Third Edition, Thomson, 2012.