### 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.