| Syllabus: | syllabus in pdf | ||||||||||||||||||||||||||||||
| Logistics: |
TTh 11:00-12:30
GDC 2.410 Unique Number: 51530 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: TTh 2-3 |
||||||||||||||||||||||||||||||
| TA: | Ridwan Syed Office Hours: WF 4-5, TA Station, GDC, Desk 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 341 or 341H, or CS 331 or 331H, or CS 357 or 357H should like this class. This course is excellent preparation for graduate school. | ||||||||||||||||||||||||||||||
| Class is waitlisted? | If this class is waitlisted and you want to take it, please come to the first few classes. In the past, space has opened up as students dropped it. Every student who has wanted to enroll in previous versions of this class has been able to. | ||||||||||||||||||||||||||||||
| 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.
A list of topics and approximate times follows.
|
||||||||||||||||||||||||||||||
| Prerequisites: | The following coursework with a grade of at least C-: CS 429 (or 310) and CS 331 (or 341 or 357), or equivalent honors versions. Naturally, you will also need the prerequisites of these prerequisites, especially Probability (SSC 321 or M 362K). Automata Theory (CS 341) is helpful but not required. | ||||||||||||||||||||||||||||||
| Grading: | 10% Quiz 25% Midterm 30% Last Exam 25% Homework 10% Participation |
||||||||||||||||||||||||||||||
| Exams: | The three exams will be held in class on the following dates: the Quiz on Thursday, September 6; the Midterm on Tuesday, October 11; and the Last Exam on Thursday, December 1. 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. You must write up your own solutions. In particular, nobody should email partial or full solutions to anybody. 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. Submission policy: Homeworks are due at the beginning of class. 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, 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. | ||||||||||||||||||||||||||||||
|
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. |