The course consists of two parts. The first part covers discrete
mathematics -- a division of mathematics that is extensively used in
computer science. The topics covered include: logic (propositional logic and
predicate logic), proof techniques, sequences (mathematical induction and
recursion), and functions. The second part covers the theory of
computation -- a division of theoretical computer science that deals with
what can be computed and what cannot be computed on a computer. The topics
covered include: computational models (FA, PDA, and Turing machines),
grammars accepted by different computational models (regular grammars,
context-free grammars, and unrestricted grammars), languages accepted by
different computational models (regular languages, context-free languages,
and Turing-acceptable languages), Turing-complete systems, and
algorithmically unsolvable problems.
This course cannot be used to satisfy lecture course requirement for MS
students; it also cannot be used to satisfy qualifier requirements or credit
requirements for PhD students.
