Current Catalog Description
Formal study of theoretical computational models: finite automata, pushdown automata, and Turing machines. Study of formal languages: regular, context-free, and decidable languages. Prerequisite: CSE 140.
Instructor: Arielle Carr (Spring 2021)
Textbook
Micheal Sipser, "Introduction to the Theory of Computation", 3rd Edition, ISBN 978-1133187790
RELATIONSHIP BETWEEN COURSE OUTCOMES AND STUDENT ENABLED CHARACTERISTICS
CSE 318 substantially supports the following student enabled characteristics
A. An ability to apply knowledge of computing and mathematics appropriate to the discipline
COURSE OUTCOMES
Students will:
- Understanding theoretical capabilities and limitations of algorithms as a function of the problems they can/cannot solve
- Formal understanding of the notion of nondeterministic computation
- Understanding the classes of machines, as per the Chomsky hierarchy, their capabilities and limitations
- Understanding the principles of formal languages
Major Topics Covered in the Course
- Regular Languages
- Regular expressions
- Finite automata
- Non regular expressions
- Context-free languages
- Context-free grammars
- Pushdown automata
- Non context-free languages
- Computational Theory
- Turing machines
- Decidable languages
- Turing-recognizable languages
- Turing-enumerability
- Definition of algorithm
- Non-decidable languages
- Halting problem
- Diagonalization methods
Assessment Plan for the Course
The students are giving weekly homework assignments on each of the topics covered in the course. There are two exams and a final exam.
How Data in the Course are Used to Assess Program Outcomes: (unless adequately covered already in the assessment discussion under Criterion 4
Each semester I include the above data from the assessment plan for the course in my self-assessment of the course. This report is reviewed, in turn, by the Curriculum Committee.