Homework 10

**Abbreviations**

**DPV**=*Algorithms*, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.**PG**= Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

- Chapters 8 and 9 of DPV

(19 points) DPV, Exercise 8.1.

*Hint:*Binary search.(20 points) DPV, Exercise 8.2.

*Hint:*Ask the decision problem about certain variations of the input graph.(20 points) DPV, Exercise 8.3.

*Hint:*This is really easy.(20 points) DPV, Exercise 8.9

Specifically: Let be an instance of**SAT**where be the clauses to be satisfied. Let be the variables in this instance. We construct an instance of**Hitting Set**as follows:For , define the set of literals in .

For , define .

Let .Show that is a yes-instance of

**SAT**if and only if is a yes-instance of**Hitting Set**.(21 points) DPV, Exercise 8.10 parts (a), (c), and (d).