CS 575 - Models of Computation
Credits: 3
Course Description
The formal study of computation, including computability and computation with limited resources. Church's thesis and models of computation. Formal languages and machines as recognizers of languages. The Chomsky Hierarchy of language types. Topics may include Turing machines or other basic models of computation; decidability and undecidability; basic complexity theory; finite automata and regular languages; pushdown automata and context-free languages. The course will cover primarily theory, including assignments that utilize concepts covered in lectures.
Prereqs: CS 375 or consent of instructor.
Needed Skills
Students should be familiar with logic, discrete mathematics, and comfortable using proof techniques such as induction.
Learning Outcomes
Successful students will learn:
1. Basic models of computation, their properties and relationships among them.
2. Notions of computability; proofs of insolvability and intractability.
3. Foundations for complexity analysis of algorithms.
4. Relationships between machine models and languages.
5. Applications of these topics to program design and analysis.
Measures
These five specific outcomes will be evaluated on the basis of student homeworks and exams that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the five outcomes performed at the end of the semester.
CAC Categories
|
Topic |
Core |
Advanced |
|
Math
Fundamentals |
3 |
9 |
|
Data
Structures |
6 |
6 |
|
Algorithms
& Software Design |
0 |
9 |
|
Computer
Organization and Architecture |
0 |
0 |
|
Concepts
of Programming Languages |
5 |
6 |
|
Social
and ethical issues |
1 |
0 |
|
Total |
15 |
30 |
Math Fundamentals (12):
Core (3): Sets, functions, relations, graphs (3)
Advanced (9): Turing machines (4); decidability and undecidability (5)
Data Structures (12):
Core (6): finite automata (3); pushdown automata (3)
Advanced (6): equivalence of automata and language constructs (6)
Algorithms and Software (9): Advanced: Complexity theory and intractability (9)
Computer Organization and Architecture: none
Concepts of Programming Languages (11):
Core (5): Regular languages (3); Context-free grammars (3)
Advanced (6): Closure properties of regular and context-free languages (2); nonregular languages (2); noncontext free languages (2)
Social and Ethical Issues (1): Discussion of professional and academic integrity
Oral Communication (presentations)
none
Written Communication
7--8 homeworks, ~3 pages/assignment
Coverage
Theoretical Content: 60%
Almost all of it
Problem Analysis: 20%
Recognizing the complexity (either in the Chomsky hierarchy or in terms of limited resources, e.g. time, space, nondeterminism) of given languages
Solution Design: 20%
Finding automata, grammars or expressions, or algorithms to demonstrate the specified or conjectured
Student Evaluation and Feedback
Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems and to point to correct or better solutions. Problems that turn out to be especially difficult are discussed in class during lectures or during recitations.
Course Evaluation Questions
The course has helped me to:>
37. Recognize the relationship between machine models and language generation.
38. Analyze languages in terms of machine complexity.
39. Analyze algorithms in terms of time and space complexity.
40. Design better algorithms.
41. Recognize problems that are intractable or uncomputable.
42. Understand the relevance of Theory to the CS curriculum.
Possible Textbook
Introduction to Languages and the Theory of Computation
J. Martin
McGraw Hill, 1991.
Introduction to the Theory of Computation
Michael Sipser
PWS Publishing Company