\documentclass{article}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{clrscode}

\author{Nada Amin\\
\texttt{namin@mit.edu}
}
\date{September 12, 2007}

\title{6.854 Problem Set 1}

\begin{document}
\pagestyle{myheadings}
\markright{Nada Amin (6.854 Problem Set 1) (09/12/07)}

\maketitle

\section*{Collaborators}
\begin{itemize}
\item Thomas Belulovich (\texttt{thobel@mit.edu})
\item Thomas Mildorf (\texttt{tmildorf@mit.edu})
\end{itemize}

\section*{Problem 1}

For each $n$, I exhibit a sequence of Fibonacci heap operations on $n$
items that produce a heap ordered tree of depth $\geq n - 3 =
\Omega(n)$.

For $n \leq 3$, the solution is trivial as the required lower-bound on
the depth is $\leq 0$.

For $n \geq 4$, below is a sequence of operations on $n$ items with
keys from $1$ to $n$ (each item will be noted by its key) that produce
a heap-ordered tree of depth $n-3$, specifically either the tree $3
\rightarrow 4$ if $n=4$ or, if $n>4$, the tree $2 \rightarrow \ldots
\rightarrow n-3 \rightarrow n-1 \rightarrow n$, i.e. the tree with
item $2$ as a root and with each greater item except item $n-2$
present as the only child of the previous smaller item present.

\begin{codebox}
\Procname{$\proc{Make-Tree}(n)$}
\li $\proc{insert}(n)$
\li $\proc{insert}(n-1)$
\li $\proc{insert}(n-2)$
\li $\proc{delete-min}()$
\li \For $k \gets 4$ \To $n-1$
\li      \Do $\proc{insert}(n-2)$
\li          $\proc{insert}(n-k+1)$
\li          $\proc{insert}(n-k)$
\li          $\proc{delete-min}()$
\li          \Comment to $\proc{delete}(n-2)$:
\li          $\proc{decrease-key}(n-2, -\infty)$
\li          $\proc{delete-min}()$ \End
\end{codebox}

\section*{Problem 2}

I show that modifying Fibonacci heaps so that a node is cut only after
losing $k$ children improves the amortized cost of
$\proc{decrease-key}$ (to a better constant) at the cost of a worse
cost for $\proc{delete-min}$ (by a constant factor).

\subsection*{$\proc{decrease-key}$}

I analyze the amortized cost of $\proc{decrease-key}$, when a node is
cut only afer losing $k$ children (i.e. having $k$ marks). I choose
the potential function:

   $$\Phi = \frac{2}{k-1} \text{(number of marks)} + \text{(number of roots)}$$

so that the cost of a cascading cut is $0$: 

\ \\
\begin{tabular}{lrl}
   & $1$              & (for cutting the node)                     \\
$+$& $1$              & (for adding a root)                        \\
$-$& $(k-1) 2 / (k-1)$& (for removing the $k-1$ marks on this node)\\
\hline
\hline
   & $0$              & (total)                                    \\
\end{tabular}

\ \\

Hence, the amortized cost of decrease-key is $2+2/(k-1)$: 

\ \\
\begin{tabular}{lrl}
   & $1$              & (for cutting the node)                     \\
$+$& $1$              & (for adding a root)                        \\
$+$& $2/(k-1)$        & (for adding a mark)                        \\
$+$& $0$              & (for cascading cuts)                       \\
\hline
\hline
   & $2+2/(k-1)$      & (total)                                    \\
\end{tabular}

\ \\

As $k>2$, the constant cost of $\proc{decrease-key}$ decreases.

\subsection*{$\proc{delete-min}$}

For $\proc{delete-min}$, I show that the trees are exponential in degree, so
that adding the children of the min as roots result in $O(\log(n))$ new
roots.

By the union-by-rank procedure, the $i^\text{th}$ added child will have degree
$\geq i-k$. Indeed, by virtue of being the $i^\text{th}$ child added,
it must have been in the $(i-1)^\text{th}$ bucket, so it must have
started with $i-1$ children. Since it losts at most $k-1$ children,
it still has at least $i-k$ children. Now, let
 $$S_k = \text{the number of descendants of a tree with $k$ children}$$
\begin{align*}
 S_0 =& 1\\
 S_1 =& 2\\
 S_n \geq& \sum_{i=0}^{n-k} S_i\\
 S_n \geq& S_{n-1} + S_{n-k}\\
 S_n =& \Omega(C^k)\\
\end{align*}

Hence, $\proc{delete-min}$ will add $O(\log_C(n))$ roots. When $k=2$,
$C=\Phi$ (the golden number). Clearly, for $k>2$, $C<\Phi$, so
$\log_C(n) < \log_\Phi(n)$.  Therefore, as $k>2$, the performance of
$\proc{delete-min}$ will be worse by a constant factor (precisely
$\log_C(\Phi)$).

\section*{Problem 3}

\subsection*{Part (a)}

I show how to use a priority queue $P$ that performs $\proc{insert}$,
$\proc{delete-min}$ and $\proc{merge}$ in $O(\log(n))$ time and
$\proc{make-heap}$ in $O(n)$ time to construct a priority queue $Q$ that
performs $\proc{insert}$ in $O(1)$ amortized time while still performing
$\proc{delete-min}$ and $\proc{merge}$ in $O(\log(n))$ amortized time.

For my new priority queue $Q$, I maintain two structures, a list $m$
and the priority queue $p$. On $\proc{insert}$, I simply add the new
element to the list $m$. On $\proc{delete-min}$ and $\proc{merge}$, I
make a priority queue out of the list $m$ and merge it with the
priority queue $p$, before calling the $\proc{delete-min}$ or
$\proc{merge}$ procedure of $p$.

\begin{codebox}
\Procname{$\proc{Q:make-heap}(l)$}
\li $m \gets ()$
\li $p \gets \proc{P:make-heap}(l)$
\end{codebox}

\begin{codebox}
\Procname{$\proc{Q:insert}(i)$}
\li $m.\proc{add}(i)$
\end{codebox}

\begin{codebox}
\Procname{$\proc{Q:delete-min}(i)$}
\li $p2 \gets \proc{P:make-heap}(m)$
\li $m \gets ()$
\li $p.\proc{merge}(p2)$
\li \Return $p.\proc{delete-min}()$
\end{codebox}

\begin{codebox}
\Procname{$\proc{Q:merge}(p2)$}
\li $p3 \gets \proc{P:make-heap}(m)$
\li $m \gets ()$
\li $p.\proc{merge}(p3)$
\li $p.\proc{merge}(p2)$
\end{codebox}

\subsubsection*{Amortized Analysis}

Let $\Phi(Q) =$ number of elements in the list $m$. Then:

The amortized cost of $\proc{insert}$ is $O(1)$:

\ \\
\begin{tabular}{rl}
real cost     :&  $1$\\
$\Delta\Phi$  :&  $1$\\
\hline
\hline
amortized cost:&  $2$
\end{tabular}

\ \\

The amortized cost of $\proc{delete-min}$ is $O(\log(n))$:

\ \\
\begin{tabular}{rl}
real cost     :& $\Phi + O(\log(n))$\\
$\Delta\Phi$  :& $-\Phi$\\
\hline
\hline
amortized cost:& $O(\log(n))$
\end{tabular}

\ \\

Similarly, the amortized cost of $\proc{merge}$ is $O(\log(n))$.

\subsection*{Part (b)}

I show how even binary heaps can be modified to support $\proc{insert}$ in
$O(1)$ amortized time while maintaining an $O(\log(n))$ time bound for
$\proc{delete-min}$.

As in part (a), on $\proc{insert}$, I add the new element to a list $m$,
which I make into a binary heap during $\proc{delete-min}$. However, instead of
merging, I add the new heap in a heap of heaps, a ``super'' heap.

Therefore, for my new priority queue $Q$, I maintain two structures: a
list $m$ and a heap of heaps $s$. The super-heap is keyed by the
smallest element in each inner heap. On $\proc{delete-min}$, I make a
new inner heap out of the list $m$ and add it to the super-heap. I
find the min inner heap in the super-heap, perform $\proc{delete-min}$
on the min inner heap, and then $\proc{min-heapify}$ the super-heap to
maintain the (super-)heap order (or delete the inner heap from the
super-heap if it's empty).

\begin{codebox}
\Procname{$\proc{Q:make-heap}(l)$}
\li $m \gets ()$
\li $s \gets \proc{P:make-heap}(\proc{P:make-heap}(l))$
\end{codebox}

\begin{codebox}
\Procname{$\proc{Q:insert}(i)$}
\li $m.\proc{add}(i)$
\end{codebox}

\begin{codebox}
\Procname{$\proc{Q:delete-min}(i)$}
\li $s.\proc{insert}(\proc{P:make-heap}(m))$
\li $m \gets ()$
\li $h \gets s.\proc{min}()$
\li $x \gets h.\proc{delete-min}()$
\li \If $h.\proc{empty}()$
\li \Then $s.\proc{delete}(h)$
\li \Else $s.\proc{min-heapify}()$ \End
\li \Return $x$
\end{codebox}

\subsubsection*{Amortized Analysis}

The amortized analysis in similar to part (a). In $\proc{delete-min}$,
deleting the min from the min inner heap and maintaining the heap
order of the super-heap each takes $O(\log(n)$. Indeed, an inner heap
has at most $n$ elements while the super-heap has at most $n$ inner
heaps (with $1$ element each). Therefore, as in part (a), the
amortized cost of $\proc{delete-min}$ is $O(\log(n))$:

\ \\
\begin{tabular}{rl}
real cost     :& $\Phi + O(\log(n))$\\
$\Delta\Phi$  :& $-\Phi$\\
\hline
\hline
amortized cost:& $O(\log(n))$
\end{tabular}

\ \\

\subsection*{Problem 4}
I show how to use the techniques of persistent data structures to
preprocess a tree in $O(n\log(n))$ time so as to allow LCA queries to
be answered in $O(\log(n))$ time.

The time axis consists of the nodes of the tree in postorder. For each
node, I maintain a timestamped pointer to its parent, a pointer to a
binary search tree of timestamped names and an ephemeral rank for the
union-by-rank heuristic.

Initially, at time $t = 0$, each node is isolated, having a null
parent pointer and an empty tree of names and a rank of $0$.

I support $3$ operations:
\begin{description}
\item[$\proc{union-with-name}(a,b)$] increments time, $\proc{union}$ node $a$ with node $b$ and set the name of the representative to $b$.
\item[$\proc{find-at-time}(a,t)$] finds the representative of node $a$ at time $t$.
\item[$\proc{name-at-time}(r,t)$] finds the name associated with the representative $r$ at time~$t$.
\end{description}

\begin{codebox}
\Procname{$\proc{union-with-name}(a,b)$}
\li $t \gets t+1$
\li $r_a \gets \proc{find-at-time}(a,t)$
\li $r_b \gets \proc{find-at-time}(b,t)$
\li \Comment apply the union-by-rank heuristic
\li \If $\text{rank}(r_a) = \text{rank}(r_b)$
\li \Then set parent pointer of $r_b$ to $r_a$ and timestamp it
\li       $r \gets r_a$
\li       $\text{rank}(r_a) \gets \text{rank}(r_a) + 1$
\li \ElseIf $\text{rank}(r_a) < \text{rank}(r_b)$
\li \Then set parent pointer of $r_a$ to $r_b$ and timestamp it
\li       $r \gets r_b$
\li \ElseNoIf \Comment $\text{rank}(r_b) < \text{rank}(r_a)$
\li       set parent pointer of $r_b$ to $r_a$ and timestamp it
\li       $r \gets r_a$ \End
\li add the name $b$ at time $t$ to the binary search tree of names of $r$
\end{codebox}

\begin{codebox}
\Procname{$\proc{find-at-time}(a,t)$}
\li \If $\text{parent}(a)$ is null or $\text{timestamp-parent}(a) > t$
\li \Then \Return $a$
\li \Else \Return $\proc{find-at-time}(\text{parent}(a), t)$
\end{codebox}

\begin{codebox}
\Procname{$\proc{name-at-time}(r,t)$}
\li \Return the name at time $t$ in the binary search tree of names of $r$
\end{codebox}

During pre-processing, I simply call
$\proc{union-with-name}(\text{node},\text{parent})$ for each node in
postorder.

During a query for the pair $(a,b)$, I proceed as follows. Assuming,
without loss of generality that node $a$ occurs before node $b$ in
postorder, I let $t$ be the time just before $b$ was processed. The
query call is then simply
$\proc{name-at-time}(\proc{find-at-time}(a,t),t)$.

\subsubsection*{Analysis}
Thanks to the union-by-rank heuristic, I assure the union-find has
only trees of depth $O(\log(n))$. Therefore, $\proc{find-at-time}$ is
$O(\log(n))$. $\proc{union-with-name}$ is therefore
$O(\log(n)+\log(t))$ and $\proc{name-at-time}$ is $O(\log(t))$. Since
$t \leq n$, all operations are $O(\log(n))$. Therefore pre-processing
is $O(n\log(n))$ and querying is $O(\log(n))$.

\subsection*{Problem 5}
I show that the expected behavior of markless Fibonacci heaps (where,
each time I do a cut, I flip an unbiased coint to decide whether to
cascade the cut to the parent) is like that of the standard
ones. Indeed, the expected number of children cut before a node is
cut, $E_\text{cut}$, is 2:
\begin{align*}
E_\text{cut} &= \frac{1}{2} &+& 2\cdot\frac{1}{4} &+& 3\cdot\frac{1}{8} &+& \ldots\\
             &= (\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \ldots) &
                +& (\frac{1}{4} + \frac{1}{8} + \ldots) &
                +& (\frac{1}{8} + \ldots) &
                +& \ldots\\
             &= 1 &+& \frac{1}{2} &+& \frac{1}{4} &+& \ldots\\
             &= \sum_{i=0}^{\infty} \frac{1}{2^i} &&&&&&\\
             &= 2&&&&&&
\end{align*}

It is possible to bias the coint so that a cascade is more than 50\%
likely to achieve the effect of cascading after (say) one and a half
children are cut. Let $p$ be the probability of cascading a cut,
i.e. the bias of the coin. Then:
\begin{align*}
E_\text{cut} &= p + 2\cdot p^2 + 3p^3 + \ldots\\
             &= \sum_{i=0}^{\infty} p^i\\
             &= \frac{1}{p}
\end{align*}
So in order to have $E_\text{cut} = 1.5 = \frac{3}{2}$, we need a bias
of $p = \frac{2}{3}$.

This can be used to improve the expected amortized time for
$\proc{delete-min}$ at the cost of increasing the expected amortized
time for $\proc{decrease-key}$. The analysis is similar to Problem 2,
with $k=1.5<2$: $\proc{decrease-key}$ is more costly because the
expected number of cascading cuts is higher, $\proc{delete-min}$ is
less costly because the expected exponent in the exponential-in-degree trees is
greater.

\end{document}
