• Theory of Computation
• CS205 at IITG by R. Inkulu

---

• This is a core course for second-year undergrads. It introduces foundational topics from automata, computability, and complexity theories. The specific topics covered include the following -
  
  Automata: finite automata, pushdown automata, Turing machines; regular, context-free, decidable, Turing-recognizable languages; Chomsky hierarchy.
  
  Computability: Church-Turing thesis; decidability, undecidability; many-one reducibility, Rice's theorems, reductions via computation histories, Post's correspondance problem.
  
  Complexity: P, NP, NP-hard, Cook-Levin theorem, coNP, coNP-hard; PSPACE, Savitch's theorem, PSPACE-hard; polynomial-time reductions; L, NL, NL-hard, coNL.



• Texts:
• Introduction to Automata Theory, Languages, and Computation by J. E. Hopcroft and J. D. Ullman, First Edition.
• Introduction to the Theory of Computation by M. Sipser, Third Edition.



---



• Prereq: Introduction to Computing,   Discrete Mathematics,   Introduction to Algorithms.


• Lectures are held in ? in Slot ?: TBA.
• The academic calendar is here.


• Teaching Assistants: TBA
  
• The set of guidelines for TAs is here.


• The grading is relative, and it is based on the total marks obtained in the following:
  
  

  exam1	15 points	10 am to 11:30 am on ? (?) in ?
  mid-sem	18	2 hours; refer to institute time table
  exam3	20	10 am to 12 pm on ? (?) in ?
  end-sem	25	3 hours; refer to institute time table
  surprise (4 to 6)	3*(≥4)	15 minutes each; not scheduled beforehand
  homework	0	one/two problems posted after every lecture
  class participation	4	-

---