3 Semester Credit Hours

Course Description

This course is an introduction to the core logical and mathematical foundations of Computer Science. Different theoretical models of computation (automata) are introduced, along with their relationships with realistic practical computation.

Specifically, this course introduces Finite Automata and their relationship with pattern matching and filters, Pushdown Automata and their relationship with grammars and parsing, and Turing Machines and their relationship with algorithms in general. Turing machines are then used to introduce the limitations of computing, specifically undecidability and NP-completeness of problems. The latter is shown of use in practical algorithm design situations.

Prerequisites

• One year of college-level calculus
• A lower division course in programming and elementary data structures
• An undergraduate course in Discrete Mathematics covering sets, sequences, functions and relations, undirected and directed graphs, asymptotic notation for the running time of algorithms, (concept of proof, and techniques for constructing proofs (by contradiction, by induction).
• General prerequisite: Students must have the knowledge resulting from appropriate prerequisite coursework in the curriculum for a BS degree in Computer Science from a regionally-accrediated institution in the United States or the equivalent from a foreign institution; performance level in this coursework should be equivalent to a cumulative undergraduate GPA of 2.9 or better on 4.0 scale.
   

Course Objectives

Upon successful completion of the class, a student should be able to:

• Describe the role of finite automata and regular expressions in computer science
• Transform non-deterministic finite automata, deterministic finite automata and regular expressions into one another
• Invent finite automata, Turing machines, or regular expressions to solve specific simple recognition problems
• Use the pumping lemma for regular languages to show that some simple languages are not regular
• Describe the role of contest-free grammars and pushdown automata in computer science
• Invent context-free grammars to descibe simple context-free languages
• Describe in English the language defined by a simple context-free grammar
• Invent simple Pushdown Automata to solve simple context-free recognsition problems
• Describe the role of Turing machines in computer science, and the meaning of decidability, undecidability and Turing recognizability
• Invent simple reductions to show that given problems are undecidable or not Turing recognizable
• Describe the role of the classes P and NP in computer science, and show that simple problems are in P or are in NP
• Describe what it means for a problem to be NP-complete, both theoretically and in practice
• Invent simple reductions to show that given problems are NP-complete

Course Topics