CS353 - Theory of Computation (Fall 2016)

Syllabus: syllabus in pdf
Logistics: TTh 11:00-12: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: 471-9729
Office: GDC 4.508
Office Hours: TTh 2-3
TA: Ridwan Syed
Office Hours: WF 4-5, 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.

Topic Chapter(s) Approximate Time
Regular Languages 1 1-2 weeks
Decidability 3-4 1-2 weeks
Reducibility 5 1 week
Time Complexity 7 3-4 weeks
Space Complexity 8 2-3 weeks
Intractibility 9 1 week
Parallel Computation 10.5 1 lecture
Approximation & Randomization 10.1,10.2 1 week
Cryptography 10.6 1 lecture

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 make-up 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 NP-complete problems
2SAT in P
Certificate definition of NL is Definition 4.17 (Chapter 4) in Arora & Barak's graduate-level 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 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.

Last modified: November 7, 2016