Instructor: M. Mavronicolas
  Room: FST 01-106
  Telephone: 22-892702
  E-mail: mavronic@ucy.ac.cy
           
       
Back to Main Page Class Pages Class Notes Books Related Links
 

SYLLABUS

 

Formal methods of computation based on machines, grammars and languages: finite automata vs. regular languages; pushdown automata vs. context-free grammars; Turing machines vs. unrestricted grammars. Models of computation equivalent to Turing machines and Church's Thesis. Computability and Uncomputability. Introduction to Theory of Computational Complexity with emphasis on the Theory of NP-completeness.

 

Prerequisites:

CS 111: Discrete Structures in Computer Science and Computation

MAS 004: Introductory Mathematics I