\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\emax}{\mbox{{\sc Extract-Max}}}
\newcommand{\ins}{\mbox{{\sc Insert}}}
\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\ind}{\mbox{{\it in-degree}}}
\newcommand{\Adj}{\mbox{{\it Adj}}}

\head{3390}{Analysis of Algorithms}{Winter 2000}{22 February 2000}{13}

\begin{center}
\Large{\bf Problem Set 3 (due March 7) -- no late homework}
\end{center}

\bigskip 

{\bf 1. (20 points)} Problem 16--1, page 324.

{\bf Answer:} Arrange the points non-decreasing order of $X$
coordinates and, let points $1, 2, \ldots, n$, be the resulting
configuration, where each $i = (x_i, y_i)$.  We then note that
\begin{itemize}
\item A line segment joining points $1$ and $2$ has to exist in any
configuration. Hence the problem is reduced to finding out a path
from $1$ to $2$ passing through all the other points.
\item In general, given path between points $i$ and $i+1$ passing through
all the all points $< i$, we can extend the definition as follows:

\begin{figure}[h]
\begin{center}
\centerline{\epsfxsize=4in \epsffile{problem1.eps}}
\caption{Dynamic programming framework for the problem}
\end{center}
\end{figure}

Let point $j+1$ be the next point that must be connected to $i+1$ in the
optimal bitonic tour. Then we know that all the points $k \ni i+1 < k \le j$
(if exists) 
must be connected in order, forming a sequence of line segments $(i, i+2)$, 
$(i+2, i+3)$, $\ldots$, $(j-1, j)$. Note that in the special case of 
$j = i + 2$, there will be only one additional line segment $(i, j)$. 

The problem is thus reduced to finding out an optimal such $j+1$. We can
thus proceed by finding a new point at minimal cost. Since there
are $n$ possibilities at each possible step, this gives us an $O(n^2)$ 
algorithm.

Let $w(j, k)$ represent the Euclidean distance between points
$j$ and $k$ and 
$C(i, i+1)$ represent the cost of creating a bitonic tour from a point
$i$ to a point $i+1$ passing only through points on the right. The
mathematical formulation is then:
\[C(i, i+1) = \left\{ \begin{array}{ll}
w(i, i+1),\; i+1 = n &\\
Min \{&\\
\hspace*{.3cm} \{C(j, j+1) + w(i+1, j+1) + (w(i, i+2) & \\
\hspace*{.8cm} + w(i+2, i+3) + \ldots + w(j-1, j)), i+3 < j+1 \le n\} & \\
\hspace*{.3cm} \{w(i+1, j+1) + w(i, j) + C(j, j+1), j + 1 = i+3 \le n\} & \\
\hspace*{.3cm} \{w(i+1, j+1) + C(i, j+1), j + 1 = i+2 \le n\}&\\
\},\; otherwise & \\

\end{array}
\right. \]

based on  which an algorithm can easily be devised.
\end{itemize}

{\bf 2. (15 points)} Let the multi-LCS problem be defined as follows.
The input is a set of $m$ length-$n$ sequences $X_i$, $0 \le i < m$.
The output is a longest sequence $Y$ such that $Y$ is a subsequence of
every $X_i$.  Use dynamic programming to develop an algorithm for the
multi-LCS problem that runs in polynomial time for any fixed constant
$m$.

{\bf Answer:} Define $c[i_1, i_2, \ldots, i_m]$ to be the length of
the multi-LCS for the sequences $X_{i_1}, \ldots, X_{i_m}$, where each
$X_k$ is defined as $X_k = X[1 \ldots k]$.  The following recurrence
relation defines $c$:

\[ c[i_1, i_2, \ldots, i_m]  = \left\{ \begin{array}{ll} 0 & \mbox{$i_k =0 for any 1 \le k \le m$}\\
 c[i_1 - 1, \ldots, i_m - 1]+ 1 & \mbox{ $i_k > 0 for all 1 \le k \le m$}\\
& \mbox{\& $X[i_1] = \ldots = X[i_m]$}\\
 Max \{c[i_1 -1, i_2, \ldots, i_m], &\mbox{}\\
c[i_1, i_2 - 1, i_3, \ldots, i_m],& \mbox{}\\
\ldots, c[i_1, i_2, \ldots, i_{m-1} i_m - 1]\} & \mbox{ otherwise}
\end{array}
\right. \]

Using this relation, the problem can be solved using an algorithm
similar to LCS-Length on page 317, CLR.

{\bf 3. (20 points)} Suppose you are a high-level manager in a
software firm and you are managing $n$ software projects.  You are
asked to assign $m$ of the programmers in your firm among these $n$
projects.  Assume that all of the programmers are equally competent.

After some careful thought, you have figured out how much benefit $i$
programmers will bring to project $j$.  View this benefit as a number.
Formally put, for each project $j$, you have computed an array $A_j[0..m]$
where $A_j[i]$ is the benefit obtained by assigning $i$ programmers to project
$j$.  Assume that $A_j[i]$ is nondecreasing with increasing $i$.  Further make
the economically sound assumption that the marginal benefit obtained by
assigning an $i$th programmer to a project is nonincreasing as $i$ increases.
Thus, for all $j$ and $i \ge 1$, $A_j[i+1] - A_j[i] \le A_j[i] - A_j[i-1]$.

Design a greedy algorithm to determine how many programmers you will assign to
each project such that the total benefit obtained over all projects is
maximized.  Justify the correctness of your algorithm and analyze its running
time.

{\bf Answer:} We assign programmers one at a time, from $1$ to $m$.  At the
$i$th step, we greedily assign the $i$th programmer to the project to which
the programmer will bring the most marginal benefit.  Note that the marginal
benefit that the $i$th programmer brings to a project $j$ depends on the
particular assignment of the previous $i - 1$ programmers; it may not be the
same as $A_j[i]$.

We now prove that the above greedy choice leads to an optimal solution using a
standard ``swapping argument''.  Our main claim is this: for all $i$, the
assignment obtained after the $i$th step is the subset of an optimal
assignment.  We prove the claim by induction. 

The induction basis is trivial since we start with an empty assignment which
is clearly a subset of an optimal assignment.  As the induction hypothesis, we
assume that the claim holds after step $i - 1$.  That is, the assignment
obtained after step $i - 1$ is a subset of an optimal assignment, say $S$.  We
now consider the state after step $i$.  Let us suppose that the greedy choice
assigns the $i$th programmer to project $j$, thus resulting in $k$ programmers
for project $j$.  If $S$ has assigned at least $k$ programmers to project $j$,
then there is nothing to prove.  (Note that by the induction hypothesis, $S$
has assigned at least $k - 1$ programmers to project $j$.)  Consider the case
in which $S$ has assigned only $k - 1$ programmers.  This implies that there
must be some other project $j'$ such that $S$ has assigned more programmers
than the greedy assignment has assigned thus far.  By the definition of our
greedy choice and the assumption about marginal benefits, it follows that if
we modify $S$ by removing one programmer from project $j'$ and move it to $j$,
the change in total benefit cannot decrease.  Therefore, the new assignment
thus obtained by modifying $S$ is optimal.  It also contains the current
greedy assignment, thus establishing the induction step.

We now consider the running time of the greedy algorithm.  We have $m$
iterations and in each iteration we are determining the project for which the
marginal benefit will be maximum.  Thus, a naive $n$-element comparison to
determine the maximum will take $O(n)$ time, leading to a runtime of
$\Theta(nm)$.  One can do better by maintaining a priority queue in which we
store an element for each project, representing the marginal benefit the next
programmer will bring to the project.  Initially, we add $n$ entries to a
priority queue, one for each of the projects, representing the marginal
benefit that the first programmer brings to the project.  As we have seen in
class (and Chapter 7), we can implement this in $O(n)$ time using {\sc
Build-Heap}.  Each iteration then translates to one \emax\ operation (to find
the project to which the programmer will be assigned) and an \ins\ operation
to insert a new element giving the marginal benefit the next programmer will
bring to the chosen project.  Each iteration thus takes $O(\log n)$ time, thus
leading to a total runtime of $O(n + m\log n)$.

{\bf (10 bonus points)} Now {\em remove}\/ the assumption made above that the
marginal benefit obtained by assigning an $i$th programmer to a project is
nonincreasing as $i$ increases.  Design a dynamic programming algorithm to
determine how many programmers you will assign to each project such that the
total benefit obtained over all projects is maximized.  Analyze its running
time.

{\bf Answer:} Let $C[i,j]$ denote the total benefit obtained in the optimal
assignment $i$ programmers among projects $1$ through $j$.  Let $B[i,j]$
denote the number of programmers assigned to the $j$th project in this optimal
solution.  We can establish the following recurrences for $C[i,j]$ and
$B[i,j]$. We set $C[0,j]$ to $0$ for all $j$.  Furthermore, for all $i$,
$C[i,1]$ equals $A_1[i]$ and $B[i,1]$ equals $i$.  For $i > 0$ and $j > 1$, we
have the following.  Let $k$ be such that $A_j[k] + C[i-k,j-1] = \max_{0 \le \ell
\le i} \{A_j[\ell] + C[i-\ell,j-1]\}$.  Then, $C[i,j] = A_j[k] + C[i-k,j-1]$
and $B[i,j] = k$.  

The algorithm proceeds by iteratively computing $C[i,j]$ and $B[i,j]$, $i$
going from $1$ through $m$ and $j$ going from $1$ through $n$.  The final
assignment can be computed using the $B$ array.  In each iteration, we need to
take the maximum of at most $m$ entries.  Therefore, there are at most $nm$
iterations, each taking $O(m)$ time, leading to a runtime of $O(m^2 n)$.

Note that in the above argument, we do not use the property about marginal
benefits that was used in the first part of the problem.  The property that
the array $A_j$ is nondecreasing is implicitly used by the fact that we try
to get as much benefit as we can by using all of our programmers.

{\bf 4. (10 points)} Exercise~17.3-2, page 344.

{\bf Answer:} For the character set $a$, $b$, $c$, $d$, $e$, $f$, $g$, and
$h$, with the frequencies $1$, $1$, $2$, $3$, $5$, $8$, $13$, and $21$,
respectively, the Huffman code is $0000000$, $0000001$, $000001$, $00001$,
$0001$, $001$, $01$, and $1$, respectively.  In general, for an $n$-length
Fibonacci sequence, the Huffman encoding is $n-1$ 0's for $a_1$, and $n-i$ 0's
followed by a $1$ for $a_i$, $2 \le i \le n$.  

{\bf 5. (15 points)} Exercise~23.3-10, page 485.

We present a simple $O(V\cdot E)$ algorithm for the problem.
But first, we establish a claim that will help presenting the algorithm
and proving its correctness.

{\flushleft {\bf Claim1}} For any node $u$, there is at most one simple path from
$u$ to $v$ for all $v \in V$ if and only if, the dfs-tree rooted at $u$ has no
forward and cross edges.

{\flushleft {\bf Proof}} Consider the dfs-tree $T$ rooted at $u$ (
obtained by executing DFS-VISIT($u$) -- refer page 478 of text). For the if part,
$T$ has no forward and cross edges. Let, if possible, there be two simple paths
from $u$ to some node $v \in V$ . Clearly $v \in T$ as only the vertices in $T$ are
reachable from $u$. At least one of the paths (say $P$) contains
some back edge. Let the first back edge in this path be $(w,x)$. So path $P$ consists
of tree edges from $u$ to $w$ and then the back edge $(w,x)$ followed by possibly
more edges. Since $(w,x)$ is a back edge, $x$ lies in the subpath consisting
entirely of tree edges from $u$ to $w$, thus making $P$ non-simple.

If $T$ has some
forward or cross edge $(v,w)$, then there are two simple paths from $u$ to $w$ -- one
solely following the tree edges, and the other following the tree edges to $v$
and then the edge $(v,w)$.

\begin{verbatim}
SINGLY-CONNECTED?(G)
{Input:  Graph G = (V,E).
 Output: TRUE if G is singly connected, FALSE otherwise}
1 singly_connected := FALSE;
2 for each v in V do
3     singly_connected := MODIFIED-DFS-VISIT(v);
4     if (singly_connected = FALSE)
5        return FALSE;
6 endfor
7 return TRUE;

MODIFIED-DFS-VISIT(v)
{Input:  Vertex v of graph G
 Output: TRUE if there are no forward and cross edges in
         dfs-tree rooted at v, FALSE otherwise}
1 color[u] := GRAY;
2 for every edge (u,v)
3     do if color[v] = BLACK
4           return FALSE;
5        if color[v] = WHITE
6           if (MODIFIED-DFS-VISIT(v) = FALSE)
7              return FALSE;
8 color[v] = BLACK;
9 return TRUE;
\end{verbatim}
MODIFIED-DFS-VISIT starts a depth-first search from node $v$ and returns
FALSE when a forward or cross edge is detected (line 3). By Claim1,
SINGLY-CONNECTED?(G) returns TRUE if for every vertex $u$, there is at most one
simple path from $u$ to any vertex $v \in V$, FALSE otherwise.

MODIFIED-DFS-VISIT for every vertex $v$ takes $O(E)$ time. And this
procedure is called $O(V)$ times. Therefore the running time is
$O(V\cdot E)$

{\bf 6. (15 points)} Exercise~23.4-5, page 488.

{\bf Answer:} The algorithm begins by first finding the in-degree of
all vertices.  For this we initialize the in-degrees to zero and then
go through all of the edges and increases the increment the in-degrees
of the heads of the edges by $1$. 
\begin{tabbing}
1. \= \myfor\ \= $u \in V$\\
2. \> \> $\ind[u] \leftarrow 0$\\
3. \> \myfor\ $u \in V$\\
4. \> \> \myfor\ \= $v \in \Adj[u]$\\
5. \> \> \> $\ind[v] \leftarrow \ind[v] + 1$
\end{tabbing}
This takes $\Theta(V + E)$ time, since $V$ adjacency lists are
accessed and $E$ edges found.  We keep the vertices with in-degree $0$
in a FIFO queue, so that they can be enqueued and dequeued in $O(1)$
time.
\begin{tabbing}
6. \= $Q \leftarrow \emptyset$\\
7. \> \myfor\ \= $u \in V$\\
8. \> \> \myif\ \= $\ind[u] = 0$\\
9. \> \> \> $\enq(Q, u)$
\end{tabbing}
This takes $\Theta(V)$ time.  As we process each vertex from the
queue, we effectively remove its outgoing edges from the graph by
decrementing the in-degree of each vertex one of those edges enters,
and we enqueue any vertex whose in-degree goes to $0$.  Each vertex is
enqueued/dequeued at most once because it is enqueued only if it
starts out with in-degree $0$ or if its in-degree becomes $0$ after
being decremented (and never incremented) some number of times.
\begin{tabbing}
10. \= \mywhile\ \= $Q \neq \emptyset$\\
11. \> \> $u \leftarrow \deq(Q)$\\
12. \> \> output $u$\\
13. \> \> \myfor\ \= $v \in \Adj[u]$\\
14. \> \> \> $\ind[v] \leftarrow \ind[v] - 1$\\
15. \> \> \> \myif\ \= $\ind[v] = 0$\\
16. \> \> \> \> $\enq(Q, v)$
\end{tabbing} 
The processing of a vertex from the queue happens $O(V)$ times because
no vertex can be enqueued more than once.  The per-vertex work
(dequeue and output) takes a total of $O(V)$ time.  Since each
adjacency list is scanned at most once (the for-loop in line 13), the
total time spent scanning the edges is $O(E)$.  Finally, we check for
cycles.
\begin{tabbing}
17. \= \myfor\ \= $u \in V$\\
18. \> \> \myif\ \= $\ind[v] \neq 0$\\
19. \> \> \> print ``cycle exists''
\end{tabbing}
Lines 17 through 19 take $\Theta(V)$ time.  Therefore, the overall
running time of the algorithm is $O(V + E)$.

\BfPara{Proof of correctness:} The algorithm outputs vertices in the
right order because a vertex $v$ will not be output until its
in-degree becomes $0$, which happens only when every edge $(u,v)$
leading into $v$ has been ``removed'' due to the processing of $u$.
Furthermore, if there are no cycles, then all vertices are output.  We
prove this by contradiction.  Assume that some vertex $v_0$ is not
output.  This implies that some edge, say $(v_1, v_0)$ coming into
$v_0$ never got removed, which means that $v_1$ was not output.
Similarly, $v_1$ not output implies the existence of some vertex $v_2$
such that $(v_2, v_1)$ was not removed.  Since the number of vertices
is finite, this path $\ldots \rightarrow v_2 \rightarrow v_1
\rightarrow v_0$ is finite, so we must have two identical vertices in
this path, implying that the path is a cycle, thus yielding a
contradiction.

We finally show that if there is a cycle, then the in-degree of no
vertex in the cycle will go to zero and, thus, none of the vertices in
the cycle will be output.  Again, the proof is by contradiction.  Let
$v$ be the first vertex in a cycle to be output.  This implies that
the edge, say $(u,v)$, in the cycle that comes into $v$ must have been
removed.  But this can only happen if $u$ has been already output,
yielding a contradiction to the fact that the $v$ is the first vertex
in the cycle to be output.

{\bf 7. (15 points)} Prove that if $T_1$ and $T_2$ are two minumum
spanning trees of a graph $G$, then $T_1$ and $T_2$ have the same
``weight distribution'' (i.e., for any weight $w$, both $T_1$ and
$T_2$ contain the same number of edges with weight $w$).

{\bf Answer:} We prove this by induction. Let $T_1$ and $T_2$ be the
two minimum spanning trees with $m$ vertices, and $x_1, x_2, \ldots,
x_m$ \& $y_1, y_2, \ldots, y_m$ be their edge weights, sorted in
non-decreasing order. We now argue that both these lists must be
exactly the same. That is, $x_i = y_i, 1 \le i \le m$.

For the base case compare $x_1$ and $y_1$. If they are equal, look keep
looking for the first set of $x_i, y_i$ that are not equal. If no such
set exists, done.
Otherwise, without loss of generality, let $y_1$ be the smaller quantity.
Then insert the edge corresponding to $y_1$ into $T_1$. This creates a
cycle, and all edges in the cycle originally belonging to $T_1$ have weights
greater than $y_1$. Removing one of them gives a tree with weight less
than that of $T_1$, a contradiction as $T_1$ is a MST.

Assume this to be true for $i = k - 1$. That is, $x_i = y_i, 1 \le i \le k - 1$.
We now prove that this is true for $i = k$ proving the result by
induction. Let $x_k > y_k$. Then we prove that we can replace each of
the edges with weights $x_i$ by those with weights $y_i$, 
for $1 \le i \le k - 1$, and then arrive at a 
contradiction.

Let $w_1, w_1, \ldots, w_l$ be the distinct edge weights in the graph
and, $x_{i.w_k}$ represent the fact that edge $x_i$ has weight $w_k$.

Then from what we have shown above, the two edge lists are of the form\\
$<x_{1.w_1}, \ldots, x_{{i_1}.{w_1}}$, $x_{{{i_1}+1}.{w_1}}, \ldots, x_{{i_2}.{w_1}}, \ldots,$ 
$x_{{{i_{z-1}}+1}.{w_1}}, \ldots, x_{{i_z}.{w_1}}$, $x_k, \ldots, x_m>$\\
and,\\
$<y_{1.w_1}, \ldots, y_{{i_1}.{w_1}}$, $y_{{{i_1}+1}.{w_1}}, \ldots, y_{{i_2}.{w_1}}, \ldots,$ 
$y_{{{i_{z-1}}+1}.{w_1}}, \ldots, y_{{i_z}.{w_1}}$, $y_k, \ldots, y_m>$,\\
for some $i_p \ge 1\; for\;  1 \le p \le z$, such that $\sum_1^z {i_p} = k - 1$.

Note in the above representation edges of some weights may not occur, but
that does not make a difference to our proof, as there will be same
weighted edges up to the index $k$.

Now we begin the process of replacing an edge of $T_1$ with an edge of $T_2$. 
Inserting an edge into $T_1$ creates a cycle, from which a ``suitable'' 
edge is removed to get back an MST. (Even though $T_1$ is technically
transformed into a totally different MST by the transformation, we still
refer to the new graph as $T_1$ to avoid confusion.)
\begin{itemize}
\item Firstly, note that when any of the edges with weights $y_{j.w_1}$'s are 
inserted into $T_1$, then they create cycles only with (some of the) 
edges with 
weights $x_{j.w_1}$'s, because if they do so with any other edge (whose
weight is greater), it
would mean that $T_1$ is not an MST. 

\item The other point to note is that
when placing, say $y_{j.w_1}$, into $T_1$, after edges corresponding to weights
$y_{1.w_1}, \ldots, y_{j-1.w_1}$ 
have already been inserted, then 
in the cycle formed by the insertion of edge with weight 
$y_{j.w_1}$ will not form
a cycle solely with the those with weights $y_{1.w_1}, \ldots, y_{j-1.w_1}$, 
because this would imply that there is a cycle in $T_2$, contradicting the
fact that $T_2$ is an MST. 

\item Finally, inserting edges with weights $y_{j.w_2}$'s into $T_1$, 
creates a cycle only with edges with weights $x_{j.w_2}$'s ,again because
of the fact that $T_1$ is an MST and that there can be no cycles in $T_2$.
\end{itemize}

At the end of all this effort we have transformed $T_1$ from \\
$<x_{1.w_1}, \ldots, x_{{i_1}.{w_1}}$, $x_{{{i_1}+1}.{w_1}}, \ldots, x_{{i_2}.{w_1}}, \ldots,$ 
$x_{{{i_{z-1}}+1}.{w_1}}, \ldots, x_{{i_z}.{w_1}}$, $x_k, \ldots, x_m>$\\
to,\\
$<y_{1.w_1}, \ldots, y_{{i_1}.{w_1}}$, $y_{{{i_1}+1}.{w_1}}, \ldots, y_{{i_2}.{w_1}}, \ldots,$ 
$y_{{{i_{z-1}}+1}.{w_1}}, \ldots, y_{{i_z}.{w_1}}$, $x_k, \ldots, x_m>$,\\
for some $i_p \ge 1\; for\;  1 \le p \le z$, such that $\sum_1^z {i_p} = k - 1$.

Now insert $y_k$ into $T_1$. This creates a cycle. The cycle 
cannot have any 
of the edges with weights $< y_k$, as this would imply the existence of 
a cycle in $T_2$. Hence the cycle must contain at least one edge of weight
$> y_k$. Removal of this edge, gives an MST with lesser weight, resulting
in a contradiction.

Hence the proof.

{\bf 8. (7 + 8 + 5 = 20 points)} Problem~18--1, page 375.

{\bf Answer:} 
\begin{itemize}
\item[{\bf (a)}] 

BIT-REVERSAL-PERMUTATION($A$)
\begin{enumerate}
\item for $i = 1$ to $\lfloor \frac{n}{2} \rfloor$
\item \hspace*{.5cm} A[$i$] $\longleftrightarrow$ A[$rev_k$ ($i$)]
\end{enumerate}

This algorithm performs $\lfloor \frac{n}{2} \rfloor$ steps each taking
$\Theta(k)$ time, hence taking a total time of $O(nk)$.

{\bf NOTE}: The result of part c. depends on
the assumptions that are made while making up the algorithm in part b.
This is because of the confusing ``etc.'' word in part b. of the question
For example, the given implementation makes use of AND and OR and shifting
of bits as they are all mentioned in the question. In this case, the
required result cannot be obtained in part c. However, using another
implementation, in which no bit shifts are used, only ANDing and ORing
with suitable bits, it is possible to get a working solution for c. Credit
will be given as long as the assumptions are clearly stated and/or understood.

\item[{\bf (b)}]
  
  BIT-REVERSED-INCREMENT($a$, $k$)
\begin{enumerate}
\item $i = k$
\item while $i > 0$ and ($a$ $\gg$ $(i-1$) = 1)
\item \hspace*{.5cm} do $a \longleftarrow a$ AND $\{(1 \ll (i - 1) -
1\}$
\item \hspace*{.5cm} $i \longleftarrow i - 1$
\item if $i > 0$
\item \hspace*{.5cm} then $a \longleftarrow a$ OR $(1 \ll (i - 1))$
\item return a
\end{enumerate}

Note that not all the bits flip (by the OR statements) each time
BIT-REVERSE-INCREMENT is called. The highest order bit flips each
time it is called, the second highest order bit flips every other
time. In general for $i = 0, 1, 2, \ldots, k$, bit $a_{k - i}$
flips $\lfloor \frac{n}{2^{i-1}} \rfloor$ times in a sequence
of $n$ calls.

The total number of flips in the sequence

\[= \sum_{i = 0}^{\lfloor lgN \rfloor} \lfloor
\frac{n}{2^{i-1}}\]
\[ < n \sum_{i = 0}^{\infty} \frac{1}{2^{i}}\]
\[ = 2n\]

So amortized cost of each of the $n$ operations is O(1).  Now consider
the following implementation of BIT-REVERSAL-PERMUTATION.

BIT-REVERSAL-PERMUTATION($A$)
\begin{enumerate}
\item for $i = 1$ to $\lfloor \frac{n}{2} \rfloor$
\item \hspace*{.5cm} A[$i$] $\longleftrightarrow$
A[BIT-REVERSED-INCREMENT($i$)]
\end{enumerate}

Now the running time is $(\frac{n}{2}) x O(1) = O(n)$.

\item[{\bf (c)}] When the shifts cannot be done in unit time, the cost
  increases because even though the number of flips remains the same,
  the multiple shift operations in the algorithm depend on the value
  of $i$ for each loop and hence the amortized analysis does not give
  the above result.
\end{itemize}

{\bf 9. (5 + 3 + 12 = 20 points)} Problem~25--2, page 546.

\begin{itemize}
\item[{\bf (a)}] We want to show that if box $x$ nests in box $y$, and
  box $y$ nests in box $z$, then box $x$ nests in box $z$.
  
  If $y$ nests in $z$, then there is a permutation function, $\pi_{y,
    z}$, such that $y_{\pi_{y, z}(j)} < z_j$ for $1 \le j \le d$ where
  $d$ is the dimension of the box. Similarly, if $x$ nests in $y$,
  there is another permutation function $\pi_{x, y}$, such that
  $x_{\pi_{x, y}(j)} < y_j$ for $1 \le j \le d$.  Now,

\[x_{(\pi_{x, y})(\pi_{y, z})(j)} < y_{\pi_{y, z}(j)} < z_j, \mbox{ for } 1 \le j \le d.\]

Hence the result.       

\item[{\bf (b)}] Given two boxes $X$ and $Y$, sort the dimensions of
  individual boxes in non-decreasing order. Let the sorted dimensions
  be $<x_1, x_2, \ldots, x_d>$, and be $<y_1, y_2, \ldots, y_d>$,
  where $d$ is the dimension of the space. Then box $X$ nests inside
  box $Y$, if $x_i < y_i, 1 \le i \le d$, and box $Y$ nests inside box
  $X$, if $y_i < x_i, 1 \le i \le d$.
  
\item[{\bf (c)}] The longest sequence of nestable boxes can be found
  by constructing the following graph $G$ and then running the DAG
  shortest-paths algorithm. Let each box $B_i$ represent a vertex, and
  an edge is added from box $B_i$ to box $B_j$ if box $B_i$ nests
  inside box $B_j$, and given a weight of $-1$.  Two new vertices $s$
  and $t$ depicting the source and target respectively are also added.
  An edge from $s$ to each $B_i$ is added, and an edge from each $B_i$
  to $t$ is added, with all edges being assigned weight -1.  The
  shortest path from $s$ to $t$ is then determined using DAG
  shortest-paths algorithm. The longest sequence of nestable boxes is
  determined by removing $s$ and $t$ from the output.
  
  DAG shortest-paths algorithm can be used to solve the shortest paths
  problem in $O(V+E) = O(n^2)$ time.
\end{itemize}
\end{document}

