CS301 : Theory of Computation

07-October-2013

The mid semester examination's question paper can be found here.
The first open examination's question papers can be found here and here.

18-September-2013

Group: Vishal Anand, Shashank Rai, Vishavdeep Mattu.
- Problem:[Arora, Barak - Exercise 1.5] Consider the following definition of Oblivious Turing machine -
  A Turing machine M is said to be oblivious if its head movements do not depend on the input but only on the input length. That is, M is oblivious if for every input x ∈ {0,1}^* and i ∈ N, the location of M's head at the i^th step of execution on input x is only a function of |x| and i.
  Consider the following definition of time constructible function -
  A function T:N→N is time constructible if T(n)≥n and there is a TM M that computes the function x↦T(|x|) in time T(|x|).
  Note that if a Turing machine is restricted to work within T(|x|) steps on input x, and the function T is time constructible, then the Turing machine can compute T(|x|) i.e., the Turing will know how much time it will have to compute the output.
  Show that for every time-constructible T:N→N, if L can be computed in time T(n), then there is an oblivious TM that decides L in time O(T(n)²).
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 16-September-2013.
- Review:The proof is well written, but there is one point which needs a bit more explanation. Since the movement of the tape head in oblivious Turing machine are not dependent on the input, it is not clear how the marker, denoting the tape head of the traditional Turing machine, can be moved to the right of the current location. The issue arises because the step of the traditional Turing machine is implemented on the way back by the oblivious Turing machine.
Group: Aditya Kumar Jha, Arun Bhati, Shreyas Basarge.
- Problem:[Arora, Barak - Exercise 2.18] Prove that the language HAMCYCLE of undirected graphs that contain Hamltonian cycle (a simple cycle involving all the vertices) is NP-complete.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 15-September-2013.
- Review:An elegant, well written, easy to follow proof.
Group: Nishant Yadav, Rohan Kumar Kwatra, Rohit Kamra.
- Problem:[Arora, Barak - Exercise 2.16] In the MAX CUT problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset of vertices S such that there are at least K edges that have one endpoint in S and one endpoint in S. Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 15-September-2013.
- Review:An excellent construction with the proof written in bulleted points showing the progression of thought very well. The reader would be best served if the "MAX CUT implying INDSET" is written in a more verbose manner.
Group: Mainak Sethi, Vivek Bhargav, Chaitanya Agarwal.
- Problem: [Arora, Barak - Exercise 2.15] In the VERTEX COVER problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset S of at most K vertices such that every edge (i,j) of G, at least one of i or j is in S (such a subset is called a vertex cover of G). Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 15-September-2013.
- Review: A cute little argument, but it would have been nice if the argument, however trivial, for "vertex cover implies independent set" was also provided.
Group: Piyush Dhore, Soumak datta, Charanjeet Ghai.
- Problem: [Arora, Barak - Exercise 2.10] Suppose L₁, L₂ ∈ NP. Then is L₁ ∪ L₂ ∈ NP? What about L₁ ∩ L₂?
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 12-September-2013.
- Review: A well written, well argued proof.
Group: Harshil Lodhi, Shobhit Chaurasia, Hitesh Arora
- Problem: Prove that 2SAT is in the complexity class P i.e., given any expression in 2CNF, you can decide whether it has a satisfying assignment in polynomial time.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted: 12-September-2013.
- Review: A beautifully written, well formatted, lucid argument.

11-September-2013

Group: V.Abhinav Bommireddi, K.S.V.A Ravi Teja, G. Bhanu Teja.
- Problem: [Arora, Barak - Exercise 2.15] In the CLIQUE problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset S of at least K vertices such that every two distinct vertices u,v ∈ S have an edge between them (such a subset is called a clique of G). Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted:7-September-2013.
- Review:The proof is correct but not complete - the proof that CLIQUE ∈ NP is missing.
Group: Chetan, Jillella Reddy, B. Prasanna Kumar.
- Problem: [Arora, Barak - Exercises 2.8,2.9] Let HALT be the following language -
  HALT = { <M,x> : The Turing machine M halts on input x }.
  Prove that if a language L is in the class NP, then L ≤_p HALT. Also prove that the relation ≤_p though is reflexive and transitive, it is not symmetric.
- Deadline: 31-August-2013.(Note: I noticed that I missed this field while declaring the problems, but I would assume that a uniform deadline applied for everybody)
- Solution: here.
- Submitted:9-September-2013.
- Review:The proof is correct but it is not well written. The motivation of the Turing machine M', though clear from the proof, has not been declared earlier. The relation to halting problem is clear from the context but it should have been more explicitly stated.
Group: Shubham Luhadia, Simrat Singh, Rahul Huilgol.
- Problem:[Arora, Barak - Exercise 2.17] In the SUBSET SUM problem, we are given a list of n numbers A₁, ..., A_n and a number T and need to decide whether there exists a subset S ⊆ [n] such that ∑_{i ∈ S} A_i = T (the problem size is the sum of all the bit representations of all the numbers). Prove that SUBSET SUM is NP-complete.
- Deadline: 31-August-2013.
- Solution: here.
- Submitted:7-September-2013.
- Review:This is the most well organized proof I have seen. The solution is also very ingenious, thorough and extensive. They have gone through 3 reductions to arrive at the solution. I would like to suggest a few modifications to the writing -
  - In Section D, the restriction of the size of integers in the problem M to O(log(n)) bits is not necessary.
  - In Section E, the necessity of choosing such an elaborate T should be made more clear.
  - The expression for ∑A_j looks like product of terms on the R.H.S. rather than collection of bits.

25-August-2013

Group: Abhishek Sarkar, Ajay Kumar Kilaka, Ankit Kanwat.
- Problem: Prove that every language in the class P is P-complete i.e., given any two languages L₁, L₂ in the class P,
  L₁ ≤_p L₂.
- Deadline: 31-August-2013.
Group: Harshil Lodhi, Shobhit Chaurasia.
- Problem: Prove that 2SAT is in the complexity class P i.e., given any expression in 2CNF, you can decide whether it has a satisfying assignment in polynomial time.
- Deadline: 31-August-2013.
Group: Chetan, Jillella Reddy, B. Prasanna Kumar.
- Problem: [Arora, Barak - Exercises 2.8,2.9] Let HALT be the following language -
  HALT = { <M,x> : The Turing machine M halts on input x }.
  Prove that if a language L is in the class NP, then L ≤_p HALT. Also prove that the relation ≤_p though is reflexive and transitive, it is not symmetric.
Group: Piyush Dhore, Soumak datta, Charanjeet Ghai.
- Problem: [Arora, Barak - Exercise 2.10] Suppose L₁, L₂ ∈ NP. Then is L₁ ∪ L₂ ∈ NP? What about L₁ ∩ L₂?
- Deadline: 31-August-2013.
Group: V.Abhinav Bommireddi, K.S.V.A Ravi Teja, G. Bhanu Teja.
- Problem: [Arora, Barak - Exercise 2.15] In the CLIQUE problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset S of at least K vertices such that every two distinct vertices u,v ∈ S have an edge between them (such a subset is called a clique of G). Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
Group: Mainak Sethi, Vivek Bhargav, Chaitanya Agarwal.
- Problem: [Arora, Barak - Exercise 2.15] In the VERTEX COVER problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset S of at most K vertices such that every edge (i,j) of G, at least one of i or j is in S (such a subset is called a vertex cover of G). Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
Group: Rachit Kumar.
- Problem: [Arora, Barak - Exercise 2.17] In the EXACTLY ONE 3SAT problem, we are given a 3CNF formula φ and need to decide if there exists a satisfying assignment u for φ such that every clause of φ has exactly one TRUE literal. Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
Group: Shubham Luhadia, Simrat Singh, Rahul Huilgol.
- Problem:[Arora, Barak - Exercise 2.17] In the SUBSET SUM problem, we are given a list of n numbers A₁, ..., A_n and a number T and need to decide whether there exists a subset S ⊆ [n] such that ∑_{i ∈ S} A_i = T (the problem size is the sum of all the bit representations of all the numbers). Prove that SUBSET SUM is NP-complete.
- Deadline: 31-August-2013.
Group: Md. Siddiq, Madhu prudhvi raj, Harsha nadimpalli.
- Problem:[Arora, Barak - Exercise 2.18] Prove that the language HAMPATH of undirected graphs with Hamiltonian paths is NP-complete.
- Deadline: 31-August-2013.
Group: Rachuri Anirudh, Harsha S.T., Harshith Reddy.
- Problem:[Arora, Barak - Exercise 2.18] In the TRAVELLING SALESPERSON problem, we are given a set of n nodes, ⁿC₂ numbers d_i,j denoting the distances between all pairs of nodes, and a number K. We have to decide if there is a closed circuit (i.e., a "salesperson tour") that visits every node exactly once and has total length at most K. Prove that the TRAVELLING SALESPERSON problem is NP-complete.
- Deadline: 31-August-2013.
Group: Aditya Kumar Jha, Arun Bhati, Shreyas Basarge.
- Problem:[Arora, Barak - Exercise 2.18] Prove that the language HAMCYCLE of undirected graphs that contain Hamltonian cycle (a simple cycle involving all the vertices) is NP-complete.
- Deadline: 31-August-2013.
Group: Nishant Yadav, Rohan Kumar Kwatra, Rohit Kamra.
- Problem:[Arora, Barak - Exercise 2.16] In the MAX CUT problem, we are given an undirected graph G and an integer K and have to decide whether there is a subset of vertices S such that there are at least K edges that have one endpoint in S and one endpoint in S. Prove that this problem is NP-complete.
- Deadline: 31-August-2013.
Group: Vishal Anand, Shashank Rai, Vishavdeep Mattu.
- Problem:[Arora, Barak - Exercise 1.5] Consider the following definition of Oblivious Turing machine -
  A Turing machine M is said to be oblivious if its head movements do not depend on the input but only on the input length. That is, M is oblivious if for every input x ∈ {0,1}^* and i ∈ N, the location of M's head at the i^th step of execution on input x is only a function of |x| and i.
  Consider the following definition of time constructible function -
  A function T:N→N is time constructible if T(n)≥n and there is a TM M that computes the function x↦T(|x|) in time T(|x|).
  Note that if a Turing machine is restricted to work within T(|x|) steps on input x, and the function T is time constructible, then the Turing machine can compute T(|x|) i.e., the Turing will know how much time it will have to compute the output.
  Show that for every time-constructible T:N→N, if L can be computed in time T(n), then there is an oblivious TM that decides L in time O(T(n)²).
- Deadline: 31-August-2013.

16-August-2013

Prove that 2SAT can be computed in polynomial time. Also, reason why the same technique fails for 3SAT.

14-August-2013

Assignment one can be found here.

Course details

Syllabus

http://www.iitg.ernet.in/cse/csecourses/?courseCode=CS301

Class Room

2204

Class Slots

Monday	11:00 am to 11:55 am
Thursday	9:00 am to 9:55 am
Friday	10:00 am to 10:55 am

Teaching Staff

Instructor : Deepanjan Kesh(deepkesh@)
Teaching Assistants :

Sachin Shah	sachin.shah@
Khushboo Rani	khushboo@
Rakesh Pandey
Sanjay Kumar
P Sri Hari

Evaluation Criteria

Weightages

Mid Semester Examination	10%
End Semester Examination	20%
First Open Time Examination	35%
Second Open Time Examination	35%
Make-up Examination

Passing percentange

50%

How to calculate your final score?

M₁ - Normalized marks of Mid Semester Examination.
M₂ - Normalized marks of End Semester Examination.
M₃ - Normalized marks of First Open Time Examination.
M₄ - Normalized marks of First Open Time Examination.
X - Marks (out of 50) in Make-up Examination.

Let M = M₁+M₂+M₃+M₄. Then,

Final Score =	M,	if M >= 50
	50,	if M < 50 and M+X >= 50
	M+X,	if M < 50 and M+X < 50