CS353 - Theory of Computation (Spring 2023)

Logistics: TTh 2:00--3:30, GDC 4.304 (in person only)
Unique Number: 52320
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: MTh 3:30 - 4:30
TA: Michael Jaber
Email: mjjaber@cs.utexas.edu
Office Hours: TBD
Who should
take this?
Students interested in the science of computation, who like mathematics and proofs, and who like a challenge. Students who liked CS 331 or 331H should like this class. This course is excellent preparation for graduate school.
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. The course should be similar to the 2018 version. (The 2021 version was flipped, but this year won't be.) 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 2-3 weeks
Space Complexity 8 1-2 weeks
Intractibility 9 1 week
Parallel Computation 10.5 1 lecture
Approximation & Randomization 10.1,10.2 1 week
Cryptography & Iteractive Proofs 10.4, 10.6 1 week

Prerequisites: CS 331 or 331H. Naturally, you also need the prerequisites and corequisites for CS 331, including Discrete Math (CS 311 or 311H), Probability (SDS 321 or M 362K), and Linear Algebra (SDS 329C, Math 340L, or Math 341).
Grading: 25% Midterm
40% Final Exam
25% Homework
10% Participation
Exams: The midterm will be held in class on Thursday, March 2. The final exam will be held in a room to be determined on Monday, May 1, from 1-3pm. 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).
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.
Additional Class
Policies

This class will follow the standard policies described in the CS Department Code of Conduct.

Last modified: January 6, 2023