This course introduces fundamental concepts in the theory of computation. Students will be introduced to formal languages, automata, computability and computational complexity. These include finite automatons, Turing machines, grammars, decidable problems, reductive procedures and different kinds of computational problems. The course aims to explore these theoretical concepts to apply on practical issues of interest to software engineering, data science, and AI, for instance, natural language processing, algorithmic development and evaluation of computational efficiency. By the end of this course, students will be able to assess the performance bounds of computing models and their applicability towards modern computing problems.
Prerequisite Courses