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).