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
- Discrete Mathematics OR Discrete Structures
Course Objectives
- The student is able to describethe basic computational models FAs, PDAs, grammars and Turing machines.
- The student is able to formally model a given computational problem and prove its correctness
- 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.
- QUIZ = sum of 6 highest quiz scores (each quiz carries 3.00%) = 18%
- HWS (starred homework questions) = sum of top 4 questions (each quiz carries 1.5%) = 6%
- 2 HWSQ from HW1 (Ch 1: finite automata)
- 1 HWSQ from HW2 (Ch 2: pushdown automata)
- 2 HWSQ from HW4 (Ch 4: Turing machine - undecidability, etc.)
- 1 HWSQ from HW5 (Ch 5: Turing machine - reductions, etc.)
- HWOPT_COUNT = number of non-starred problems that are submitted (default 0)
- HWOPT_TOTAL= 1.5% x ceiling(HWOPT_COUNT/2)
- HWOPT = sum of scores of ceiling(HWOPT_COUNT/2) non-starred problems, each weighted to 1.5%
- I don't know policy : For exam problems, you can say "I don't know" for any partial question (for which some point/mark is mentioned) or for the entire question and you will be awarded 10% of the points allotted to that question.
- EXAM = 76 - HWOPT_TOTAL
- MID = midsem score weighted by floor of (3/7)*EXAM
- END = endsem score weighted by EXAM - MID
- CUMULATIVE (%) = QUIZ + HWS + HWOPT + MID + END
- At least 33% is required in the EndSem exam and 33% overall to pass this course.
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.
- Monday 9-10PM Kartikey Singh kartikey17242@
- Tuesday 6-7 Ayushi Jain ayushi19031@
- Tuesday 7-8 Kushagra Gupta kushagra19056@
- Wednesday 4-5 (or 6-7 if there is a meeting -- I will inform on Classroom) Debajyoti Bera dbera@
- Friday 7-8 Sanchita Saha sanchita21075@
- Saturday 4-5 Tharrma Shastha tharrmashasthav@
Material