| Logistics: | TTh 2:00-3:30 TAY 3.144 Unique Number: 55675 Course web page: http://www.cs.utexas.edu/~diz/353 |
|||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: TAY 3.134 Office Hours: TTh 3:30-4:30 |
|||||||||||||||||||||||||||
| TA: | Raghu Meka Email: raghu@cs.utexas.edu Phone: 471-9520 Office (for office hours): ENS 31NQ Desk #2: directions since it's slightly tough to find. Office (for all other purposes): TAY 3.108 Office Hour: M 3-4 |
|||||||||||||||||||||||||||
| Who should take this? |
Students interested in the science of computation, students who liked CS 341 or CS 341H, and students who like mathematics 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.
It is essentially a continuation of CS 341, but
is more in depth and focuses on more modern topics.
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.
This course should be similar to the
2007 version.
A list of topics and approximate times follows.
|
|||||||||||||||||||||||||||
| Prerequisite: | CS 341 or 341H with a grade of at least C. | |||||||||||||||||||||||||||
| Grading: |
20%: Homework (7-8 problem sets) 20%: Exam 1 20%: Exam 2 40%: Final exam |
|||||||||||||||||||||||||||
| Homework policy: |
Collaboration policy: You are encouraged to discuss homework
problems with your classmates.
However, you should think about the problems before discussing
them, and you must write up your own solutions.
In particular, nobody should email partial or full solutions
to anybody.
Finally, you must acknowledge any collaboration by writing
your collaborators' names on the front page of the assignment.
Citation policy: If you 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. Submission policy: Homeworks are due at the beginning of class. Late homeworks should be submitted directly to the TA. Late policy: You have two late days to use during the semester with no penalty (one assignment two days late or two assignments one day late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours (so it begins and ends at 2pm). However, an assignment due Thursday may be handed in Monday by noon for two late days. On occasion, an assignment may not allow late days. | |||||||||||||||||||||||||||
| Exams: | Exam 1 will be held in class on February 14, and Exam 2 will be held in class on March 27. The final exam will be held on Tuesday, May 13, from 2-5pm. 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 Disabilites: |
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. |