Theory of Computation (CSE322) Winter 2022

The course gives an overview over basic formal grammars and abstract machine models used in Computer Science. In particular, finite automata, pushdown automata, context-free grammers and Turing machines are studied with respect to their properties and limits. Based on Turing machines the concepts of decidability and recursive enumerability are introduced.

Pre-requisites

Course Objectives

  1. The student is able to describethe basic computational models FAs, PDAs, grammars and Turing machines.
  2. The student is able to formally model a given computational problem and prove its correctness
  3. The student can explain the concepts of undecidability and recursive enumerability and is able to give examples of respective problems.

Evaluation Policy

Evaluation will be based on in-class short online quizzes (to be taken during lectures and tutorials), group homeworks, closed-book online proctored midsem and endsem exams. We will follow a flexible policy to let students focus more on exams or homeworks, as per their choice. 

The following weightage scheme will be used to calculate your cumulative score.

Quizzes

Quizzes during lectures will happen via Google Forms from 11:30 to 11:45am and will be announced on Classroom at 11:30am. Submission window closes at 11:48am to allow network issue and server load.
Google servers often take some to accept Google Form submissions, and there are network related latency issues as well. If you try to submit at 11:46am, you may miss the deadline due to such issues. Do so at your own risk. Quizzes during tutorials will happen in the same manner but start at 4:30pm.

Course Personnel and Office Hours

All office hours will take place on the Meet Link given on Classroom.

Material