Automata and languages; finite automata; regular expression and languages; context-free grammars and languages; pushdown automata; computability theory; introduction to turing machines: turing thesis and variants of turing machines; decidability: decidable languages, the halting problem; reducibility: undecidable problems; complexity theory: time complexity and space complexity; intractability