CSCE 551: Theory of Computation
Catalog Description:
551—Theory of
Computation.
[=MATH 562] (3) (Prereq: CSCE 350 or MATH 526 or 544 or 574) Basic Theoretical
principles of computing as modeled by formal languages and automata;
computability and computational complexity.
Major credit may not be received for both CSCE 355 and CSCE 551.
Prerequisite(s) By Topic:
Analysis of algorithms
Programming in a high-level language
Textbook(s) and Other
Required Material:
M. Sipser, Introduction
to the Theory of Computation, PWS, 1997.
Computing Platform: NA
Course Objectives: {Assessment Methods Shown in
Braces}
1. Describe finite
state automata. {tests}
2. Measure the
computational complexity of an algorithm. {homework, tests}
3. Describe
characteristics of a Turing machine {tests}
4. Demonstrate
computability or non-computability using a Turing machine. {homework, tests}
Topics Covered:
1. Algebra review
2. Regular languages: automata,
nondeterminism, regular and nonregular languages.
3. Context-free languages: context-free
grammars, pushdown automata, non-context-free languages.
4. The Church-Turing thesis: Turing
machines and their variants, algorithms on Turing machines.
5. Decidability: decidable languages, the
halting problem.
Laboratory Projects
none
Syllabus
Flexibility: High. The instructor
chooses the textbook and syllabus.
Relationship of Course to
Program Outcomes:
The contribution of each course objective to meeting
the program outcomes is indicated with the scale:
3 = major contributor, 2 = moderate contributor, 1 = minor contributor. Blank if not related.
|
|
Program Outcomes |
||||||||||
|
1.
Logic & Math |
2.
Computing Fundamentals |
3.
Apply Computing Principles |
4.
Work on teams |
5.
Communicate Effectively |
6.
Liberal arts & Soc. Sciences |
7.
Basic Science and Lab Procedures |
8.
Learn New Tools & Processes |
9.
Employed upon Graduation |
10.
Application Area |
11.
Electronics and Digital Sys Design |
|
|
1. Describe finite state automata. |
|
3 |
3 |
|
|
|
|
|
|
|
1 |
|
2. Measure the computational complexity of an algorithm |
|
3 |
3 |
|
|
|
|
|
|
|
1 |
|
3. Describe characteristics of a Turing machine |
|
3 |
3 |
|
|
|
|
|
|
|
1 |
|
4. Demonstrate computability or non-computability using a Turing
machine |
|
3 |
3 |
|
|
|
|
|
1 |
|
1 |
Estimated CSAB Category
Content:
Algorithms: 2
hrs
Data Structures: 0
Software Design: 0
Concepts of
Programming Languages 0.5
hr
Organization and
Architecture 0.5
hr
Oral and Written
Communication: none
Social and
Ethical Issues: none
Theoretical
Content:
Finite State Automata, Turing machines,
computational complexity, computability
Analysis and
Design:
Analysis of algorithms, computational
complexity.
Class/Laboratory Schedule:
Lecture: 3
periods of 50 minutes or 2 periods of 75 minutes per week
Difference
between Undergraduate and Graduate Work:
Students enrolled for graduate credit will have to do more difficult assignments and will be graded using more rigorous criteria in order to justify the receipt of graduate credit for this course.
Course
Coordinator: Stephen Fenner
Modification and
Approval History:
Initial description, April 1999
Revised, June 2001
Modified July 2002 to include statement
on graduate work