• 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, NPSPACE, Savitch's theorem, PSPACE-hard; polynomial-time reductions; hierarchy theorems; L, NL, coNL, Immerman-Szelepcsényi theorem.



• 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.



---



• Prereqs: CS101, CS201, CS203; ease in understanding and building formal proofs.


• 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	14 points	10 am to 11:30 am on 25th Jan (Sat) in ?
  mid-sem	18	2 hours; refer to institute time table
  exam3	15	10 am to 11:30 am on 29th March (Sat) 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	-

---