Catalog Description

This course serves as an introduction to the basic theory of Computer Science and formal methods of computation. Topics include automata theory, formal languages and grammars, Turing machines, computability and computational complexity.
Prerequisite: Computer Science 250. Three hours.

Course Objectives

Upon successful completion of this course students should be able to:

• Understand basic properties of formal languages and formal grammars
• Understand basic properties of deterministic and nondeterministic finite automata
• Understand the relation between types of languages and types of finite automata
• Understand basic properties of Turing machines and computing with Turing machines
• Understand the concepts of tractability and decidability, the concepts of NP-completeness and NP-hard problems
• Understand the challenges for Theoretical Computer Science and its contribution to other sciences