Description
Practice problems (don’t turn in):
-
[DPV] Problem 8.3 (Stingy SAT)
-
[DPV] Problem 8.4 (a),(b),(c) (Clique-3)
-
[DPV] Problem 8.10 part (a) (Subgraph isomorphism, you are encourage to try the others)
-
[DPV] Problem 8.13 (graph problems: NP vs. poly time)
Problem 1 [DPV] Problem 8.1 (TSP optimization versus search)
Solution:
Problem 2 [DPV] Problem 8.8 (Exact 4-SAT)
Solution:
Problem 3 [DPV] Problem 8.9 (Hitting set)
Solution:
Problem 4 [DPV] Problem 8.14 (Clique+IS)
Solution:
