2018-05-14
May 14 Final Review.
Solution for Q1.
Posted by Heemany Shekhar, Nag Mani, Revanth Akella
<nowiki>
Solution for Q1.
Posted by Heemany Shekhar, Nag Mani, Revanth Akella
((resource:20180514_135431.jpg|Resource Description for 20180514_135431.jpg))
</nowiki>
Posted by Dean Johnson, Sharan Duggirala, Saketh Saxena
Q3:
a mod 42, a mod 2 = 0, a mod 3 = 2, a mod 7 = 5
m1 = 42 / 2 = 21 m2 = 42 / 3 = 14 m3 = 42 / 7 = 6
t1 = 21^-1 mod 2 = 1 t2 = 14^-1 mod 3 = 2 t3 = 6^-1 mod 7 = 6
c1 = 21 * 1 = 21 c2 = 14 * 2 = 28 c3 = 6 * 6 = 36
a = (0*21) + (2*28) + (5*36)
= 56 + 180 = 26 mod 42 = 26
Posted by Dean Johnson, Sharan Duggirala, Saketh Saxena
Q3:
a mod 42, a mod 2 = 0, a mod 3 = 2, a mod 7 = 5
m1 = 42 / 2 = 21
m2 = 42 / 3 = 14
m3 = 42 / 7 = 6
t1 = 21^-1 mod 2 = 1
t2 = 14^-1 mod 3 = 2
t3 = 6^-1 mod 7 = 6
c1 = 21 * 1 = 21
c2 = 14 * 2 = 28
c3 = 6 * 6 = 36
a = (0*21) + (2*28) + (5*36)
= 56 + 180 = 26 mod 42 = 26
((Solution by Dean Johnson, Sharan Duggirala and Saketh Saxena))
(Edited: 2018-05-14)
<nowiki>((Solution by Dean Johnson, Sharan Duggirala and Saketh Saxena))
((resource:image_123923953.JPG|Resource Description for image_123923953.JPG))
</nowiki>
Solution for Q2.
Posted by Heemany Shekhar, Nag Mani, Revanth Akella
<nowiki>
Solution for Q2.
Posted by Heemany Shekhar, Nag Mani, Revanth Akella
((resource:20180514_142436.jpg|Resource Description for 20180514_142436.jpg))
</nowiki>
Team: Pratik, Niket, kunal
APPROX-VERTEX-COVER (I wrote APPROX-SET-COVER on board, please igore that )
(Edited: 2018-05-22)
Team: Pratik, Niket, kunal
APPROX-VERTEX-COVER (I wrote APPROX-SET-COVER on board, please igore that )
((resource:20180514_140958.jpg|Resource Description for 20180514_140958.jpg))
Kunal, Niket, Pratik
Q8 )
Kunal, Niket, Pratik <nowiki>
</nowiki>
Q8 ) <nowiki>
</nowiki>
((resource:Screenshot from 2018-05-14 15-00-19.png|Resource Description for Screenshot from 2018-05-14 15-00-19.png))
Vincent, Nick, Ravali
Problem 9 :
(Edited: 2018-05-14)
Vincent, Nick, Ravali
Problem 9 :
((resource:IMG_2746.JPG|Resource Description for IMG_2746.JPG))
Nick, Vincent, Ravali
Problem 10 :
(Edited: 2018-05-14)
Nick, Vincent, Ravali
Problem 10 :
((resource:IMG_2744.jpg|Resource Description for IMG_2744.jpg))
2018-05-15
Siddharth, Shantanu, Shashank
Ans.5) Define NP, NP-complete, and NP-hard. Argue the problem of determining where every assignment to a 3-SAT instance is satisfying is NP-hard.
NP: A Language L belongs to NP if there exists a two input polynomial-time algorithm A and a constant c such that
L = { x ∈ {0,1}* : ∃y, |y| = O(|x|^{c}) and A(x,y)=1 }
NP-Complete: A Language L is NP-Complete if 1) L ∈ NP, and 2) L' ≤ L in polynomial time, for every L' ∈ NP
NP-Hard : A language which satisfies (2) but not necessarily (1) is called NP-Hard. We can say that NP-Complete is a subset of NP-Hard.
We are trying to solve the second part of this question, if anyone feels they have a solution, do upload.
Siddharth, Shantanu, Shashank
Ans.5) Define NP, NP-complete, and NP-hard. Argue the problem of determining where every assignment to a 3-SAT instance is satisfying is NP-hard.
----
NP: A Language L belongs to NP if there exists a two input polynomial-time algorithm A and a constant c such that
L = { x ∈ {0,1}* : ∃y, |y| = O(|x|^{c}) and A(x,y)=1 }
NP-Complete: A Language L is NP-Complete if
1) L ∈ NP, and
2) L' ≤ L in polynomial time, for every L' ∈ NP
NP-Hard : A language which satisfies (2) but not necessarily (1) is called NP-Hard. We can say that NP-Complete is a subset of NP-Hard.
----
We are trying to solve the second part of this question, if anyone feels they have a solution, do upload.
Siddharth, Shantanu, Shashank
Ans 6.
p-time reduction from 3-SAT to CLIQUE Let F=C_1 ∧ C2... ∧ C_k be an instance of 3SAT. For each C_r=(l^r_1∨l^r_2∨l^r_3), we put a triple of vertices into our graph G, v^r_1,v^r_2,v^r_3. We put an edge between vertices v^r_i and v^s_j if they are in different triples and their corresponding literals are not negations of each other. Let (G,k) be the output instance of CLIQUE. Notice if there is a satisfying assignment to F then if we look at the corresponding vertices v^r_j of at least one satisfied literal/clause, it will be a CLIQUE of size k in G. As there are no edges between vertices coming from the same clause, any CLIQUE of size k has to have at least one vertex v^r_j for each 1≤r≤k. Choosing an assignment so that the corresponding literals for each v^r_j evaluate to true gives a satisfying assignment. So the reduction works.
Siddharth, Shantanu, Shashank
Ans 6.
p-time reduction from 3-SAT to CLIQUE
Let F=C_1 ∧ C2... ∧ C_k be an instance of 3SAT. For each C_r=(l^r_1∨l^r_2∨l^r_3), we put a triple of vertices into our graph G, v^r_1,v^r_2,v^r_3. We put an edge between vertices v^r_i and v^s_j if they are in different triples and their corresponding literals are not negations of each other. Let (G,k) be the output instance of CLIQUE. Notice if there is a satisfying assignment to F then if we look at the corresponding vertices v^r_j of at least one satisfied literal/clause, it will be a CLIQUE of size k in G. As there are no edges between vertices coming from the same clause, any CLIQUE of size k has to have at least one vertex v^r_j for each 1≤r≤k. Choosing an assignment so that the corresponding literals for each v^r_j evaluate to true gives a satisfying assignment. So the reduction works.
(c) 2024 Yioop - PHP Search Engine