COT 6421 -- Theory of Computation II

Spring 2005

Mondays and Wednesdays, 12:30-1:45, ECS 145

Course Prerequisites



Introduction to the Theory of Computation by Michael Sipser (PWS Publishing, 1997). The author maintains a web site with errata at

Two other books that I especially like are

Course Description

This course continues COT 5420 in exploring mathematical models of computation in an effort to understand what problems can and cannot be solved using computers. We will be begin with some advanced topics in computability theory, and then we will refine our investigation by considering the resources (such as time or space) required to solve a problem. That is, we will ask not just whether a problem can be solved at all by a computer, but whether it can be solved using a reasonable amount of resources.

The course will be structured roughly as follows:

  1. Review of Turing Machines (Chapters 3 and 4).
  2. Computability Theory (Chapters 5 and 6)
    Recursive and recursively-enumerable languages; undecidability; mapping reducibility. We will also discuss applications to logic, including Gödel's Incompleteness Theorem, and Presburger arithmetic.
  3. Computational Complexity (Chapters 7, 8, and 9)
    Asymptotic complexity; time and space complexity; the classes P, NP, and PSPACE; reductions and completeness.
  4. Selected Topics, depending on time and interest.
    Possible topics include the minimization of deterministic and nondeterministic finite automata, and theoretical topics from computer security.

As in COT 5420, problem solving is the heart of this course. What you get out of this course will mostly depend on how much effort you put into solving and writing up the homework problems. I will be assigning homework every couple of weeks; also, I encourage you to think about all the exercises and problems in the textbook, whether assigned or not.

Homework Groups

Homeworks may be done individually or with a partner. If you choose to work with a partner, you should still first try to solve all the homework problems on your own, and then you should meet with your partner to discuss the solutions that you have found. You and your partner can then prepare a single write-up of the homework to submit for grading. However you choose to submit your homeworks, it is valuable to discuss the problems with other students: often you will be able to catch one another's errors, and you will often find that your discussions lead you to cleaner and more elegant solutions.


I plan to give a final exam, or possibly a final project or presentation. Grades will be weighted as follows:
Homework 60%
Final 35%
Class Participation 5%
The final exam is scheduled for Monday, April 25, from 12:30 to 3:15.

Academic Integrity

I expect you to maintain a high level of academic integrity in this course. Please read FIU's Code of Academic Integrity at For this course, the basic principle to follow is this: the work that you submit should be the result of your group's own effort. You are allowed to consult other books in solving homework problems, or to discuss the problems with other students, but you should cite any such sources that you use. And you must write up your solutions on your own--merely copying answers from the Web, books, or other students is definitely not acceptable.

Finally, I encourage you to make a serious effort to solve the problems on your own before you consult other books or other students. Struggling with different approaches to difficult problems will give you many insights that you won't get by simply reading a beautifully polished answer in a book. (Of course, after you've solved a problem on your own, it's then nice to look at other people's solutions to see how they compare with yours.)


I will grant incompletes only in extreme circumstances, such as medical emergencies.


I expect you to attend class regularly and promptly and to participate in discussions. Please don't be shy about asking questions--if something is unclear to you, it is probably unclear to others as well.

Back to COT 6421 home page.