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.

- 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\)?")
- Jeff Erickson's problem 27.2.
- 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.
- 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.
- Jeff Erickson's problem 29.1.
- Jeff Erickson's problem 29.4.
- Jeff Erickson's problem 29.19.
- Jeff Erickson's problem 29.23 (b),(c),(d).