\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}
\newcommand{\color}{\mbox{{\em color}}}
\newcommand{\myyear}{\mbox{{\em year}}}
\newcommand{\salary}{\mbox{{\em salary}}}
\newcommand{\salarysum}{\mbox{{\em salarysum}}}
\newcommand{\num}{\mbox{{\em num}}}
\newcommand{\prefixnum}{\mbox{{\em prefixnum}}}
\newcommand{\prefixsalarysum}{\mbox{{\em prefixsalarysum}}}
\newcommand{\prefixsalary}{\mbox{{\em prefixsalary}}}
\newcommand{\treenum}{\mbox{{\em treenum}}}
\newcommand{\treesalarysum}{\mbox{{\em treesalarysum}}}
\newcommand{\pointer}{\mbox{{\em pointer}}}

\newcommand{\cp}{\mbox{{\em copy}}}
\newcommand{\ins}{\mbox{{\em insert}}}
\newcommand{\rep}{\mbox{{\em replace}}}
\newcommand{\del}{\mbox{{\em delete}}}
\newcommand{\twi}{\mbox{{\em twiddle}}}
\newcommand{\kil}{\mbox{{\em kill}}}
\newcommand{\cost}{\mbox{cost}}
\newcommand{\op}{\mbox{{\em op}}}
\newcommand{\Compute}{\mbox{{\sc Compute}}}

\newcommand{\remaining}{\mbox{{\em remaining}}}
\newcommand{\print}{\mbox{{\bf print}}}
\newcommand{\minpair}{\mbox{{\em minpair}}}
\newcommand{\Max}{\mbox{{\em Max}}}

\renewcommand{\insert}{\mbox{{\sc Insert}}}
\newcommand{\exmin}{\mbox{{\sc Extract-Min}}}
\newcommand{\exmax}{\mbox{{\sc Extract-Max}}}
\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\sempty}{\mbox{{\sc Stack-Empty}}}
\newcommand{\Nil}{\mbox{{\sc Nil}}}
\newcommand{\pop}{\mbox{{\sc Pop}}}
\newcommand{\push}{\mbox{{\sc Push}}}
\newcommand{\heapify}{\mbox{\sc Heapify}}

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

\head{1390}{Algorithms}{Winter 2000}{10 February 2000}{9}

\begin{center}
\Large{\bf Sample Solution to Problem Set 2}
\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 Answer:} There are two different $O(nk\lg k)$ time algorithms for
this problem.
\begin{itemize}
\item The first one is a divide-and-conquer algorithm.  It splits the
  $k$ lists into two parts, one containing $\lfloor k/2 \rfloor$ lists
  and the other containing $\lceil k/2 \rceil $ lists.  Then, we
  recursively call the algorithm on the two parts and obtain two
  sorted lists, the total number of elements being $nk$.  Finally, we
  merge the two lists in $O(nk)$ time using the merge algorithm
  covered in class to obtain a single sorted list with $nk$ elements.
  The correctness of the algorithm directly follows from the
  correctness of the merge algorithm.
  
  The recurrence for the worst-case running time is calculated as
  follows.  Let $T(k)$ denote the worst-case running time of merging
  together $k$ sorted lists, each of length $n$.  Clearly, $T(1) =
  \Theta(1)$.  And the recursion yields:

\[  T(k) = 2T(k/2) + nk.\]

Using the Master Theorem (viewing the recurrence as a function of $k$
and $n$ as fixed), we obtain $T(k) = nk \lg k$.

\item The second algorithm is a generalization of the two-way merge
  algorithm to a $k$-way merge.  Here, we scan through the $k$ lists,
  each time maintaining a pointer the smallest element in each list
  that has not been placed in the final list.  We maintain these
  smallest elements in a heap (or a priority queue).
  
  We first place the smallest element in each list into a heap.  This
  takes $O(k)$ time (a single call to {\sc Build-Heap}).  Then, we
  extract the minimum of the heap, place it in the first position of
  the final list.  We then insert the next element from the list where
  the extracted element belonged, into the heap and proceed.  
  
  We will thus go through $nk$ iterations. In each iteration, we
  extract a minimum from a heap of $k$ elements ($O(\lg k)$ time),
  copy this element into the final list ($O(1)$ time), and then insert
  a new element into the heap ($O(\lg k)$ time).  Therefore, the total
  running time of the algorithm is $O(nk \lg k)$.
\end{itemize}

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

{\bf Answer:} Whenever we add a record $x$ to our dynamic set $S$, we augment
$x$ by a field, which we call its {\em sequence number}.  Let $s[x]$ denote the
sequence number of $x$.  We also maintain a variable $\Max$ that stores the
largest sequence number assigned thus far.

We represent a first-in first-out queue or a stack by a priority queue in
where the key is the sequence number.
\begin{itemize}
\item First-in first-out queue: We use a priority queue that provides the
\insert\ and \exmin\ operations.  We assume that if $S$ is empty then \exmin\
returns \Nil.  The operations \enq\ and \deq\ for a FIFO queue $Q$ are defined
as follows:
\begin{tabbing}
\= \enq($Q$, $x$)\\
\> 1. \= $\Max \leftarrow \Max + 1$ \\
\> 2. \> $s[x] \leftarrow \Max$\\
\> 3. \> \insert($S$, $x$)\\
\end{tabbing}

\begin{tabbing}
\= \deq($Q$, $x$)\\
\> 1. \= $x \leftarrow \exmin(S)$\\
\> 2. \> \myif\ \= $x = \Nil$\\
\> 3. \> \> \ret\ \Nil\\
\> 4. \> \myelse\ \ret\ $x$
\end{tabbing}

For the correctness of these operations, we need to prove that if an item $x$
is enqueued after item $y$, then $x$ is dequeued after $y$.  If $x$ is
enqueued after $y$, then since the sequence number always increases, the key
of $x$ is greater than the key of $y$.  When $x$ is enqueued, we have two
cases.  If $y$ has already been dequeued, then there is nothing to prove.
Otherwise, both $x$ and $y$ are in the priority queue.  Since the key of $x$
is greater than the key of $y$ and the dequeueing operation always extracts
the item with the minimum key, it follows that $y$ is dequeued before $x$.

\item Stack:  We will use a priority queue that provides the \insert\ and
\exmax\ operations.  We assume that if $S$ is empty then \exmax\
returns \Nil.  The operation \push\ is exactly the same as \enq\ above.  The
operation \pop\ is exactly the same as \deq\ above with \exmin\ replaced by
\exmax.  The correctness of these operations follows in a manner analogous to
the correctness of the first-in-first-out queue operations given above. 

The operation \sempty\ can be defined as follows:
\begin{tabbing}
\= \sempty($T$, $x$)\\
\> 1. \myif\ $\exmax(S) = \Nil$, then \ret\ \mytrue\\
\> 2. \myelse\  \= \ret\ \myfalse.
\end{tabbing}
\end{itemize}

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

\begin{itemize}
\item[{\bf (a)}] 
A $d$-ary heap can be represented by an array as follows: Let $A[1]$ be the
root.  For each $i$ and $1 \le j \le d$, the $j$th child of $A[i]$ is given by
$A[(i-1)d + j + 1]$.  We can prove the correctness by induction on $i$.  For
the base case, we take $i = 1$.  Clearly, the $d$ children of $A[1]$ are
$A[2]$ through $A[d + 1]$, thus establishing the base case.  For the induction
step, all we need to check is that the $d$ children of $A[i]$ come immediately
following the $d$ children of $A[i-1]$, which is true according to our formula.

The parent of $A[i]$ is given by $A[\lceil (i-1)/d \rceil]$; this directly
follows from the fact that if $A[k]$ is the parent of $A[i]$, then $i$ is of
the form $(k-1)d + j + 1$, implying that $\lceil (i - 1)/d \rceil = k$.

\item[{\bf (b)}]
The number of nodes at level $1$ is $1$, at level $2$ is $d$, at level $3$ is
$d^2$, and in general, at level $i$ is $d^{i-1}$, except the last level $h$,
where it may be between $1$ and $d^{h-1}$.  We thus have:
\begin{eqnarray*}
1 + d + d^2 + \ldots + d^{h-2} \le & n & \le 1 + d + d^2 + \ldots + d^{h-1}\\
\frac{d^{h-1} - 1}{d-1}  \le & n & \le  \frac{d^{h} - 1}{d - 1}\\
d^{h-1} - 1 \le & n(d - 1) & \le d^h - 1.
\end{eqnarray*}
It thus follows that $\log_d(nd - d + 1) \le h \le \log_d(nd - d + 1) + 1$,
which implies that $h = \Theta(\log_d n) = \Theta(\lg n/(\lg d))$.

\item[{\bf (c)}] The \exmax\ routine can be the same as the routine described
in text on page 150 for $d = 2$.  The main procedure that needs to be changed
is \heapify.  In the \heapify\ routine, rather than just finding the largest
among a node and its two children, we find the largest among the node and its
$d$ children.  This takes $O(d)$ time.  Therefore, the \heapify\ routine will
take $\Theta(d \log_d{n})$ time.  The running time of \exmax\ will also be
$\Theta(d \log_d{n})$.

\item[{\bf (d)}]
Exactly the same algorithm as the one given on page~150 will work since we
only traverse the parent pointers.  Note that the parent pointer has been
defined according to part~(a).  The running time of \ins\ is $\Theta(h) =
\Theta(\log_d n)$. 

\item[{\bf (e)}]
When we increase any key $A[i]$, then the heap property is preserved in the
subtree rooted at $A[i]$.  However, the heap property may be violated between
$A[i]$ and its parent.  We can use a procedure similar to \ins\ in which we
move the tree and reestablish the heap property as we go on.  

If $A[i] \ge k$, then we do nothing.  Otherwise, we set $A[i] = k$, and then
execute lines~3 to~6 of {\sc Heap-Insert} given on page 150 of text.
\end{itemize}


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

\begin{itemize}
\item[{\bf (a)}] To prove that \SS($A, i, j$) sorts correctly, we use
  induction on $\ell = j - i + 1$.  (That is, $\ell$ is the number of
  elements in $A[i.. j]$.)  For the induction basis, we consider two
  cases: $\ell = 1$ or $\ell = 2$, i.e., $i = j$ or $i = j -1$.  For
  each of these cases, in Steps~1 and~2, $A[i]$ and $A[j]$ are
  exchanged if $A[i] > A[j]$.  Also, in both cases the condition in
  Step~3 holds.  Therefore, \SS($A, i, j$) returns after having sorted
  $A$.
  
  For the induction hypothesis, we assume that \SS\ sorts correctly
  for all arrays of length less than $m$, where $m > 2$.  We now show
  that \SS\ sorts correctly for all inputs of length $m$.  Since $m >
  2$, the condition in Step~3 is not true; hence \SS\ does not return
  in Step~4.  Moreover, for the discussion that follows, it does not
  matter whether the exchange of $A[i]$ and $A[j]$ took place in
  Step~2.  So we now consider Steps~5 through~8.  The variable $k$ is
  set to $\lfloor(j - i + 1)/3\rfloor$ in Step~5.  Since $j - i + 1
  \ge 3$, $k \ge 1$; therefore, $j - i - k + 1 = m - k < m$.
  Therefore, the length of the array $A[i.. j- k]$ on which \SS\ is
  called in Step~6 is less than $m$.  By the induction hypothesis, it
  follows that $A[i.. j - k]$ is in sorted order after Step~6.  Hence,
  $A$ has the following property: (P1) for all $x$ in $[i.. i + k -
  1]$ and $y$ in $[i+ k.. j- k]$, $A[x] \le A[y]$.  In particular, we
  see that there are at least $k$ elements in $A[i+k.. j]$ that are
  greater than or equal to every element in $A[i.. i+k-1]$.  Next,
  \SS\ sorts $A[i + k, .., j]$.  Again, the length of the array is
  less than $m$.  So we invoke the induction hypothesis and claim that
  after Step~7, $A[i + k.. j]$ is sorted. Since $A[i+k.. j]$ is
  sorted, $A$ has the following property: (P2) $A[j-k+1.. j]$ is
  sorted correctly, and (P3) for all $x$ in $[i + k.. j - k]$ and $y$
  in $[j - k + 1.. j]$, $A[x] \le A[y]$.
  
  Since the elements in indices $[i.. i+k-1]$ do not move, the
  following property (that follows from~(P1)) still holds: (P4) there
  are at least $k$ elements in $A_7[i+k.. j]$ that are greater than or
  equal to every element in $A[i.. i+k-1]$.  Therefore, combining with
  property~(P3) above, we have: (P5) for all $x$ in $[i.. j - k]$ and
  $y$ in $[j - k + 1.. j]$, $A[x] \le A[y]$.  Thus, after step~6,
  properties~(P2) and~(P5) hold.

Finally, we apply \SS\ on $A[i.. j -k]$.  Again the length of the array, $j -
k - i + 1$ is less than $m$.  So applying the induction hypothesis, we obtain
that $A[i.. j - k]$ is sorted correctly.  Moreover, since the indices
$[j-k+1.. j]$ are unaffected, properties~(P2) and~(P5) still hold.  We thus
obtain that the entire array $A[i.. j]$ is sorted correctly.

\item[{\bf (b)}] Let $T(n)$ be the running time of \SS\ on an array of
  length $n$.  Steps~1 through~5 take $\Theta(1)$ time.  Steps~6
  through~8 each take $T(n - \lfloor n/3 \rfloor)$ time.  If we ignore
  the floor, then we obtain that steps~6 through~8 each take $T(2n/3)$
  time.  We thus have the following recurrence:

\[ T(n) = 3T(\frac{2n}{3}) + \Theta(1),\]

which can be solved by the Master method as follows.  Here $a$ is $3$,
$b$ is $3/2 = 1.5$, and $f(n)$ is $\Theta(1)$.  This falls under
case~1.  Therefore, we obtain $T(n) = \Theta(n^{\log_{1.5} 3})$.

We now prove the same result using substitution and taking the floor
into account.  Steps~6 through~8 each take $T(n - k)$ time.  Since $k
= \lfloor n/3 \rfloor$, $2n/3 \le n - k \le 2n/3 + 1$.  We show by the
substitution method that $T(n) = \Theta(n^{\log_{3/2} 3})$.  We will
show that there exist constants $c$, $c_1$, $c_2$, and $n_0$ such that
$cn^{\log_{3/2} 3} \le T(n) \le c_1 n^{\log_{3/2} 3} - c_2 n^2$ for
all $n \ge n_0$.  Since $\log_{3/2} 3 > 2$, this yields the desired
tight bound.  We first establish the induction step for the upper
bound.  For $n \ge 3$, we have:
\begin{eqnarray*}
T(n) & \le & 3(c_1(2n/3 + 1)^{\log_{3/2} 3} - c_2(2n/3 + 1)^2) + O(1)\\
     & \le & 3c_1((2n/3)^{\log_{3/2} 3} + c_3 n^2) - 3c_2(2n/3 + 1)^2 + O(1)\\
     & \le & c_1n^{\log_{3/2} 3} + 3c_1c_3 n^2 - 4c_2 n^2/3 + O(n)\\
     & \le & c_1n^{\log_{3/2} 3} - c_2 n^2 - (c_2n^2/3 - 3c_1c_3n^2 - O(n))\\
     & \le & c_1n^{\log_{3/2} 3} - c_2 n^2.
\end{eqnarray*}
(In the second step, $c_3$ is a constant that is obtained when we
consider the non-leading terms in the binomial expansion of $(2n/3 +
1)^{\log_{3/2} 3}$.  The last step holds since we can choose $c_2/c_1$
sufficiently large such that $(c_2/c_1) \ge 3c_3 + O(1)$ .)  For the
lower bound, we have:
\begin{eqnarray*}
T(n) & \ge & 3c(2n/3 + 1)^{\log_{3/2} 3}\\
     & = &  cn^{\log_{3/2} 3}.
\end{eqnarray*}
Finally, we note that we can select $n_0$ and $c_1$ sufficiently large and $c$
sufficiently small such that that $cn^{\log_{3/2} 3} \le T(n_0) \le c_1
n^{\log_{3/2} 3} - c_2 n^2$.

\item[{\bf (c)}] Since $T(n) = \Theta(n^{\log_{3/2} 3}) =
  \omega(n^2)$, \SS\ is worse than each of insertion sort, merge sort,
  heapsort, and quicksort.
\end{itemize}


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

{\bf Answer:} Strassen used the idea that if we can multiply two $2
\times 2$ matrices using $7$ multiplications, then we can reduce the
problem of multiplying two $n \times n$ matrices to $7$
multiplications of $n/2 \times n/2$ matrices plus $O(n^2)$ time for
additions.  Similarly, we can multiply two $n \times n$ matrices by
partitioning each matrix into $k^2$ $n/k\times n/k$ matrices and then
recursing using the given method of multiplying two $k \times k$
matrices.  The given method employs $m$ multiplications.  Thus our
recursive procedure for multiplying two $n \times n$ matrices will
involve $m$ $n/k \times n/k$ multiplications and $\Theta(n^2)$ time
for additions.  (Note that we are ignoring floors and ceilings.) We
thus obtain the following recurrence:

\[ T(n) = m T(\frac{n}{k}) + \Theta(n^2), \]

which can be solved using case~1 of the master theorem to yield $T(n)
= \Theta(n^{\log_k m})$, if $m > k^2$.

We now apply the above analysis to V.\ Pan's methods.  Two $n \times
n$ matrices can be multiplied by $132464$ multiplications of $n/68
\times n/68$ matrices plus $O(n^2)$ time for additions.  This gives us
the following recurrence:
\[ T(n) = 132464 T(n/68) + O(n^2).\]
Similarly, if we use V.\ Pan's method for multiplying $70 \times 70$ matrices
and $72 \times 72$ matrices , we get the following recurrences, respectively:
\begin{eqnarray*}
T(n) = 143640 T(n/70) + O(n^2)\\
T(n) = 155424 T(n/72) + O(n^2)
\end{eqnarray*}
Each of the three recurrences can be solved by invoking Case~1 of the master
theorem.  We obtain the following solutions: 
\begin{eqnarray*}
T(n) = \Theta(n^{\log_{68} 132464}) \approx \Theta(n^{2.7951285})\\
T(n) = \Theta(n^{\log_{70} 143640}) \approx \Theta(n^{2.7951227})\\
T(n) = \Theta(n^{\log_{72} 155424}) \approx \Theta(n^{2.7951474})
\end{eqnarray*}
Since Strassen's algorithm takes $T(n) = \Theta(n^{\lg 7}) \approx
\Theta(n^{2.807})$ time, each of V.\ Pan's algorithms is asymptotically better
than Strassen's.  The best V.\ Pan algorithm is the one that uses $70 \times
70$ matrices.

\end{document}
