ECE324 Introduction to the Theory of Computation

INTRODUCTION: Automata, computability and complexity, mathematical concepts and terminology
REGULAR LANGUAGES: Finite Automata, Non-determinism, Regular Expressions, Non-regular Languages
CONTEXT-FREE LANGUAGES: Context-free Grammars, Pushdown Automata, Non Context-free Languages
CHURCH-TURING THESEIS: Turing Machines, Variations of Turing Machines, the definition of Algorithm
DECIDABLITY: Decidable Languages, the Halting Problem
TIME COMPLEXITY: Measuring Complexity, the Class P, the Class NP
SPACE COMPLEXITY: the Savitch theorem, the Class PSPACE

The learning objectives of this course are to:

• introduce students to the mathematical foundations of computation including automata theory, the theory of formal languages and grammars, the notions of algorithm, decidability, complexity, and computability.
  enhance/develop students’ ability to understand and conduct mathematical proofs for computation and algorithms.
• On completion of the course, a student should be able:
  to categorize abstract machines and to construct machines appropriate to specific problems
• to display an understanding of the merits and limitations of the analytical techniques of software development
• to recognize the significance of complexity classes and analysis and to deduce the complexity of certain types of algorithm
• to demonstrate a deeper and broader understanding of classes of complexity
• to prove the basic results of the Theory of Computation