\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}

\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in} \setlength{\headsep}{0.0in}
%\setlength{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}


\newcommand{\floor}[1]{\ensuremath{\lfloor\, #1\,\rfloor}}


\begin{document}



\title{Data Structures - Assignment no. 5, April 11, 2007}

\date{}

\maketitle


\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }

\vspace{-1.5cm}

 {\small {\bf Remarks:
\begin{itemize}
\item Write both your name and your ID number very clearly on the
top of the exercise. Write your exercises in pen, or in clearly
visible pencil. Please write \emph{very} clearly.

\item Recall that 80\% of the theoretical exercises must be submitted. The
exercises can and must be worked on and submitted alone.

    \item  Give correctness and
        complexity proofs for every algorithm you write.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}


\begin{enumerate}

\item Insert the keys 5, then 9 and then 2 to the heap depicted in Figure \ref{fig:heap}. Then perform delete-min four
times. Now draw the resulting heap.

\item  Show how to modify a 2-4+ search tree, in order to get a data 
structure that supports the operations \emph{delete-min} and \emph{insert} 
in $O(\log n)$ time, and \emph{find-min} in $O(1)$ time. What are the 
disadvantages of such an implementation of a heap, compared to the 
standard implementation?

\item Describe an algorithm that is given two heaps, both of size $n$,
and returns a heap that contains all elements of both heaps.
(Assume that no key appears more than once in the input). Try to
make the algorithm as asymptotically efficient as possible. (Hint: the 
solution is very easy, and can be described in one or two lines).

\item Describe an algorithm that prints the $k$ smallest elements in a 
Heap. You can assume that the heap is represented as an array or as a 
tree, whichever is more comfortable for you.  As usual, you may also 
assume that no key appears more than once in the heap. The algorithm 
should take $O(k \log k)$ time. The algortihm should not modify the heap. 
Give: (i) pseudo-code; (ii) an explanation of the algorithm; (iii) an 
explanation why it is correct; and (iv) an explanation why the running 
time is indeed $O(k \log k)$.\\ \underline{Note:} Observe that getting an 
algorithm that runs in time $O(k \log n)$, where $n$ is the size of the 
heap, is easy -- just perform $k$ delete-mins. (In order to avoid 
modifying the heap, you need to undo your actions, which takes another 
$O(k \log n)$ time).

\item Describe an algorithm that solves the following problem.
You are given $k$ sorted lists $A_1,\ldots,A_k$, each of length
$n$. The output should be one sorted list which contains the keys
of all input lists. The algorithm should take $O(nk \log k)$ time.
You may assume that no key appears more than once in the input.
Give: (i) an explanation of the algorithm; (ii) an explanation why
it is correct; and (iii) an explanation why the
running time is indeed $O(nk \log k)$.\\
\underline{Hint:} The merge procedure that is used as a subroutine
in \emph{merge-sort} (which you learned in the course ``extended
introduction to CS'') answers this question for $k=2$ in time
$O(n)$.

\item Consider an implementation of Fibonacci heaps without cascading cuts 
(all other details are as shown in class, the only difference is that 
delete and decrease-key just cut the subtree and do not continue with 
cascading cuts). For any large enough $m$ show a sequence of $m$ 
operations on heaps of size at most $n$ such that the average cost of an 
operation is as high as possible. (By $m$ large enough we mean larger even 
than some function of $n$.)


\end{enumerate}

\begin{figure}[h]

\vspace{-0.6cm}

\begin{center}
\scalebox{0.35}{\includegraphics{heap.eps}} \caption{A Heap.
\label{fig:heap}}
\end{center}
\end{figure}


\end{document}


