[ Announcements | Homeworks | Distributions ]

CSc 473 Introduction to Theory of Computation
Time and place Fall 2006
Tuesday and Thursday, 2:00-3:15pm
Modern Languages 311
Discussion section Tuesday, 7:00-8:00pm, Modern Languages 311
Honors section Thursday, 3:30-4:30pm, Gould-Simpson 942
Dates
August 22
November 23
December 5 		  First class
  Thanksgiving Recess
  Last class
Instructor John Kececioglu
kece@cs.arizona.edu
(520) 621-4526
Office hours Tuesday 3:30-4:45pm, Wednesday 12:45-2:00pm, and by appointment
Gould-Simpson 720
Teaching assistants Milind Chabbi
milind@cs.arizona.edu
(520) 621-2738
Office hours Tuesday 12:30-1:45pm, Friday 1:00-2:15pm
Gould-Simpson 749C

Andrew Predoehl
predoehl@cs.arizona.edu
(520) 621-4089
Office hours Monday 10:30-11:45am, Thursday 9:30-10:45am
Gould-Simpson 710A
Description This course studies three basic questions:
  • What is computation?
  • What can be computed?
  • What cannot be computed?
In exploring these questions we examine three models of computation: finite automata, pushdown automata, and Turing machines. We characterize the class of problems that can be solved in each model (possibly when resources such as time and space are limited), as well as develop techniques for proving that a given problem cannot be solved.

These topics are mathematical by nature, and proofs are presented throughout. Skill in reasoning about computation and constructing proofs is developed through written assignments containing challenging exercises. This is a writing emphasis course.

Prerequisites CSc 345
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,
John Hopcroft, Rajeev Motwani, and Jeffery Ullman,
Introduction to Automata Theory, Languages, and Computation, second edition,
Addison-Wesley, Boston, MA, 2001.
Bernard Moret,
The Theory of Computation,
Addison-Wesley, Reading, MA, 1998.
Reserved books The above books will be placed on reserve in the Science Library.
Syllabus The course is organized in four parts, covering Chapters 1-5 and 7 of the text. (Chapter 0 on prerequisite material should be reviewed by students.) In parentheses after each topic below, are the corresponding section numbers from the text, followed by an approximate number of lectures.

I   Regular Languages   (Chapter 1; 8 lectures)

  • Deterministic finite automata (1.1; 1): computation as language recognition, finite state machines without memory.
  • Nondeterministic finite automata (1.2; 3): equivalence with deterministic finite automata, closure under regular operations.
  • Regular expressions (1.3; 2): equivalence with finite automata.
  • Nonregular languages (1.4; 2): Pumping Lemma for regular languages.

II   Context-Free Languages  (Chapter 2; 9 lectures)

  • Context-free grammars (2.1; 2): describing languages by rewriting rules, ambiguity.
  • Pushdown automata (2.2; 5): equivalence with context-free grammars.
  • Non-context-free languages (2.3; 2): Pumping Lemma for context-free languages.

III   Computability  (Chapters 3-5; 8.5 lectures)

  • Turing machines (3.1-3.3; 6): Church-Turing thesis, single- and multi-tape machines, nondeterminism.
  • Decidability (4.1-4.2; 2): decidable problems on regular and context-free languages, Halting Problem.
  • Reducibility (5.1-5.3; 0.5): reductions among problems to prove undecidability.

IV   Complexity  (Chapter 7; 2.5 lectures)

  • Measures of complexity (7.1; 0.25): orders of growth of functions, analyzing algorithms.
  • The class P (7.2; 0.25): polynomial-time solvable problems.
  • The class NP (7.3; 0.5): nondeterministic polynomial-time solvable problems, the P=NP question.
  • NP-completeness (7.4-7.5; 1.5): polynomial-time reducibility and completeness, Cook-Levin Theorem, examples of NP-complete problems, proving NP-completeness.
Exams There are two in-class exams and a final. The final is comprehensive and optional. Students attending the final must take it.
Homeworks There are five homeworks, which occur roughly every three weeks. The last homework is optional. Its points may be used to replace the lowest prior homework points.
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.

Without the final          
25%   Homeworks
35%   Exam 1
40%   Exam 2 		With the final
25%   Homeworks
20%   Exam 1
20%   Exam 2
35%   Final
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.)

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 to the TAs 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.

The attendance policy allows one unexcused absence in the first week, two unexcused absences in the first four weeks, and four unexcused absences in the first eight weeks. Students exceeding these limits may be dropped from class. Roll is taken at the start of class with a sign-in sheet; a missing signature on the roll sheet counts as an absence.

Distributions Current grade distributions are available here.
Grades A listing of course grades is available here. Grades are identified by the last six digits of the CSID. If you notice any discrepancies, please see the TAs or the instructor with the graded item.
Announcements

Course grades have been posted above.

A sample exam for the final exam has been posted above.

The assignment for Homework 5 has been posted above.

The solutions for Homework 4 have been posted above.

The solutions for Homework 3 have been posted above.

The solutions for Exam 2 have been posted above.


[ Top | Department ]

28 November 2006
John Kececioglu (kece@cs.arizona.edu)
http://www.cs.arizona.edu/classes/cs473/fall06/