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

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

\title{6.854 Problem Set 3}

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

%\maketitle

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

\pagebreak

\section*{Problem 1}
\markright{Nada Amin (6.854 Problem 3-1) (09/26/07)} 

I discuss how the runtimes of the operations $\proc{Insert}$,
$\proc{Decrease-Key}$, $\proc{Delete-Min}$ changes in an
implementation of multi-level-bucket heaps where I keep the set of a
block's nonempty buckets in a standard binary heap instead of
maintaining it in an array.

Let $k$ be the depth of the tree and $\Delta$ the branching factor,
such that $\Delta^k = C$.

\begin{description}
\item[$\proc{Insert}$] took $O(k)$ time in the array
implementation. In the binary heap implementation, it takes $O(k)$
time to find the right binary heap and $O(\log \Delta)$ to insert into
it, so the total running time is $O(k + \log \Delta)$.
\item[$\proc{Decrease-Key}$] took $O(k)$ time in the array
implementation. In the binary heap implementation, it takes $O(k +
\log \Delta)$ time: it takes $O(\log \Delta)$ to delete the item from
the binary heap where it used to be (simply decrease its key to
$-\infty$ and delete it as the min), then, like for the $\proc{Insert}$
operation, it takes $O(k)$ to find the new binary heap for the item
and $O(\log \Delta)$ to insert into it.
\item[$\proc{Delete-min}$] took $O(k\Delta)$ time in the array
implementation (plus an overall $O(n\Delta)$). In the binary heap
implementation, it takes $O(\log \Delta)$ time to delete the min
thanks to the cheap $\proc{Delete-Min}$ operation of the binary
heap. However, if the heap becomes empty, the change might need to get
cascaded to the top, which costs at most $O(k)$ in additional
time. Therefore, in the binary heap implementation, the total running
time might reach $O(k + \log \Delta)$.

\end{description}

To balance the running time of $O(k + \log \Delta)$ of the operations
in the binary heap implementation, I pick $k = \log \Delta$. Recalling
that $\Delta^k = C$ or $\log \Delta = (\log C)/k$, I get $k =
\sqrt{\log C}$. Thus, by setting $k = \log \Delta$, I get a runtime of
$O(\sqrt{\log C})$ for each $\proc{Insert}$, $\proc{Decrease-Key}$ and
$\proc{Delete-Min}$.

Since Dijkstra's shortest path algorithm makes $m$ calls to
$\proc{Decerease-Key}$, $n$ calls to $\proc{Insert}$ and $n$ calls to
$\proc{Delete-Min}$, its running time using this binary heap
implementation of multi-level-bucket heaps is $O((m+n)\sqrt{\log C})$.

\pagebreak

\section*{Problem 2}
\markright{Nada Amin (6.854 Problem 3-2) (09/26/07)}

I show that for the single-source shortest paths problem on a graph
with $n$ nodes and range of edge lengths $\{1,2,\ldots,C\}$, I can
obtain $O(\log\log C)$ time per queue operation.

Even though the range of values is $\{1,2,\ldots,nC\}$, the trick is
to notice that, in Dijkstra's algorithm, only values between $x$ and
$x+C$ are active at once. Indeed, if $x$ is the minimum, I will
only add values as great at $x+C$ when I process $x$, as $C$ is the
max value of an edge. So before processing $x$, by a similar argument,
I must have only added values $\leq x+C$. Then, after processing $x$,
the range of values remain in an interval $\leq C$. In addition,
$\proc{decrease-key}$ will only reduce values within the active range.

I maintain two van Emde Boas priority queues, $Q_1$ and $Q_2$ which
only stores values modulo $C$. Each queue has an extra field
indicating the quotient of the ``actual'' values stored modulo $C$ in
the queue. I start with $Q_1$ and $Q_2$ empty, representing the
quotients 0 and 1, respectively. When $Q_1$ becomes empty, I increase
its quotient by $2$, and switch $Q_1$ and $Q_2$. By the trick
explained in the previous paragraph, I guarantee that the active range
of values can fit in $Q_1$ and $Q_2$ at any time. 

When inserting an element, I put it in the queue corresponding to its
quotient with its value modulo $C$. When decreasing the key of an
element, I either just decrease its key directly in the queue in which
it is (if the quotient doesn't change) or (if its quotient decreases)
I delete it from $Q_2$ (necessarily) and insert it in $Q_1$ with the
new key value modulo $C$. Deleting the min is as simple as deleting
the min of $Q_1$ (and switching the queues as explained in the
previous paragraph if $Q_1$ becomes empty).

Since they only have values in the range $\{0,\ldots,C-1\}$, my two
van Emde Boas priority queues perform each queue operation in $O(\log
\log C)$ time. Thus, I achieve the bound of $O(\log \log C)$ per queue
operation.

\pagebreak

\section*{Problem 3}
\markright{Nada Amin (6.854 Problem 3-3) (09/26/07)} 

I augment the van Emde Boas priority queue presented in class (which
performed the insert and successor queries) to support the following
operations on integers in the range $\{0,1,2,\ldots,u-1\}$ in $O(\log
\log u)$ worse-case time each and $O(u)$ space total:
\begin{description}
\item[$\proc{Find}(x,Q)$:] Report whether the element $x$ is stored in the structure.

\begin{codebox}
\Procname{$\proc{Find}(x,Q)$}
\li \If $x < Q.\text{min}$ or $x > Q.\text{max}$
\li \Then \Return False \End
\li \If $x = Q.\text{min}$ or $x = Q.\text{max}$
\li \Then \Return True \End
\li \Return $\proc{Find}(\text{low}(x), Q[\text{high}(x)])$
\end{codebox}

\item[$\proc{Predecessor}(x,Q)$:] Return $x$'s predecessor, the
element of largest value less than $x$, or null if $x$ is the minimum
element.

\begin{codebox}
\Procname{$\proc{Predecessor}(x,Q)$}
\li \If $x \leq Q.\text{min}$ 
\li \Then \Return null \End
\li \Comment $x$ is at position $\text{low}(x)$ in $Q[\text{high}(x)]$
\li \If $\text{low}(x) > Q[\text{high}(x)].\text{min}$
\li \Then \Return $\text{high}(x).\sqrt{|Q|} + \proc{Predecessor}(\text{low}(x),Q[\text{high}(x)])$
\li \Else \Comment $\text{low}(x) = Q[\text{high}(x)].\text{min}$
\li $i \gets \proc{Predecessor}(\text{high}(x),Q.\text{summary})$
\li \If $i$ is not null
\li \Then \Return $i.\sqrt{|Q|} + Q[i].\text{max}$
\li \Else \Return $Q.\text{min}$\End
\end{codebox}

\item[$\proc{Delete}(x,Q)$:] Delete $x$ from the queue while
preserving the structure of the priority queue.

\begin{codebox}
\Procname{$\proc{Delete}(x,Q)$}
\li \If $Q.\text{min}$ is null or $x < Q.\text{min}$:
\li \Then \Return \End
\li \If $Q.\text{min} = x$
\li \Then $i \gets Q.\text{summary}.\text{min}$
\li       \If $i$ is null
\li       \Then $Q.\text{min} \gets$ null
\li             $Q.\text{max} \gets$ null
\li             \Return
\li       \Else $x \gets i.\sqrt{|Q|} + Q[i].\text{min}$ \Comment overwriting $x$
\li             $Q.\text{min} \gets x$ \End 
\li \End
\li $\proc{Delete}(\text{low}(x), Q[\text{high}(x)])$
\li \If $Q[\text{high}(x)].\text{min}$ is null
\li \Then $\proc{Delete}(\text{high}(x), Q.\text{summary})$ \End
\li \Comment Update the $\text{max}$ if necessary
\li \If $Q.\text{max} = x$
\li \Then \If $Q[\text{high}(x)].\text{max}$ is null
\li       \Then $i \gets Q.\text{summary}.\text{max}$
\li       \Else $i \gets \text{high}(x)$ \End
\li       \If $i$ is null
\li       \Then $Q.\text{max} \gets$ null
\li       \Else $Q.\text{max} \gets i.\sqrt{|Q|} + Q[i].\text{max}$ \End
\li \End
\end{codebox}

\end{description}

\subsection*{Analysis}
$\proc{Find}$, $\proc{Predecessor}$ and $\proc{Delete}$ do at most $1$
costly recursive call of size $\sqrt{u}$. $\proc{Delete}$ might do two
recursive calls, but, when it does, the first call is cheap: it takes
$\Theta(1)$ time as it simply nulls the minimum (and unique) element of
$Q[\text{high}(x)]$. Therefore, the running time of each operation is
$T(u) = T(\sqrt{u}) + \Theta(1) = O(\log \log u)$. The total space
remains $O(u)$ with these added operations as they don't change the
structure in any way.

\pagebreak

\section*{Problem 4}
\markright{Nada Amin (6.854 Problem 3-4) (09/26/07)}
% Done on paper.

\pagebreak

\

\pagebreak

\

\pagebreak

\section*{Problem 5}
\markright{Nada Amin (6.854 Problem 3-5) (09/26/07)} 

I suppose I have already computed the maximum flow in a network with
$m$ edges and integral capacities using an augmenting-paths algorithm.

\subsection*{Part (a)}
I show how to update the maximum flow in $O(m)$ time after increasing
a specified capacity by $1$.

I construct the residual graph of the old maximum flow and find an
augmenting path. Since only a specified capacity was increased by $1$,
if there is an augmenting path, it must involve this increased
capacity (as the flow used to be maximum) and once the augmentation is
performed, there cannot be any other augmenting paths (as the
increased capacity must now be completely used).

The residual graph takes $O(m)$ time to construct. Using a Breath
First Search, I can find the augmenting path in $O(m)$ time. Since the
path has $\leq n$ edges (as each node can only appear once), the
augmentation can be done in $O(n)$ time. Therefore, the running time
of the update is $O(m)$.

\subsection*{Part (b)}
I show how to update the maximum flow in $O(m)$ time after decreasing
a specified (positive) capacity by $1$.

If the old maximum flow did not saturate the decreased capacity, then
it can be decreased by $1$ without affecting the maximum flow.

Otherwise, I choose a flow path of value $1$ that uses this capacity,
and substract it from the old maximum flow. This modified flow has a
value decreased by $1$ compared to the old maximum flow. I construct
the residual graph of this modified flow and find an augmenting
path. If there is an augmenting path, once the augmentation is
performed, there cannot be any other augmenting paths because
otherwise the new maximum flow would have a greater value than the old
maximum flow, a contradiction since the network is more constrained.

Using a Breath First Search, I can find a flow path of value $1$ and
substract it in $O(m)$. Like in part (a), finding an augmenting path
using a Breath First Search takes $O(m)$ and the augmentation takes
$O(n)$. Therefore, the running time of the update is $O(m)$.

\pagebreak

\section*{Problem 6}
\markright{Nada Amin (6.854 Problem 3-6) (09/26/07)}

\subsection*{Part (a)}
Supposing all people are initially in a single room $s$, and that the
building has a single exit $t$, I show how to use maximum flow to find
a fastest way to get everyone out of the building.

For time $i$, I construct an auxiliary graph $G_i'$ as explained
below. The value of maximum flow of $G_i'$ from $s_0$ to $t_i$ tells
me how many people I can get out of the building in time $i$. So I try
time $i=1$, $i=2$, $\ldots$ until I reach a time $i_\text{min}$ where the
value of the maximum flow is greater than the number of people
initially in $s$. The maximum flow in the graph $G_{i_\text{min}}'$ tells the
fastest way to get everyone out of the building.

The auxiliary graph $G_i'$ for time $i$ is constructed as follow.
\begin{itemize}
\item For each vertex $v$ in $G$, add vertices $v_0, \ldots, v_i$ in
$G_i'$ and edges $v_0 \rightarrow v_1, \ldots, v_{i-1} \rightarrow
v_i$ with capacity $\infty$.
\item For each edge $(v,w)$ with capacity $c$ in $G$, add edges $v_0
\rightarrow w_1, \ldots, v_{i-1} \rightarrow w_i$ with capacity $c$ in
$G_i'$.
\end{itemize}

\subsection*{Part (b)}
I show that the same technique can be used when people are initially
in multiple locations and there are multiple exists.

I construct the auxiliary graph $G_i'$ for time $i$ as before, except
that I add a super-source $s$ and a super-sink $t$ in $G_i'$. For each
location $v$ in which $x$ people are initially, I add an edge $s
\rightarrow v_0$ with capacity $x$. For each exit $v$, I add an edge
$v_i \rightarrow t$ with capacity $\infty$. Now, when I look for the
maximum flow in $G_i'$, the source is $s$ and the sink $t$.

\subsection*{Part (c)}
I generalize the approach to where different corridors have different
(integral) transit times. 

When I construct the auxiliary graph $G_i'$,
I take edges of $G$ into account as follows:
\begin{itemize}
\item For each edge $(v,w)$ with capacity $c$ in $G$ and transit time $k$, add edges $v_a \rightarrow w_{a+k}$ with capacity $c$, $\forall a$ such that $0 \leq a \leq i-k$.
\end{itemize}

\end{document}
