Description
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).