Theory of Computation (2020)

Welcome #

Welcome to “Theory of Computation”. In this course, we are going to try and answer fundamental questions about the nature of computation such as:

Are all problems computable?
Does backtracking help?
Is there a best algorithm for all problems?
Does more time help?
Does more memory help?
Is verifying solutions easier than finding them?

Use this to add lectures to your Google calendar. The Google meet link for lectures is here.

Please use your iitgn email id to login to the lectures. If you don’t have an iitgn email id yet and plan to attend the lectures, write to me.

News #

17.11: Assignment 3 is uploaded
02.10: Assignment 2 is uploaded.
24.09: Monday’s lecture slot and Tuesday’s tutorial slot are swapped next week.
10.09: There will not be any meetings next week. Please watch the lecture videos on your own time. We will hold discussions for these lectures on 21.09.
27.08: The first quiz is on Thursday, Sep 3, 2PM IST.
26.08: Solutions to Homework 2 and 3 are uploaded. Follow the same link used to obtain homework sheet.
23.08: First assignment is uploaded.
20.08: Homework 3 is uploaded.
19.08: The tutorial on 25.08 and the lecture on 26.08 are swapped.

People #

Role	Person
Instructor	Balagopal Komarath
TA	Akash Pareek

Slots #

The lectures for this course will take place on Google meet during K slots. The tutorial will take place during the L1 slot.

Reading #

You may use any textbook in the syllabus. These materials differ only in presentation. I will follow the presentation in my notes. These will be regularly updated.

You can find my handwritten notes that support my lectures here.

Lectures #

(Aug 5) Overview (slides) (video)
(Aug 6) Alphabets, Strings, and Languages (part 1 part 2) (discussion)
(Aug 10) Finite Automata (part 1 part 2)
(Aug 13) Regular Expressions (video discussion)
(Aug 17) NFA: Introduction (part 1 part 2)
(Aug 19) RE to NFA (part 1 part 2)
(Aug 20) NFA to RE (part 1 part 2)
(Aug 24) NFA to DFA (video)
(Aug 25) Pumping Lemma (video)
(Aug 27) Myhill-Nerode Theorem (video)
(Sep 7) Turing Machines: Introduction (video)
(Sep 9) Turing Machines: Arithmetic (video)
(Sep 10) Turing Machines: Combinators (video)
(Sep 14) Turing Machines: Definition (video)
(Sep 16) Turing Machines: Variants (video)
(Sep 17) Turing Machines: One-way Infinite Tape (video)
(Sep 21) QA: Turing machines.
(Sep 23) Undecidability (video discussion)
(Sep 24) Universal TMs (video)
(Sep 29) The Halting Problem (video)
(Sep 30) Reductions (video)
(Oct 1) Properties of Reductions (video) (discussion)
(Oct 5) Examples of Reductions (video)
(Oct 8) The Computation History Method (video)
(Oct 19) Time Complexity (video discussion)
(Oct 21) The class P (video discussion)
(Oct 22) Poly-time reductions (1 2) (discussion)
(Oct 26) Verifiability (video)
(Oct 28) NP (video) (discussion)
(Nov 2) Reductions for NP (video) (discussion)
(Nov 4) Cook’s Reduction (video)
(Nov 5) Hardness and Completeness (video)
(Nov 9) HW6 (discussion)
(Nov 11) Space Complexity (video)
(Nov 12) LOG vs P (video) (discussion)
(Nov 16) Grammars and CFLs (video)
(Nov 18) Parse Trees and Ambiguity (video) (discussion)
(Nov 19) CNF and Membership (video)
(Nov 23) Push-down Automata (video)
(Nov 25) Pumping Lemma for CFLs (video)
(Nov 26) Conclusion (video)

Corrections #

(Oct 26, Lecture) The verifier TM M for HP verifies the validity of configuration sequence in terms of N, not M as mentioned in the lecture.

(Oct 22, Lecture) The time upper bounds mentioned in the lecture should be \(n^{a+ab}\).

(Sep 24, Lecture) When describing the algorithm, I mentioned search the second track for new state. It should be the third track, the one that contains the transition function.

(Aug 27, Lecture) The relation for L is called the Myhill-Nerode relation for L. Also, given a DFA for a language, the construction given in the proof of the only-if part need not give the Myhill-Nerode relation for L. In case the DFA is not optimal, it yields a more fine-grained relation. However, since even this fine-grained relation only has a finite number of equivalence classes, so does the Myhill-Nerode relation.

Classroom Quizzes #

Computation (form)
Strings (form)
Finite Automata (form)
Regular Expressions (form)
NFA: Introduction (form)
NFA and NFA to RE (form)
NFA & RE (form)
NFA to DFA (form)
Pumping Lemma (form)
Myhill-Nerode Theorem (form)
Programming TMs (form)
TMs and Computation (form)
Undecidability (form)
Universal TMs (form)
Halting Problem (form)
Reductions (form)
Reductions’ (form)
ERR to HP (form)
Complexity (form)
The class P (form)
Poly-time Reductions (form)
Verifiability (form)
NP (form)
Many-one Reductions (form)
Cook’s Reduction (form) (discussion)
Hardness and Completeness (form) (discussion)
Space Complexity (form) (discussion)
LOG vs P (form)
Grammars and CFLs (form)
Ambiguity (form)
PDA (form) (discussion)
Pumping lemma for CFLs (form) (discussion)

Quizzes #

(Sep 3) First Quiz. Submit via email or by uploading to this form.
(Oct 14) Second Quiz. Submit your solutions via email. (discussion solutions)
(Dec 04) Final

Assignments #

(Aug 30) First Assignment
(Oct 1) Second Assignment
(Nov 17) Third Assignment (Solutions 1 2 3 4 )

Homework #

(Aug 11) Homework 1 Solutions
(Aug 18) Homework 2
(Aug 26) Homework 3
(Sep 21) Homework 4
(Sep 28) Homework 5
(Nov 1) Homework 6
(Nov 5) Homework 7
(Nov 17) Homework 8

Tutorials #

(Aug 11) discussion
(Aug 18) demo discussion
(Aug 26) discussion
(Sep 8) discussion
(Sep 22) Questions about Homework - 4.
(Sep 28) HW4 (discussion) (solutions)
(Oct 6) HW5 (discussion)
(Nov 17) HW7 (discusssion)
(Nov 24) HW8 (discussion)

Software #

You may use simulators available here or elsewhere to aid you in learning the subject. Please note that simulators are strictly optional.

Evaluation #

Your grades will be determined using assignments and quizzes.

I will also give homework that will not be evaluated. The questions given as homework will be hard and are designed to deepen the understanding of the subject. You are encouraged to collaborate with others while solving homework problems after spending some time thinking about them on your own.

The assignment questions will be of moderate difficulty and you will be given 7 days or more to solve each assignment. No collaboration is allowed. When submitting solutions, you must write how you arrived at the solution and list any failed approaches.

There will be 3 time-bound quizzes. The problems will be easy provided that you have spent sufficient time on your homework and assignments.