Theory of Computation (COM-604)
Program: B.Tech Computer Science Engineering
Category: Professional Core Course
Semester: 6
Credits: 4
L-T-P: 3- 1- 0
Description
Theory of Computation (TOC) is a branch of computer science and mathematics that deals with how problems can be solved using algorithms and how efficiently they can be solved. It provides a formal framework to understand the nature of computation, computational problems, and the capabilities and limitations of various computational models.
Instructor

Dr. Rajneet Kaur Bijral*

Assistant Professor
Department Of Computer Science & Engineering
Course Outcomes
  • Understand the key notions of computation, such as algorithm, computability, decidability, reducibility, and complexity, through problem solving.
  • Understand the models of computation, including formal languages, grammars and automata, and their connections.
  • Articulate and explain the Church-Turing thesis and its significance.
  • Analyze and design finite automata, pushdown automata, Turing machines, formal languages, and grammars.
  • Solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation.
Resources
Course Handout Lesson Plan Syllabus
Evaluation Scheme
Quiz 10
Quiz_1 10
Assignment 20
Attendance 10
Total Internal 50
Total External 100
Overall Total 150