## COT 6421 -- Theory of Computation II## Spring 2005## 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* - Web: http://www.cs.fiu.edu/~smithg/
- 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.

Two other books that I especially like are

- Automata and Computability by Dexter Kozen (Springer-Verlag, 1997).
- 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
of resources.

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 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.

The final exam is scheduled for Monday, April 25, from 12:30 to 3:15.

Homework 60% Final 35% Class Participation 5%

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.)

Back to COT 6421 home page.