Syllabus

Course description and Goals

This course is a theoretic exploration of computing devices. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computing device? How does one determine if a given problem can or cannot be computationally solved? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and which problems cannot be solved on a computer? How does the power of a computer change, if it has access to random bits?

In attempting to answer these questions we will study the following topics:

  1. Computation models: Finite State Automata.
  2. Regular Expressions and Regular Grammars.
  3. Context-free Grammars and Pushdown Automata.
  4. Computation models: Turing machines (TM).
  5. Turing-decidable and Turing-recognizable languages.
  6. Enhancements of TMs: multi-tape TMs, non-deterministic TMs. Equivalence of these and the standard TM.
  7. Diagonalization. Acceptance problem is undecidable; Acceptance problem is recognizable; the complement of the Acceptance problem is unrecognizable.
  8. Reductions. Examples of other undecidable languages. Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
  9. Running time of Turing Machines. The classes P, NP, NP-hard, and NP-complete.
  10. Cook-Levin Theorem, some reductions.
  11. Space complexity, Savitch's Theorem, PSPACE. Quantified boolean formula satisfiability is PSPACE-complete. So is Generalized Geography.
  12. The space hierarchy and the time hierarchy theorems.

Textbook

Introduction to the Theory of Computation(third edition) by Professor Michael Sipser. The latest errata can be found at math.mit.edu/~sipser/book.html

Homeworks

Several small assignments will be given, covering the material from the textbook and the lectures, and to be done individually. All assignments will be collected and graded.

Exams

There will be two midterm exams and one final exam. The midterms will be held during class time. The final exam will be held as per university schedule.

Grading

The weighting of items in grade determination will be the following:


Item Weight
Homework 25%
Midterm Exam 1 20%
Midterm Exam 2 20%
Final Exam 35%


The following cutoffs will be used to determine letter grades. In the ranges below, x stands for your total score at the end of the semester. Final scores near a cutoff will be individually considered for the next higher grade. Plus (+) and minus (-) grades will also be given; their cutoffs will be determined at the end of the semester.


Score Grade
88 <= x < 100 A
75 <= x < 88

B
60 <= x < 75 C
50 <= x < 60 D
00 <= x < 50 F

Grades are not curved in this course. It is theoretically possible for everyone in the class to get an A (or an F). Your final grade depends only on your own final score and not on that of others.

Cheating

Academic dishonesty will not be tolerated. In particular, under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the Internet.

Graded Homework: Sharing solutions of graded homework (assignments and project) between students/teams or copying someone else's work, including posted solutions from previous editions of the course, is not allowed. Doing that will result in a zero on the assignment and a report to the CS department's chair and the college.
You are allowed and encouraged to discuss with students in other teams concepts and ideas that relate to the class and the homework assignments. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Exams: The midterm exams are individual tests. Each student must be complete them without any help from others. Exam answers showing strong similarities and/or duplication will receive a fail grade and the students involved will be reported to the Department and the College.
If you are unclear about what constitutes academic dishonesty it is your responsibility to contact the instructors or consult the CLAS policy (online version). Be aware that repeated academic dishonesty offenses lead to suspension or expulsion from the University.

General Course Policies

Late submissions: Late-due homework are not accepted. In general you will be better off turning in what you have on time rather than seeking extra time to complete your work.

Communicating with the Instructors: We welcome questions related to the course. We will try to answer all questions by the end of the following day.
We will occasionally send email announcements to all students in the class. Recall that you are responsible for all official correspondence sent to your Hawkmail address (see General CLAS Policies on electronic Communication below).

Assigned Readings: Students are expected to study all the material assigned as required readings, even if that material is not explicitly discussed in class or in the homeworks.

Additional Readings and Discussions: Students are encouraged to go over any specifically suggested readings and consult any relevant materials beyond those provided on the course's web site. They are also encouraged to discuss the course topics with their classmates. It is a genuinely helpful learning activity having to formulate one's own thoughts about the material well enough to express them to others.

Attendance: Students are expected to attend all classes. Their knowledge and therefore their grade depends on it. They are responsible for all announcements and material covered during class even if they did not attend.

Extra Credit: No extra-credit assignments or tests will be given on an individual basis (although they maybe given to the whole class).

Make-up Exams: Make-up exams will be offered only if there is a serious, documented reason for not being able to take a scheduled exam, and if the request is made at least a week before the exam.

Regrading: Students thinking a graded assignment or test has been misgraded and deserves a regrading are invited to let the instructor know. The instructor welcomes and will give full consideration to all well motivated regrading requests.

College Policies

This course follows the general policies of the College of Liberal Arts and Sciences (see http://clas.uiowa.edu/faculty/teaching-policies-resources-syllabus-insert).