CSE 30151

Source: Amitabh Chaudhary

Course Outcomes

At the end of the course, students will:

1.   Demonstrate understanding of the operation of finite automata, and their equivalence to regular languages and expressions.

Assessed in: Homework 1: 3-5; Homework 2: 1-6; Homework 3: 1-4.  Exam 1: 1-4. Final: 1-2, 5.

2.   Demonstrate understanding of the operation of pushdown automata, and their  equivalence to context-free languages and grammars.

Assessed in: Homework 4: 1-5; Homework 5: 1-5.  Exam 1: 5; Exam 2: 1.  Final: 1, 3-4, 5.

3.   Show ability to design simple Turing machines to decide languages, and understand that computational ability of Turing machines is maximal among computational models. 

Assessed in: Homework 5: 6-7; Homework 6: 1-3.  Exam 2: 2-3.
4.   Show decidability of certain languages, and prove undecidability of other languages using reduction.

Assessed in: Homework 7: 1-4; Homework 8: 1-4.  Exam 2: 4-5.  Final: 3, 6.

5.   Demonstrate ability to construct proofs showing NP-completeness of languages using reduction.

Assessed in: Homework 9: 1-4.  Final: 5, 7-9.