\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 4}
\author{Chris Laas: Section G}
\date{March 7, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 3/7/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}



\begin{document}
\maketitle

\section*{Problem 4-1}
\begin{enumerate}

\item%(a)

\begin{program}
|Majority-Element-Ordered|(A)
\quad\tab x \gets |Select|(A, \left\lfloor\frac{|Length|(A)}{2}\right\rfloor)
          c \gets 0
          \FOR i \gets 1 \rdots |Length|(A)
              \IF A[i] = x
                 \THEN c \gets c + 1
                      \untab%
                 \untab%
              \untab%
          \IF c > \frac{|Length|(A)}{2}
             \THEN \RETURN x
             \ELSE \RETURN |None|
\end{program}

Since the majority element is stored in the array more than
$\frac{n}{2}$ times, it must be the median element; thus, if
$A$ has a majority element, the $|Select|$ finds it and returns it to
$x$.  The rest of the algorithm simply counts the number of
occurrences of $x$; if it appears more than $\frac{n}{2}$
times, it is the majority element, else there is no majority element.

Since the for loop executes exactly $n$ times, and the $|Select|$
subcall must terminate, this algorithm must terminate.

The $|Select|$ subcall executes in $O(n)$ time; the for loop executes
in $\Theta(n)$ time.  Thus, this algorithm executes in $\Theta(n)$
time.


\item%(b)

Assume that $a$ is the majority element of $A$, i.e. $a$ is stored in
$A$ more than $\frac{n}{2}$ times.  Assume $A[i] \neq A[j]$; and let
$A'$ be $A$ with $A[i]$ and $A[j]$ removed.  If $A[i] \neq a$ and
$A[j] \neq a$, then $A'$ still has $a$ stored in it more than $\frac{n}{2}$
times, so clearly $a$ is in $A'$ more than $\frac{n-2}{2}$ times.  Else,
if $A[i] = a$, then $A[j] \neq a$, so $A'$ has $a$ stored in it more
than $\frac{n}{2}-1 = \frac{n-2}{2}$ times.  (Likewise if $A[j] = a$.)

Either way, $A'$ has $a$ stored in it more than $\frac{n-2}{2}$
times.  Thus, $a$ is the majority element of $A'$.


\item%(c)

\begin{program}
|Majority-Element-Unordered|(A)
\quad\tab c \gets 0
          \FOR i \gets 1 \rdots |Length|(A)
              \IF c = 0
                 \THEN c \gets 1
                       |key| \gets A[i]
                 \ELSE \IF A[i] = |key|
                          \THEN c \gets c + 1
                          \ELSE c \gets c - 1
                               \untab%
                          \untab%
                      \untab%
                 \untab%
              \untab%
          \IF c = 0
             \THEN \RETURN |None|
             \ELSE \RETURN |key|
\end{program}

For this algorithm, $A'$, the working array, is conceptually equal to
the value of $|key|$ repeated $c$ times, followed by the elements of
$A$ after the $i$th.  The loop invariant is that, after each
iteration, the majority element of $A'$ is the same as the majority
element of $A$ (unless $A$ has no majority element, in which case $A'$
has no majority element).  The condition holds, trivially, at the
beginning of the loop; at each iteration, one of three things happens.
If there is currently no $|key|$ ($c = 0$), the next element of $A$ is
made the key (this does not change $A'$).  If there is a key, and the
next element of $A$ is equal to it, $c$ is incremented to indicate
that $A'$ has another copy of $|key|$ in it (again, $A'$ is not
changed).  Lastly, if there is a key, and the next element of $A$ is
not equal to it, then the next element of $A$ is thrown away, along
with one copy of $|key|$ (by decrementing $c$).  In this case, $A'$
retains the same majority element, by the result of (b).

Since the loop executes exactly $n$ times, the algorithm must
terminate; the loop invariant, along with the postcondition (that
there are no more elements of $A$ to process), imply that if there is
a key, it is the majority element.  This proves correctness.

Since the loop executes exactly $n$ times, the algorithm runs in
$\Theta(n)$ steps.


\end{enumerate}
\newpage



\section*{Problem 4-2}

This algorithm should be called as $|Select-From-Two|(A, B, k, 1, k)$.
It performs a binary search to find the $k$th smallest element (where
$k=1$ results in the smallest element).  The precondition is that the
$k$th smallest element is either in $A[p \rdots q]$ or
$B[k+1-q \rdots k+1-p]$; the postcondition is that it returns the
$k$th smallest element.

\begin{program}
|Select-From-Two|(A, B, k, p, q)
\quad\tab \IF p = q
             \THEN \IF k+1-p > n
                      \THEN \RETURN A[p]
                           \untab%
                      \untab%
                   \IF p > n
                      \THEN \RETURN B[k+1-p]
                           \untab%
                      \untab%
                   \IF      (2p - k \neq 0 \AND A[p] < B[k+1-p])
                        \OR (2p - k =    0 \AND A[p] > B[k+1-p])
                      \THEN \RETURN A[p]
                      \ELSE \RETURN B[k+1-p]
                           \untab%
                      \untab%
                  \untab%
             \untab%
          i \gets \left\lfloor\frac{p+q}{2}\right\rfloor
          \IF A[i] < B[k+1-i]
             \THEN \RETURN |Select-From-Two|(A, B, k, i, q)
             \ELSE \RETURN |Select-From-Two|(A, B, k, p, i)
\end{program}

I think I may have missed some of the many annoying edge cases, but
the concept is certainly sound.  It boils down to binary searching for
the point at which the respective elements of $A$ and $B$ would be
sequential in a sorted union of $A$ and $B$, while holding the sum of
the indices into $A$ and $B$ equal to $k$.  Termination is guaranteed
by the monotonically decreasing value of $q-p$.  The recursion formula
for the run time is $T(k) = T(k/2) + \Theta(1)$, so
$T(k) = \Theta(\lg k)$.

\newpage



\section*{Problem 4-3}
\begin{enumerate}

\item%(a)

This algorithm walks through the preorder traversal $A$ one element at
a time, placing each one in the tree by consulting the inorder
traversal $B$.  It first checks whether the next element is a child of
the ``current parent node'' at all, and returns 'nil' if not.  If it
is, it allocates a new node for this ``next element'', and recurses to
regenerate first the left subtree, and then the right subtree.

\begin{program}
|Make-Tree|(A, B, i, p, q)
\quad\tab k \gets |Binary-Search|(B, A[i], p, q)
          \IF k = |None|
             \THEN \RETURN (i, |Nil|)
                  \untab%
             \untab%
          |node|.|value| \gets A[i]
          i \gets i + 1
          (i, |node|.|left|)  \gets |Make-Tree|(A, B, i, p, k)
          (i, |node|.|right|) \gets |Make-Tree|(A, B, i, k, q)
          \RETURN (i, |node|)
\end{program}

\item%(b)

There is no way to reconstruct the original tree from a postorder
traversal and a preorder traversal.  Take, for example, the tree, with
two nodes $a$ and $b$, such that $a$ is the root and $b$ is its left
child.  The preorder traversal of this tree is $ab$, and the postorder
traversal is $ba$.  However, the tree with $a$ as the root and $b$ is
its {\em right} child has the same preorder and postorder traversals.
Thus, no algorithm can distinguish between the two trees given only
the preorder and postorder traversals.

\item%(c)

This problem is, in fact, equivalent to part (a).  Consider that we
can regenerate the inorder traversal merely by sorting the preorder
traversal; then we can just feed the results into the algorithm from
part (a) to regenerate the binary tree.

(Conversely, given an algorithm to regenerate a binary search tree, we
could have solved (a) by defining the order on the elements {\em by}
the given inorder traversal.)

\end{enumerate}
\newpage




\section*{Problem 4-4}
\begin{enumerate}

\item%(a)

Assume that a given node in a binary search tree has two children.
Then, since all nodes not in the nodes's right subtree will be greater
than the node's right child or less than the node's left child, the
node's successor is in its right subtree, and its predecessor is in
its left subtree.  Now assume, for the sake of contradiction, that the
node's successor has a left child.  Then, since the successor is in
the right subtree, its left child is in between the node and its
successor.  But this contradicts the definition of the node's
successor.  The same logic shows that the node's predecessor has no
right child.


\item%(b)

Yes, we are always left with the same tree, using the deletion
algorithm given in lecture.  This is because the successor of $b$ is
not affected by deleting $a$, and vice versa, unless $a$ {\em is}
$b$'s successor (or vice versa), in which case the deletion order
still doesn't matter.

\end{enumerate}
\newpage



\section*{Problem 4-5}
\begin{enumerate}

\item%(a)

If the weights are $w_i = 1/n$, then the weighted median is the
element $x_k$ satisfying

$$ \sum_{x_i < x_k} \frac{1}{n} \leq \frac{1}{2} $$
and
$$ \sum_{x_i > x_k} \frac{1}{n} \leq \frac{1}{2} $$

i.e.

$$ |Count|(x_i < x_k) \leq \frac{n}{2} $$
and
$$ |Count|(x_i > x_k) \leq \frac{n}{2} $$

This is equivalent to the condition that $x_k$ be the standard median.

\item%(b)

Simply sort the elements by $x_i$, and iterate over the sorted
weights, summing until the total exceeds 1/2.  Then you are at the
weighted median.

\item%(c)

To modify $|Select|$ to compute the weighted median, you need to make
another pass over the two partitions after partitioning, to calculate
the weighted sum of the elements on each side of the partition.  Then
you simply choose to recurse on the correct partition based on the
weighted sum instead of on the element count.


\end{enumerate}
\newpage



\end{document}
