Subsections
[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).
