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 language, and Turing-acceptable languages), Turing-complete systems, and algorithmically unsolvable problems.

CSE581