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