Unique Number: 51605
Course web page: http://www.cs.utexas.edu/~diz/353
Office: GDC 4.508
Office Hours: TBD
|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|
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 2016 version.
A list of topics and approximate times follows.
|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).|
|Laptops/Phones:||The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and use them only for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced.|
|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.|
Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
|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.|