COT 6421 -- Theory of Computation II
Mondays and Wednesdays, 12:30-1:45, ECS 145
- COT 5420 (Theory of Computation I)
- Geoffrey Smith
- Office: ECS 320
- Telephone: 305 348-6037
- E-mail: smithg @ cs.fiu.edu
- Office Hours: Mondays and Wednesdays, 2:00 -- 3:15
I'll usually be happy to meet at other times.
Send email, call, or drop by.
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
- Automata and Computability by Dexter Kozen
- Introduction to Automata Theory, Languages, and Computation
by John Hopcroft and Jeffrey Ullman (Addison-Wesley, 1979).
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
The course will be structured roughly as follows:
- Review of Turing Machines (Chapters 3 and 4).
- 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.
- Computational Complexity (Chapters 7, 8, and 9)
Asymptotic complexity; time and space complexity;
the classes P, NP, and PSPACE; reductions and completeness.
- Selected Topics, depending on time and interest.
Possible topics include the minimization of deterministic and
nondeterministic finite automata, and theoretical topics from
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.
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:
The final exam is scheduled for Monday, April 25, from 12:30 to 3:15.
|Class Participation|| 5%|
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.
COT 6421 home page.