COT 5420 -- Theory of Computation I Fall 2004

Geoffrey Smith

• ECS 320
• 305 348-6037
• smithg @ cs.fiu.edu
• Office Hours: Mondays and Wednesdays, 3:30 -- 4:45
  I'll usually be happy to meet at other times. Send e-mail, call, or drop by.

Introduction to the Theory of Computation by Michael Sipser.

Course Syllabus

Final Exam

Homework Assignments

• Homework 0. Not to hand in.
• Homework 1. Due Monday, September 27.
• Homework 1 Bonus Problem Solution.
• Homework 2. Due Monday, October 18.
• Homework 2 Bonus Problem Solution.
• Homework 3. Due Monday, November 8.
• Homework 4. Due Monday, November 22.
• Homework 4 Bonus Problem Solution.
• Homework 5. Due Wednesday, December 8.
• Homework 5 solutions.

Resources

• Here is a link to Alan Turing's 1936 paper, On computable numbers, with an application to the Entscheidungsproblem.
• Here's a Java version of the proof that the Halting problem is undecidable: Halt.java.
• Some resources for Michael Sipser's Fall 2002 Theory of Computation course. (Quite different from our course.)