ICS 441: Theory of Computation

Description: Grammars, sequential machines, equivalence, minimalization, analysis and synthesis, regular expressions, computability, unsolvability, Gödel’s theorem, Turing machines.

Objectives

• Students can write rigorous proofs.
• Students can compose analytical arguments.
• Students can conduct theoretical research on topics in fields of their interests.
• Students can write theoretical papers.

Course Learning Outcomes: See objectives.

Program Learning Outcomes

• a. Students can apply knowledge of computing and mathematics appropriate to the discipline
• b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution

Prerequisites: 311 or consent

Textbook(s): “Introduction to Automata Theory, Languages, and Computation,” John E. Hopcroft and Jeffrey D. Ullman

Grading: A few assignments (100%) in which students have to solve given theoretical problems and write technical reports on their solutions to the given problems, where the last assignment is the take-home final exam

Schedule

• Weeks 1-2: Basics of Formal Languages and Automata Theory (Review of ICS241)
• Weeks 3-5: Regular Sets, Regular Grammars and Finite Automata. Assignment 1
• Weeks 6-8: Context-Free Languages, Regular Grammars and Pushdown Automata, Assignment 2
• Weeks 9-10: Turing Machines
• Weeks 11-12: Computability
• Weeks 13-15: Computational Complexity Theory Assignment 3
• Week 16 Review
• Week 17: Final exam