CS41001: Theory Of Computation
| CS41001 | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Theory Of Computation | ||||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||||||||
Syllabus[edit | edit source]
Syllabus mentioned in ERP[edit | edit source]
Computability theory: Review of Turing machines, some other computing models and formalisms, their equivalence with Turing machines, undecidability, Post correspondence problem, Turing computability, primitive recursive functions, Cantor and Goedel numbering, Ackermann function, mu-recursive functions, recursiveness of Ackermann and Turing computable functions, lambda calculus, term rewriting, oracle machines and the arithmetic hierarchy.Complexity theory: Time- and space-bounded Turing machines, reduction and complete problems, oracle machines and the polynomial hierarchy, randomized computation, parallel computation.Logic: First-order predicate calculus- syntax, semantics, validity and satisfiability, decision problems in logic, quantified Boolean formulas and their relation with the polynomial hierarchy.References1.Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.2.Fred C. Hennie. Introduction to Computability. Addison-Wesley.3.Bernard M. Moret, The Theory of Computation, Pearson Education Asia.4.Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman.5.Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.6.John Martin, Introduction to Languages and The Theory of Computation, Tata McGraw Hill.7.John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
Concepts taught in class[edit | edit source]
Student Opinion[edit | edit source]
How to Crack the Paper[edit | edit source]
Classroom resources[edit | edit source]
Additional Resources[edit | edit source]
Time Table[edit | edit source]
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | NR421 | |||||||||
| Tuesday | NR421 | NR421 | ||||||||
| Wednesday | ||||||||||
| Thursday | NR421 | |||||||||
| Friday |