\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. 10, May 31, 2006}

\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 Consider the Union-Find data structure that we presented in
class, which uses both the union-by-rank and the path compression
heuristics. Suppose that you are given a sequence of $m$
operations which contains only MAKE-SET, UNION and FIND
operations, and where all UNION operations appear before all FIND
operations.
Show that the total running time of executing all of these operations is $O(m)$.\\
\underline{Remark:} In class we proved a bound of $O(m
\alpha(n))$, but in this question we also have the assumption that
all FIND operations appear after all UNION operations. Also,
recall that in a UNION(a,b) operation we assume that both $a$ and
$b$ are roots.

\item This question is about the analysis of the Union-Find data
structure, as you learned it in the lecture. (This question was
taken from CLRS second edition, chapter 21, problems 21.4-2,3,5,6)

\begin{enumerate}

\item Prove that every node has rank at most $\lfloor \log_2 n
\rfloor$.

\item In light of item (a), how many bits are necessary to store
$rank[x]$ for each node $x$?

\item Professor Dante reasons that because node ranks increase
strictly along a path to the root, node levels must monotonically
increase along the path. In other words, if $rank(x)>0$ and $p[x]$
is not a root, then $level(x) \le level(p[x])$. Is the professor
correct?

\item Consider the function $\alpha'(n)=\min \{k : A_k(1) \ge \log
(n+1)\}$. Show that $\alpha'(n) \le 3$ for all practical values of
$n$ and, using item (a), show how to modify the potential-function
argument to prove that a sequence of $m$ MAKE-SET, UNION and FIND
operations, $n$ of which are MAKE-SET operations, can be performed
on a disjoint-set forest with union-by-rank and path-compression
in worst-case time $O(m \alpha'(n))$.

\end{enumerate}

\item Show how to preprocess an array $A$ of size $n$,
such that the data structure supports the operation SUM($i,j$). This
operation computes $A[i]+A[i+1]+\ldots+A[j-1]+A[j]$. The
preprocessing time should be $O(n)$, the space usage of the data
structure should be $O(n)$, and the query time should be $O(1)$.\\
\underline{Hint:} the solution is really simple! (once you find the
trick). Think about a Prefix-Sum array -- an array $B$ where in
location $k$ the number written is $A[1]+A[2]+\ldots+A[k]$.

\item Give a solution to the Range Minima Problem with space usage
$O(n)$, preprocessing time $O(n)$, and query-time $O(\log n)$.\\
\underline{Reminder:} In the Range Minima Problem you need to
preprocess an array $A$ of size $n$, such that the data structure
supports the operation RM($i,j$). This operation computes
$MIN(A[i],A[i+1],\ldots,A[j])$.

\item Let $s$ be a string of length $n$ and let $T$ be its suffix tree.

\begin{enumerate}

\item What is the maximum possible height of $T$ as a function of
$n$? (give the answer up to a constant). Give an example, you don't
have to prove that it is optimal.

\item What is the minimum possible height of $T$ as a function of
$n$? (give the answer up to a constant). Give an example, you don't
have to prove that it is optimal.

\end{enumerate}

%\item Let $s$ be a string, and suppose that you have constructed its
%suffix tree, and preprocessed the suffix tree to solve Least Common
%Ancestor (LCA) queries. Let $p$ be a string of length $m$, where
%$m<n$. ($s$ is the text, and $p$ is the pattern). In class you have
%learned how to report all $k$ occurrences of the pattern in the text
%in time $O(m+k)$. LEt $1 \le e \le m$ be an integer. Call the
%sub-string of $s$, from location $i$ to $i+m-1$, an $e$-occuirence
%if it matches $p$ except at $e$ locations or less. That is, an
%$e$-occurnece is an occurance with at most $e$ mismatches. Give an
%algorithm that reports all $k$ $e$-occurances of the pattern in the
%text in time $O(me+k)$.\\ \underline{Hint:} Suppose that you have
%found some matches

\item Given two strings $s_1,s_2$, both of length $n$, and given an integer $k$, show an
algorithm that finds the longest string $s$ that appears at least
$k$ times in $s_1$ and at least $k$ times in $s_2$.\\
\underline{Hint:} First think of how to find all of the longest
strings that appear in $s_1$ at least $k$ times.

\end{enumerate}

\end{document}
