\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}

%\documentstyle[11pt]{article}
%\usepackage{fullpage}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\pagestyle{empty} \setlength{\textwidth}{6.5in}
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in} \setlength{\topmargin}{-0.25in}
%\setlength{\textheight}{9.0in}
%\setlength{\baselineskip}{1.3\baselineskip}
%\setlength{\parindent}{0in}
%
%\newcommand\qed{\hspace*{\fill} {\large$\Box$}}
%\newcommand\set[1]{\left\{#1\right\}}
%\newcommand\ang[1]{\left\langle #1 \right\rangle}
%\newcommand\brac[1]{{\left[ {#1} \right]}}
%\newcommand\card[1]{\left| #1 \right|}
%\newcommand\inR{{~\in_{\rm R}~}}


\begin{document}



\title{Data Structures - Assignment no. 7, June 13, 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

\begin{enumerate}

\item Solve the recurrence relation $T(n)=2T(n/2)+n^2$ (you can
use the recursion-tree method).

\item Prove the correctness of the solution you found in $(a)$.
(You can use induction).

\end{enumerate}

\item Describe a data structure that implements a dictionary ADT.
(The dictionary ADT maintains a set of keys, $S$, and supports the
operations $insert(x)$, $delete(x)$ and $find(x)$). Let $n$ be the
number of operations performed on the data structure since it was
created. The data structure should implement insert and delete in
time $O(1)$ worst-case, and find in time $O(n \log n)$ worst case.
Also, the amortized complexity of all operations should be $O(\log
n)$. (In other words, the worst-case time of performing $n$
operations should be $O(n \log n)$). Describe the data structure
(no need to give pseudocode), and prove your claims about the
running time.

\item A \emph{well-ordered heap} is a regular heap, with the
additional property that in each level of the heap the elements,
viewed from left to right, are in increasing order.

\begin{enumerate}

\item Give an algorithm that gets as input $n$ numbers, and
outputs a well-ordered heap that contains these numbers.

\item Prove that the algorithm that you showed is optimal. That
is, give a matching lower bound for the problem. (Hint: you'll
probably want to prove the lower bound by giving a reduction, like
we showed in class and in exercise 6, question $3(b)$).

\end{enumerate}

\item
\begin{enumerate} \item Suppose you are given an array of size $n$ in which no element appears more than once,
and two integers $k_1$ and $k_2$ such that $1 \le k_1 \le k_2 \le
n$. Describe an $O(n)$ time algorithm that returns all of the
elements whose ranks in the array are
$k_1,k_1+1,k_1+2,\ldots,k_2$. Note that you do not have to return
these elements in sorted order. (Note: The \emph{rank} of an
element in an array is the number of elements smaller or equal to
it).

\item (Corrected after giving the exercise in class). Denote $k=k_2-k_1$. 
What running time could you get if we did require that the elements be 
returned in sorted order? Write the best running time you can get as a 
function of both $n$ and $k$.

\end{enumerate}

\item Suppose you are given 3 sorted arrays of size $n$. You may
assume that no element appears in the input more than once.
Describe an algorithm that computes the median of the union of
these arrays in time $O(\log n)$. Prove the correctness of your
algorithm and prove the running-time bound.

\end{enumerate}

\end{document}
