\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{Spring 1999}{12 May 1999}{18}

\begin{center}
\Large{\bf Problem of the Week -- 6}
\end{center}

\bigskip

Consider the problem of making change for $n$ cents using the least number of
coins. 
\begin{itemize}
\item[(a)] Suppose the available coins are in the denominations $c^0, c^1,
\ldots, c^k$ for some integers $c > 1$ and $k \ge 1$.  Describe a greedy
algorithm to make change for $n$ cents using the above denominations.  Prove
that your algorithm yields an optimal solution.

\item[(b)]
Suppose the available coins are in the denominations $d_0$, $d_1$, \ldots,
$d_r$, where the only condition known is $d_r > d_{r-1} > \ldots > d_1 > d_0 =
1$.  Design an $O(rn)$ time and $O(r + n)$ space algorithm for the problem
using dynamic programming.
\end{itemize}

\end{document}


