Deterministic and nondeterministic finite automata (DFAs and NFAs), regular expressions, context-free grammars, relationship of push-down automata and context-free grammars, definintion of the classes P and NP, NP-completeness (Cook's Theorem), standard NP-complete problems, reduction techniques, Turing machines, the halting problem.
3 lecture hours
Credit: 0.50
Prerequisite: CP312, MA238
| Section | Days | Times | Room | Instructor |
|---|---|---|---|---|
| B | MWF | 12:30 PM - 01:20 PM | Dr. Evgueni Zima |