COT 5420: Theory of Computation I -- Fall 01
Course Homepage
Office: ECS 389; Phone: (305) 348-3748;
Office Hours: Tuesdays 10:30-11:30 AM; Thursdays 4:30-5:30 PM
e-mail: giri@cs.fiu.edu
ANNOUNCEMENTS
November 26, 2001.
For a schedule of project presentations:
HANDOUTS AND HOMEWORK ASSIGNMENTS
One must learn by doing the thing; for
though you think you know it, you have no certainty until you try.
Sophocles
TEXT:
"Introduction to the Theory of Computation", by Sipser
[ISBN 0-534-94728-X]
EVALUATION:
- Written homeworks (25%)
- MidTerm Exam (25%) & Final Exam (25%)
- Class participation (5%)
- Semester Project (20%)
EXPECTED PREREQUISITE KNOWLEDGE
- Course on Discrete Mathematics
- Material from Sipser's book: Chapter 0
SYLLABUS
- Regular Languages and Finite Automata
- Regular Expressions and Non-deterministic Automata
- Pumping Lemma and Properties of Regular Languages
- Context-Free Languages and Grammars
- Push-down Automata
- Pumping Lemma for CFLs and Properties of CFLs
- Turing Machines and Variants
- Church-Turing Thesis
- Decidability and Undecidability
- Halting Problem
- Reducibility
- Complexity Hierarchy and Intractability
- Parallel Models of Computation
- Sampling of Advanced Topics
Other Reference Books
- "Introduction to Automata Theory,
Languages, and Computation", by Hopcroft, Motwani, and Ullman
[ISBN 0-201-44124-1]
- "Elements of the Theory
of Computation", by Lewis and Papadimitriou (Second Edition)
[ISBN 0-13-262478-8]
Old Announcements
Thursday, September 13, 2001
- AS ANNOUNCED EARLIER, THERE WILL BE NO CLASS ON THURSDAY, SEPT. 13.
- HOMEWORK #2 IS NOT AVAILABLE YET SINCE WE HAVE NOT COVERED ENOUGH
MATERIAL. I RECEOMMEND THAT YOU TRY PROBLEM 1.4 TO IMPROVE YOUR
UNDERSTANDING -- THIS IS NOT A HOMEWORK AND NEED NOT BE TURNED IN.
September 20, 2001.
- Homework #2 is now available. See below. It is due on October 2.
- Some ideas for projects are now available if you Click
here. NOTE THAT THIS PAGE IS STILL BEING UPDATED AND MORE PROJECTS
SHOULD BE AVAILABLE SOON!
