Computer Science is the study of computers and programs, the collections of instructions that direct the activity of computers. The computers are made of simple elements but they perform very often a very complex task. The great disparity between the simplicity of the computers and the complexity of computational tasks offers intellectual challenges of the highest order. Theoretical computer science develops methods and models of analysis to meet those challenges.
This course provides an introduction to general computational models (logic circuits, upper bond on the size and depth of the circuits for important problems), automata (finite-state, random-access, Turing machines), formal languages and computational complexity (time and space bounded complexity classes, space-time tradeoffs).
Prerequisite: COMP 213, COMP 220, COMP 223