# Homework 6

These are practice problems. Pick any of them to practice the course material. You do not need to submit your solution, it will also not be graded.

1. Give an $$O(nt)$$ algorithm for SUBSET SUM. (Hint: Look at subproblems of the form "does a subset of $$\{a_1, a_2,\ldots , a_i\}$$ add up to $$s$$?")
2. Jeff Erickson's problem 27.2.
3. Prove that finding the second largest element in an $$n$$-element array requires exactly $$n − 2 + \lceil\log n\rceil$$ comparisons in the worst case. Prove the upper bound by describing and analyzing an algorithm; prove the lower bound using an adversary argument.
4. In an undirected graph $$G = (V, E)$$, we say $$D \subset V$$ is a dominating set if every $$v \in V$$ is either in $$D$$ or adjacent to at least one member of $$D$$. In the DOMINATING SET problem, the input is a graph and a budget $$b$$, and the aim is to find a dominating set in the graph of size at most $$b$$, if one exists. Show a reduction from SAT to DOMINATING SET.
5. Jeff Erickson's problem 29.1.
6. Jeff Erickson's problem 29.4.
7. Jeff Erickson's problem 29.19.
8. Jeff Erickson's problem 29.23 (b),(c),(d).