\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. 6, June 6, 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 Please write your exercises in pen, or in clearly visible pencil. Please write \textbf{very} clearly.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}



\begin{enumerate}

%\item \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 Solve the recurrence relation $T(n)=2T(n/2)+n^2$ using the
%recursion-tree method. Then formally prove your solution (you can use
%induction).

\item Manually run the quicksort algorithm on the array
(16,3,89,13,9,45,5,17,4,90,14,10,46,6,30). Assume that at every
step the pivot that is chosen is the median element.

\item In this question we discuss a model called the ``extended
comparison model'', which is like the comparison model, except
that you are allowed 5 types of questions: (i) ``$a=b$?'', (ii)
``$a<b$?'', (iii) ``$a>b$?'', (iv) ``$a<b+100$?'', (v) ``$a>b+100$?''.
Prove a lower bound of $\Omega(n \log n)$ for sorting an array of
size $n$ in the extended comparison model.

\item \begin{enumerate}

\item You are given two arrays, $A$ and $B$, each of size $n$.
Give an algorithm that returns an array $C$ of size $n$, such that
$C[i]$ is equal to the number of elements of $A$ that are less or
equal to $B[i]$. The algorithm should run in time $O(n \log n)$.
Describe the algorithm and explain why the running time is $O(n
\log n)$. You do not have to give pseudo-code.

\item Prove a lower bound of $\Omega(n \log n)$ for this problem
in the comparison model.\\ \underline{Hint:} You can prove this
lower bound directly. However, it is easier to give a reduction.
To do this, you should: (i) Prove that if you can solve this
problem in time $f(n)$ then you can sort an array of size $n$ in
time $O(f(n) + n)$; (ii) Deduce from this that if you can solve
this problem in time $f(n)$ then $f(n)=\Omega(n \log n)$.

\end{enumerate}

\item \begin{enumerate}

\item You are given an array of size $n$, which contains $\log n$
distinct elements, each of them occurring exactly $\frac{n}{\log n}$
times. Give an algorithm that sorts this array in time $O(n \log
\log n)$. Describe the algorithm and explain why the running time is
$O(n \log \log n)$. You do not have to give pseudo-code.

\item Prove a lower bound of $\Omega(n \log \log n)$ in the
comparison model for this problem.\\
\underline{Hint:} Work like the lower bound that you have seen in
class. First prove that there must be at least $(n!) / \left( (n/ \log
n)! \right)^{\log n}$ leaves in the comparison tree. Then use Stirling's
approximation of $n!$ to prove that the depth of the tree is $\Omega(n
\log \log n)$. When using Stirling's approximation, it is
enough to use that:
\begin{equation*}
n! = \Theta \left (\sqrt{n} \left( \frac{n}{e} \right)^n \right)
\end{equation*}
You can use this approximation without proving it.

\end{enumerate}


\end{enumerate}

\end{document}
