% -*- compile-command: "rubber -d --unsafe hw-08-dynamic-programming-2.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=8,date=October\ 30,topic=Dynamic\ programming\ II]{../algorithms-hw}
\begin{document}
\coversheet
\begin{question}[10 points] \label{q:subset} This problem is similar to one we
did in class, but slightly more general. Suppose we have a set
$\{x_1, x_2, \dots, x_n\}$ of $n$ positive integers, and a target
sum $S$, which is a positive integer. In class, we considered
finding a subset of $\{x_1, \dots, x_n\}$ whose sum is \emph{exactly
equal to} $S$. Instead, let's now consider finding a subset whose
sum is \emph{as close to $S$ as possible without going over}; that
is, the subset with the largest possible sum $\leq S$. For example,
given the set $\{1,2,7,12\}$ and the target sum $18$, there is no
subset which sums exactly to $18$, but the one which comes closest
without going over is $\{12,2,1\}$ which sums to $15$. Note that
$\{12,7\}$, with a sum of $19$, is closer to the target in an
absolute sense, but it is greater than the target; we are interested
in the biggest sum which is $\leq$ the target.
\begin{enumerate}[label=(\alph*)]
\item Describe a simple brute-force algorithm for solving this
problem. What is the running time of the algorithm?
\item \marginnote{\emph{\ref{q:subset}}\quad\qrcode{Let\ $m[k,s]$\ be\
the\ best\ possible\ sum\ using\ only\ $x_1$\ through\ $x_k$\ which\ is\ at\
most\ $s$.}}
Using dynamic programming, describe an algorithm with running time $\Theta(nS)$.
Be sure that you explain how to find not only the maximum possible
sum, but also the actual subset which has that sum. Justify the
correctness of your algorithm.
\item This is known as a \emph{psuedopolynomial-time} algorithm: the
running time is a polynomial in the \emph{value} of $S$, but
actually exponential in terms of the \emph{size} of the input
(\emph{i.e.} the number of bits needed to represent $S$).
Give one example of a set of inputs for which your dynamic programming
solution would be faster, and one example of a set of inputs for
which the brute force algorithm would be faster.
\end{enumerate}
\end{question}
\begin{question}[10 points]
Consider the problem of making change for $C$ cents using the fewest
possible number of coins. Assume that each coin's value is an
integer.
\begin{enumerate}[label=(\alph*)]
\item Describe a greedy algorithm to make change for $C$ cents using
US quarters, dimes, nickels, and pennies.\marginnote{It turns out
that the greedy algorithm is actually optimal for US coins (and
most real-world coin systems), though coming up with a proof of
this fact is nontrivial.}
\item Give a set of coin denominations for which the greedy
algorithm does not yield an optimal solution. Your set should
include a penny so that there is a solution for every value of $C$.
\item Design and analyze an algorithm to make change using the fewest
number of coins that works for any set of coins. That is, as input
your algorithm should take
\begin{itemize}
\item $n$, the number of different coin types;
\item a list $c_1$, $c_2$, \dots, $c_n$ giving the values of the
different coins (you may assume they are already sorted from
smallest to largest); and
\item the number of cents $C$ we would like to make change for.
\end{itemize}
As output your algorithm should either report that it is not
possible to make the required amount $C$ using the given coins, or
give a multiset\footnote{A multiset is like a set that allows
duplicate elements.} of coins which add up to $C$ such that the
number of coins in the multiset is as small as possible. For
example, if given as input $c_1 = 1$, $c_2 = 5$, $c_3 = 20$ and the
target value $C = 47$, your algorithm should output
$\{20, 20, 5, 1, 1\}$. Note that we assume there is an unlimited
supply of coins of each type. Be sure to justify your algorithm's
correctness and analyze its time complexity.
\end{enumerate}
\end{question}
\end{document}