ICS 441: Theory of Computation
Description: Grammars, sequential machines, equivalence, minimalization, analysis and synthesis, regular expressions, computability, unsolvability, Gödel’s theorem, Turing machines.
- 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
- 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