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
Syllabus mentioned in ERP
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
Student Opinion
How to Crack the Paper
Classroom resources
Additional Resources
Time Table
| 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 |