| Syllabus: | Here is the detailed syllabus in pdf format | |||||||||||||||||||||||||||
| Logistics: |
TTh 2:00-3:30
ENS 31NM (in lower basement of ENS) Unique Number: 53495 Course web page: http://www.cs.utexas.edu/~diz/353 |
|||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: CSA 1.120A Office Hours: TTh 3:30-4:00, or by appointment. |
|||||||||||||||||||||||||||
| 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
2010 version.
A list of topics and approximate times follows.
|
|||||||||||||||||||||||||||
| Prerequisite: | CS 341 or 341H with a grade of at least C. Often the prerequisite is waived for strong students, such as those who got an A in CS 336H or 357, who are willing to do some extra reading. Please discuss this with me first. | |||||||||||||||||||||||||||
| Grading: |
75%: 3 Exams 15%: Homework 10%: Participation |
|||||||||||||||||||||||||||
| Homework: |
There will be about ten short problem sets throughout the semester.
Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Moreover, 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: 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. Submission policy: Homeworks are due at the beginning of class. Late policy: Late homeworks will not be accepted. Grading policy: Because this class has no TA, I do not expect to grade all homework problems. Rather, I will grade at least one problem from every problem set. | |||||||||||||||||||||||||||
| Exams: | The three exams will be held in class on the following dates: Exam 1 on Thursday, February 17; Exam 2 on Thursday, March 24; and Exam 3 on Thursday, May 5. 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). | |||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is prohibited. All phones must be silenced. | |||||||||||||||||||||||||||
|
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. |