Syllabus:  syllabus in pdf  
Logistics: 
TTh 11:0012:30
GDC 2.410 Unique Number: 51530 Course web page: http://www.cs.utexas.edu/~diz/353 

Professor:  David Zuckerman Email: diz@cs.utexas.edu Phone: 4719729 Office: GDC 4.508 Office Hours: TTh 23 

TA:  Ridwan Syed Office Hours: WF 45, TA Station, GDC, Desk 2. 

Text:  Michael Sipser, Introduction to the Theory of Computation  
Course Overview: 
This undergraduate course develops a theoretical framework
to understand computation.
Perhaps the most important concept in the class is that there are
limits to computation.
Some languages are uncomputable; others are "complete"
for certain hard classes, such as NP. Sometimes these
limitations prove useful, as in the case of cryptography. We will
also explore tradeoffs and relationships between different computational
resources, such as time and space.
A list of topics and approximate times follows.


Exams:  The three exams will be held in class on the following dates: the Quiz on Thursday, September 6; the Midterm on Tuesday, October 11; and the Last Exam on Thursday, December 1. No makeup exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary).  
Useful Pointers: 
Theory of Computing Blog Aggregator
P vs. NP page List of many NPcomplete problems 2SAT in P Certificate definition of NL is Definition 4.17 (Chapter 4) in Arora & Barak's graduatelevel textbook Computational Complexity: A Modern Approach. Complexity of various games and puzzles  
Students with Disabilities: 
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 4716259 (voice) or 4714641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations. 