Computing Theory

Learning Outcomes

Upon successful completion of this course, students are expected to be able to: Describe computing model and its corresponding language class in the Chomsky Hierarchy, Identify computational problems and define the computing requirements appropriate to its solution, Apply knowledge of computing theory in problem solving, Design a system appropriate to given computing model.

Topics

This course provides students with knowledge of computing theory concepts and to enable students’ understanding about computational capabilities of a computer, foundational issues in computer science, and develops an understanding of the capabilities and limitations of computer software based on an understanding of theoretical issues.  A number of concrete problems will be addressed in order to develop this understanding at both a conceptual and concrete level. In addressing the problems students will also gain skills in writing grammars, automata manipulations, regular expressions, proof techniques and reasoning about computational capabilities.

Prerequisite: MS107 – Discrete Mathematics