Theory of Computing

Table of Contents

1. 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.

2. 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.

3. People

Role Person
Instructor Balagopal Komarath
TA Akash Pareek

4. Slots

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

5. 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.

6. Lectures

7. 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.

8. Classroom Quizzes

9. Quizzes

10. Assignments

11. Homework

12. Tutorials

13. Software

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

14. 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.