CMPS 346 - THEORY OF COMPUTATION

Theory of Computation - CMPS 346

Class Meeting: Monday 12:00 14:00

Problem Solving:
Thursday 08:00 – 10:00

Office Hours:  Monday 10:00 – 11:00


Course Objectives:

The course aims to provide students with the sense of interest for computability theory, automata theory and complexity theory. With this overall aim, the course strives to enable students to be able to determine what can be computed and what cannot be computed, its time and memory complexity, and on which type of computational model. The course also intends to teach students how to reduce one problem to another.

Course Outcomes:
     1. Student will be able to understand the different formal languages and different abstract machines recognizing
         them.

   2. Student will be able to learn how to design a deterministic and non-deterministic finite state machine.

   3. Student will be able to distinguish between regular language and non regular language and use the pumping 
       lemma to prove that a language is non regular.

   4. Student will be able to learn how to design a context free grammar and push down automata in order to
       recognize a certain context free language.

   5. Student will be able to distinguish between context free languages and non context free languages and use
       the pumping lemma to prove that a language is non context free.

   6. Student will be able to understand turing machines and how they work.

   7. Student will be able to understand decidable and undecidable language and use the mathematically proving to
       prove the undecidability of a language.

   8. Students will gain a preliminarily knowledge about the complexity theory.

Download course syllabus as PDF