CSE 318/CSE 409 (Introduction to the Theory of Computation)
Spring 2018
Texts
Required:
Michael Sipser Introduction to the Theory of Computation
(Second Edition)
Description
The course studies formal properties of computation. The course addresses the following questions:
- What is computation? (here is a short essay to this fundamental question)
- What kinds of well-defined problems (i.e., expressed in terms of inputs and outputs) can be solved by computation?
- What kinds of well-defined problems (i.e., expressed in terms of inputs and outputs) cannot be solved by computation?
Here is a cool
video that presents Turing machines, one of the central topics of the course.
Students will gain a deep understanding of the capabilities and limitations of computation. As a result, they will have a unique insight to questions grappling society today related to the AI Question and technological singularity, which will be addressed in the course.
topics covered
The notion of computation including nondeterministic computation
Finite State Machines: finite automata and stack-based automata
Turing machines
Decidable Languages
The Church-Turing Thesis and the notion of algorithm
Course work
There will be homeworks and two tests.
Students choose between taking a final exam or working on a programming project aimed at improving their understanding of topics covered by the course.
Grading
Tests 50% (Test # 1: 25%, Test # 2: 25%)
Final Exam or Final Project 30%
Homework: 20%
Last update: Oct. 10 00:17:57 EDT
2017