\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}
 Solutions
\end{center}}

\vspace{1in}

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

{\bf solution:} Lets assume, wlog, that the player bets on number $1$. Then, 
we will tabulate the probabilities and the gains.

\begin{tabular}{|r|r|r|} \hline\hline
 number of dice &  probability & gain \\ \hline \hline
 $ 0$       &      $ (5/6)^3$   &-1 \\ \hline
 $ 1$       &      $3*(1/6)*(5/6)^2$&   1 \\ \hline
 $ 2$       &      $3*(1/6)^2*(5/6)$&   2 \\ \hline
 $ 3$       &      $1/6^3$          &   3 \\ \hline \hline
\end{tabular}

Therefore the expected gain is $ \frac{-5^3 + 3*5^2 + 6*5 + 3}{6^3} = \frac{-17}{216}$.

\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.)

{\bf solution:} We maintain a priority que (heap) which will contain the largest non
merged element from each sorted list. We initiate the heap with the
largest element from each list. This initiation step takes $O(k)$ using
the heapify algorithm.

A step of the algorithm would consist of adding the element at the top
of the heap to the end of the new merged list, replacing the top of
the heap with the top element of the sorted list to which the current
heap top belongs, and reheapifying in $O(\log k)$. (Note this means we should
maintain pointers from the heap elements to the $k$ sorted lists).
Since there are $n$ such operations, this gives a sketch of an
$O(n \log k) + O(k \log k) = O(n \log k)$ algorithm.

The above sketch didn't specify how to deal with the case where
some of the sorted lists ran out before the rest. There are
a number of ways to deal with that. Here are two:
\begin{itemize}
\item when removing the last element of a sorted list from the heap,
insert $- \infty$ into the heap instead of the next (and non-existent)
element of the list. Alternatively, you can compute the smallest element
of all the numbers in $O(n)$ and use that value minus one instead of
$ - \infty $.
\item
When you delete the last element of a sorted list from the heap, simply
dont insert any new element into the heap, so the heap becomes smaller.
In this case "delete" means the heap delete operation which consists
of replacing the element to be deleted with the last element of
the heap and reheapifying. 
\end{itemize}



\section*{Problem 3}
{\bf solution:} Here is a high level description of the requred
$k$-merge-sort algorithm.

{\em merge-sort(S,k):}
\begin{enumerate}

\item   if $ | S| \leq max(3,k(| S | ))$ use a simple sort
  
\item divide the set S into k disjoint sets $S_{1} \cdots \S_{k}$.
          This step takes $O(n)$
\item merge-sort($S_1,k(|S_1|)$) ... merge-sort($S_k,k(|S_k|)$)
\item  merge the k sorted lists from step $2$ using algorithm from question $2$.
          This step takes $O( n \log k)$
\end{enumerate}

note that $k$ can be a function of the set sizes, and
that's why the  notation $k(|S_i|)$ is used.
If $k = \sqrt n$ we get the following recursion formula:
\[ T(n) = \sqrt n T( \sqrt n) + O(n) + O(n \log \sqrt n) \]       
or, for some constant $C$:
\[ T(n) = \sqrt n T( \sqrt n) + C n \log n \]       
we will show that $T(n) < dn\log n$ by induction.
assume it is true for $m < n$, so we have to show that:
\[ \sqrt n  0.5 d \sqrt n \log n + C n \log n < d n \log n \]
or
\[ C n \log n < 0.5 d n \log n \]
which is true if we pick $d=3C$.
The base case of the induction is when $|S| < 3 $, which take a constant time
to sort.
  

\end{document}