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

\head{3390}{Analysis of Algorithms}{10 November 1998}{18}

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

Suppose you are the parts manager of a computer assembly firm.  Your firm
wants to buy $n$ disks, one for each of the $n$ computers the firm plans to
assemble this year.  There are $m$ disk suppliers, each of which produces
disks of the quality desired by your firm.  For any supplier $i$ and any
integer $j$, you are given the cost of buying $j$ disks from supplier $i$.
(More formally, supplier $i$ provides an array $A_i[1..n]$, where $A_i[j]$ is
the cost of purchasing $j$ disks from supplier $i$.)

Design an efficient algorithm to determine how many disks you would purchase
from each supplier such that the total cost of purchasing the $n$ disks is
minimized.  Analyze the running time of the algorithm.  ({\em Hint:} Use
dynamic programming.)

\end{document}