| CSc 573 | Theory of Computation |
| Time and place |
Spring 2007 Tuesday and Thursday, 9:30-10:45am Gould-Simpson 701 | ||
| Dates |
| ||
| Instructor |
John Kececioglu kece@cs.arizona.edu (520) 621-4526 Gould-Simpson 720 | ||
| Office hours |
Tuesdays 2:00pm-3:15pm Wednesdays 11:00am-12:15pm and by appointment | ||
| Description |
This course studies the computational solvability of mathematical problems
within discrete models of computation.
In contrast to Computability Theory,
which studies what can and cannot be solved within a given model
of computation,
the main emphasis of this course is Complexity Theory,
which studies what can and cannot be solved within a given resource bound,
such as within a given amount of time or space.
Topics covered include the relationships between time- and
space-complexity classes defined on Turing machines,
the study of NP-complete and provably intractable decision problems,
and the complexity of approximation of NP-complete optimization problems.
These topics are mathematical, and proofs will be presented throughout. The emphasis is on written assignments containing challenging exercises. The key techniques learned are the simulation of one computational model by another, the reduction of one problem to another, and the classification of problems by their complexity. | ||
| Prerequisites | CSc 473 | ||
| Required text |
Michael Sipser, Introduction to the Theory of Computation, second edition, PWS Publishing, Boston, MA, 2006. (Errata are available here.) | ||
| Other books |
Other books on the subject that may be helpful are,
Daniel Bovet and Pierluigi Crescenzi, | ||
| Reserved books | The above books will be placed on reserve in the Science Library. | ||
| Syllabus |
The assumed background is Chapters 0-4 of the text,
on regular languages, context-free languages, Turing machines,
and decidability.
(This material should be reviewed by students.)
This course will cover Chapters 5 and 7-10 of the text,
on reducibility, time complexity, space complexity, and intractability.
I Introduction (Chapters 1-4)
II Reducibility (Chapter 5)
III Time Complexity (Chapter 7)
IV Space Complexity (Chapter 8)
V Intractability (Chapter 9)
VI Special Topics (Chapter 10)
| ||
| Exams | There are two exams and an optional final. The exams have both in-class and take-home parts. The final is comprehensive and optional. Students attending the final must take it. | ||
| Homeworks |
There are four homeworks, which occur roughly every three weeks.
| ||
| Grading |
Grades are determined from a weighted average of the percentage of points earned on homeworks and exams. The weights depend on whether the final is taken. Attaining a weighted score of at least 90% guarantees an A, at least 80% guarantees a B, at least 70% guarantees a C, and at least 60% guarantees a D. These thresholds may be lowered, but will not be raised. On homework and exam questions, writing an answer that relates to the question guarantees at least 50% of the points for the question (which is a failing percentage). No points are awarded for writing nothing. Homeworks may contain bonus problems. Points earned on bonus questions are not added to points for required questions. Bonus points are tallied separately at the end of the semester, and considered subjectively as a measure of effort when deciding whether to move up a student who is near a letter-grade boundary. | ||
| Policies |
For the overall course grade, the instructor reserves the right to give a grade of D or E to a student whose weighted average on the exams is a D or an E. On homework, very-high-level ideas can be discussed with friends, but solutions must represent individual work and must be written up separately. Use of solutions from previous offerings of the course is not permitted. Any material from the Internet that is used in a solution must be cited by its URL; to not cite it is plagiarism, which is considered cheating. (For more information, see the Department of Computer Science Course Policy on Collaboration and the University Code of Academic Integrity.) So that exams can go into some depth, they consist of both in-class and take-home parts. On take-home exams, individual effort is expected. Discussion of the exam with anyone (including other students, your friends, your spouse, significant other, or parents) is forbidden. The final is in-class and optional. When turning in solutions to homeworks, write only on one side of the paper, start each problem on a separate page, put the problems in the correct order, and staple the pages together. Neatness, and especially conciseness, is required to earn the highest marks. If a problem eludes solution, state this up front and write down only what you know to be correct. Rambling at length about attempts that didn't succeed may result in more points being deducted. Homework that is late (submitted after the due date and time) is not accepted. Requests for regrading homeworks or exams must be submitted within one week of receiving the graded homework or exam. There are no makeup exams. On missing an exam, the final may be used to replace one missed exam; grades will then be computed as if taking two exams and no final. There is no formal attendance policy. | ||
| Distributions | Current grade distributions are available here. | ||
| Announcements |
The solutions to Homework 3, Homework 4, and In-Class Exam 2 have been posted above. |