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.