A rigorous introduction to the core concepts of theoretical computer science. Through this course, students will learn to analyze and classify problems according to complexity and computability. Topics covered include fundamental concepts such as string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: Proof by construction, proof by contradiction, pigeonhole principle; Deterministic and non-deterministic Finite state automata; Regular and non-regular languages, regular expressions; Equivalence of NFA and DFA; Pumping Lemma; Context free grammar (CFG) and Push down automata (PDA); Chomsky Normal form; Parsing; Turing machine, Universal Turing machine and the Halting problem; Goedel numbering; Computability (P vs NP).

• CSC 201 : Discrete Mathematics

• Learn core ideas in computer science theory, including how to define and investigate a formalized model of computation, and what it means to reduce one problem to another.
• Deepen their ability to think clearly, originally and devise correct proofs.

1. Introduction to the Theory of Computation by M. Sipser
2. Elements of the Theory of Computation by H. Lewis, C. Papadimitriou
3. Introduction to Automata Theory, Languages & Computation by J. Hopcroft, R. Motwani, J. Ullman