CS 385

From CS Wiki
Jump to: navigation, search


Theory of Computation

Catalog Description: Mathematical models of computation, including finite automata and Turing machines. Same as Math 385.

Type: Required for all CS majors.

Total Credits: 3

Contact Hours: 3 lecture hours per week

Course Coordinator: Terry Soule

URL: http://www2.cs.uidaho.edu/~cs385/f12/ (Fall 2012)

http://www.webpages.uidaho.edu/~markn/385/ (Fall 2013)

Prereq: Have passed all required CS 2XX level course with C or better.

Textbook: P. Linz, An Introduction to Formal Languages and Automata, 5th Edition, Peter Linz, 2006 or similar text.

Textbook URL: http://www.jblearning.com/catalog/9781449615529/

Prerequisites by Topic:

  • Trees, graphs, worst case analysis, recursion (CS 121)
  • Induction, counting (Math 175)
  • Series, set theory (Math 176)

Major Topics Covered

  1. Language Theory: Recursive definitions ( 2 hours)
  2. Language Theory: Regular expressions and languages ( 2 hours)
  3. Language Theory: Finite automata ( 2 hours)
  4. Language Theory: Kleene's theorem ( 1 hour)
  5. Language Theory: Myhill-Nerode theorem ( 1 hour)
  6. Language Theory: Nondeterminism ( 4 hours)
  7. Language Theory: Finite automata with output ( 2 hours)
  8. Language Theory: Nonregular languages ( 4 hours)
  9. Language Theory: Pushdown automata ( 2 hours)
  10. Language Theory: Contex-free grammars ( 2 hours)
  11. Language Theory: Chomsky normal form ( 2 hours)
  12. Language Theory: Non-context-free grammars and languages ( 3 hours)
  13. Language Theory: Parsing algorithms ( 1 hour)
  14. Computability Theory: Turing machines ( 3 hours)
  15. Computability Theory: The Halting problem ( 1 hour)
  16. Computability Theory: Rice's theorem ( 1 hour)
  17. Computability Theory: Complexity Classes ( 2 hours)
  18. Computability Theory: Completeness ( 1 hour)

Course Outcomes

  1. Use mathematical techniques and principles to define problems in terms of languages/sets. (a)
  2. Use mathematical techniques and principals to determine which language family (including regular, context free, and recursive) a particular language is in. (a)
  3. Use mathematical techniques and principals to reason about the theoretical difficulty of computational problems. (a)
  4. Write and understand recursive definitions of sets. (a)
  5. Trace the behavior of simple DFAs, NFAs, PDA, and Turing Machines. (a)
  6. Write definitions of regular languages using regular expressions, DFAs, NFAs, and regular grammars. (a)
  7. Apply the Pumping lemma to show that a language is not regular. (a)
  8. Know the basic closure properties of regular languages, context free languages, and recursive languages. (a)
  9. Write definitions of context-free languages using context-free grammars and PDA. (a)
  10. Apply the Pumping lemma to show that a language is not context-free. (a)
  11. Know the relative computational power of different models of Turing Machines (multi-tape, semi-infinite tape, etc.) (a)
  12. Know the definition of a recursively enumerable language. (a)
  13. Know the definition of a recursive language. (a)
  14. Know what the Halting problem is. (a)
  15. Be able to reduce one undecidable problem to another. (a)
  16. Ability to do proof by induction (a)
  17. Write clear, understandable mathematical proofs. (f)