**[Cr:2, Lc:2, Tt:0, Lb:0]**

- Mathematical notions: Sets, Functions, Sequences, Graphs, Boolean Logic, Proofs and types of proofs.
- Languages: Context free grammar, Examples, Ambiguity, Chomsky normal forms.
- Computability: Origin of Computability Theory, GĂ¶del and the discovery of incomputability, Church-Turing thesis, Turing machines and their variants, Examples, Decidability, Reducibility, Recursion Theorem, Self referencing, Russell's Paradox.
- Time Complexity: Big-O and small-o notation, Analysing algorithms, P and NP problems, Vertex cover problem, Hamiltonian path problem, Subset sum problem.
- Space Complexity: Savitch's problem, The class PSPACE, Classes L and NL.
- Computing time and space complexity for various algorithms.

- Michael Sipser, Introduction to the Theory of computation, Course Technology Publishers (1996).
- S. Barry Cooper, Computability Theory, CRC Press (2003).