## CS353 - Theory of Computation (Fall 2018)

Syllabus: syllabus in pdf
Logistics: TTh 11:00-12:30
GDC 6.202
Unique Number: 51605
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: M 3-4, W 2-3
TA: Subham Ghosh
Email: subham.g@utexas.edu
Office Hours: F 11-12, GDC 1.302
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 2016 version. 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 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-2 weeks

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).
45% Final Exam
25% Homework
5% Participation
Exams: The midterm will be held in class on Thursday, October 18. The final exam will be held in the usual classroom on Saturday, December 15 from 7-10pm. 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).
Homework: Most weeks a problem set will be assigned.

Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.

Late policy: No late homeworks will be accepted.

Participation and Attendance: Your participation grade is based on the quality and quantity of your participation. While attendance is not required, poor attendance will be reflected in your participation grade.
Laptops/Phones: The use of laptops and mobile devices is generally prohibited; however, you may use a tablet if you sit in the first row and use it 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.
Useful Pointers: Theory of Computing Blog Aggregator
P vs. NP page
List of many NP-complete problems
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.