CS353 - Theory of Computation (Spring 2021)

Logistics: TTh 3:30--5:00
Unique Number: 52505
Use Zoom links from Canvas.
Syllabus posted on Canvas.
Course web page: http://www.cs.utexas.edu/~diz/353
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office Hours: M 4:15-5:15, W 2-3
TA: Zihang He
Email: zhhe AT utexas.edu
Office Hours: WF 1-2
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
Videos: Most of this class will be flipped -- you'll be required to watch videos at home, and we will solve problems and answer questions in class. The videos, made by colleagues and myself, may be found here
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 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: 60% 3 Exams
30% Homework
10% Participation
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.

Last modified: January 18, 2021.