Introduction to the theory of automata, formal languages, computability and computational complexity. Prerequisite: C.S. 3326. (1st)
Expectations:
E1. Students have a working knowledge of elementary set theory and mathematical structures such as relations, functions, and graphs and are able to apply this knowledge towards solving algorithmic problems. (CS 3166)
E2. Students are able to use inference and to develop direct and inductive proofs, proofs by construction, and proofs by contradiction. (CS 3166)
E3. Students can perform in depth algorithm analysis, including average case efficiencies and Ω and Θ asymptotic notations. (CS 3326)
E4. Students can identify and understand why some problems cannot be solved efficiently (NP problems). (CS 3326)
Course Outcomes:
R1. Students are able to develop inductive proofs, proofs by construction and proofs by contradiction and can recognize errors in such proofs. (CS 14)
R2. Students recognize regular languages, know situations where regular languages are useful, are able to define regular languages using finite automaton (deterministic and non deterministic), grammars and regular expressions, and can translate between these definitions. (CS 14)
R3. Students can show that a language is not regular using the Pumping Lemma. (CS 14)
R4. Students recognize context free languages, know situations where context free languages are useful, are able to define context free languages using push down automaton and grammars, and can translate between these definitions. (CS 14)
R5. Students can show that a language is not context free using the Pumping Lemma for Context-Free Languages. (CS 14)
R6. Students understand the concept of a Turing Machine, and know several variations on Turing Machines that are all equivalent. (CS 14)
R7. Students know that Turing Machines can be used to define computability (Turing Thesis) and that all other sufficiently complex models of computation are equivalent to Turing Machines (Church-Turing Thesis). (CS 14)
R8. Students know examples of problems that are un decidable by any Turing Machine. (CS 14)
R9. Students know examples of NP-complete problems and that if a polynomial time algorithm is found for any NP-complete problem then P=NP. (CS 14)
|
