\documentstyle [12pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ignore}[1]{}
\newcommand{\remark}[1]{[{\small{\bf Editorial Remark: }#1}]}


\newcommand{\ceiling}[1]{\lceil #1 \rceil}

\begin{document}
\sloppy

{\large
CMU 15-451 \hfill ASSIGNMENT \# 2 \hfill FALL 1993
\begin{center}
DUE: Thursday September 16, 1992
\end{center}}

\vspace{1in}

\section*{Problem 1 \quad CLR $6.3-3$}

A carnival game consists of three dice in a cage. A player can bet a dollar
on any of the numbers $1$ through $6$. The cage is shaken, and the payoff is
as follows. If the player's number does not appear on any of the dice, he loses
his dollar. Otherwise, if his number appears on exactly $k$ of the
three dice, for $k=1,2,3$, he keeps his dollar and wins $k$ more dollars.
What is his expected gain from playing the carnival game once?

\section*{Problem 2 \quad CLR $7.5-6$}

Give an $O(nlg k)$ algorithm to merge $k$ sorted lists into
one sorted list, where $n$ is the total number of elements in all
the input lists. ( {\it Hint:} Use a heap for a $k$-way merging.)


\section*{Problem 3}

Devise a recursive sorting algorithm based on the previous problem.
That is using $k$-way merging algorithm in each level of the
recursion. What's the complexity of this sorting algorithm when
$k=\sqrt n$ ?

\end{document}