\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2000}{24 January 2000}{6}

\begin{center}
\Large{\bf Problem Set 2 (due February 3)}
\end{center}

\bigskip

{\bf 1. (15 points)} Design an efficient algorithm to merge $k$ sorted
lists, each of length $n$, into one sorted list of length $nk$.
Analyze the worst-case running time of your algorithm.  Make your
algorithm as efficient as you can, in terms of its worst-case running
time.

{\bf 2. (10 points)} Exercise~7.5--3, page 151.

{\bf 3. (5 $\times$ 5 = 25 points)} Problem~7--2, page 152.

{\bf 4. (6 + 6 + 3 = 15 points)} Problem~8--3, page 169.

{\bf 5. (15 points)} Suppose you have discovered a way of multiplying
two $k \times k$ matrices using $m$ multiplications, where $k > 2$ is
a positive integer and $m \ge k^2$.  Generalize the divide-and-conquer
algorithm of Strassen to derive an $O(n^{\log_k m})$ matrix
multiplication algorithm.  Now, solve Exercise~31.2--4, page 744.
\end{document}
