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

**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 beConsider the following definition of*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.*time constructible function*-A function T:N→N isNote 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.*time constructible*if T(n)≥n and there is a TM M that computes the function x↦T(|x|) in time T(|x|).

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)^{2}).**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_{1}, L_{2}∈ NP. Then is L_{1}∪ L_{2}∈ NP? What about L_{1}∩ L_{2}?**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.

**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_{1}, ..., 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.

**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_{1}, L_{2}in the class P,L_{1}≤_{p}L_{2}.**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_{1}, L_{2}∈ NP. Then is L_{1}∪ L_{2}∈ NP? What about L_{1}∩ L_{2}?**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_{1}, ..., 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,^{n}C_{2}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 beConsider the following definition of*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.*time constructible function*-A function T:N→N isNote 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.*time constructible*if T(n)≥n and there is a TM M that computes the function x↦T(|x|) in time T(|x|).

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)^{2}).**Deadline:**31-August-2013.

- Prove that 2SAT can be computed in polynomial time. Also, reason why the same technique fails for 3SAT.
**Instructor :**Deepanjan Kesh(deepkesh@)**Teaching Assistants :**

Assignment one can be found here.

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

2204

Monday | 11:00 am to 11:55 am |

Thursday | 9:00 am to 9:55 am |

Friday | 10:00 am to 10:55 am |

Sachin Shah | sachin.shah@ |

Khushboo Rani | khushboo@ |

Rakesh Pandey | |

Sanjay Kumar | |

P Sri Hari |

Mid Semester Examination | 10% |

End Semester Examination | 20% |

First Open Time Examination | 35% |

Second Open Time Examination | 35% |

Make-up Examination |

50%

M_{1} - Normalized marks of Mid Semester Examination.

M_{2} - Normalized marks of End Semester Examination.

M_{3} - Normalized marks of First Open Time Examination.

M_{4} - Normalized marks of First Open Time Examination.

X - Marks (out of 50) in Make-up Examination.

Let M = M_{1}+M_{2}+M_{3}+M_{4}. Then,

Final Score = | M, | if M >= 50 |
---|---|---|

50, | if M < 50 and M+X >= 50 | |

M+X, | if M < 50 and M+X < 50 |