\documentstyle [12pt]{article}
\setlength{\parskip}{1 ex}
\setlength{\topmargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0 in}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}

\begin{document}
\sloppy

{\large
CMU 15-451 \hfill ASSIGNMENT \# 3 \hfill FALL 1993
\begin{center}
 Solutions
\end{center}}

\section*{Problem 1: 10-1 Largest $i$ numbers in sorted order}
IN: ${\cal I} = x_1, x_2, \ldots, x_n$  \\
OUT: ${\cal O} = y_1, y_2, \ldots, y_i$ \\
where $y_1, y_2, \ldots, y_i$ are the $i$ maximum $x_j$'s in sorted order.

\subsection*{a. Sort the numbers and list the $i$ largest}

\begin{tabbing}
$B[1..n] = \mbox{sort}({\cal I})$ \\ 
${ \cal O} = B[n-i..n]$ 
\end{tabbing}

Thus the algorithm takes $O(n \log n)$ worst-case time to sort (using
for example {\sc heapsort}) and $O(i)$ worst-case time to list the $i$
numbers.  So the algorithm runs in $O(n \log n)$ time.

\subsection*{b. Build a priority queue and call {\sc Extract-Max} $i$
times}

\begin{tabbing}
$H = \mbox{buildheap}({\cal I})$ \\ 
for \= $j \leftarrow 1 \ldots i$ \\ 
    \> $y_j \leftarrow \mbox{pop}(H)$ 
\end{tabbing}

{\sc Buildheap} takes $O(n)$ time and each {\sc pop} takes $O(\log n)$ time.
Since we do $i$ {\sc pop}'s, the algorithm takes $O(n +  i \log n)$ time.

\subsection*{c. Use an order statistic algorithm to find the $i$th
largest number, partition, and sort the $i$ largest numbers.}

\begin{tabbing}
 $k \leftarrow \mbox{select}({\cal I}, n-i)$ \\
 $S_<, S_=, S_> \leftarrow \mbox{partition}({\cal I}, k)$ \\
 ${\cal O} \leftarrow \mbox{sort}(S_>)$ \\
\end{tabbing}

{\sc Select} takes $O(n)$ time and partitioning also takes $O(n)$
time.  Sorting takes $O(i \log i)$ time.  Thus the total time is $O(n
+ i \log i)$, which is significantly better than algorithms
{\bf a} and {\bf c}.

%\newpage
\section*{Problem 2: Weighted median}

\subsection*{a. Argue that $w_i = 1/n$ gives true median}

Because all of the $w_i$'s are equal, the same number of elements will
be on each side of the weighted median.  This is the definition of
median.

\subsection*{b. Use sorting to compute weighted median in $O(n \log
n)$ time}

\begin{tabbing}
 Sort the elements, let $s(i)$ be the sorted location of $x_i$. \\
 Compute a running sum, that is $y_j = \sum_{s(i)<s(j)} w_i$. \\
 Find $1/2$-crossing in the $y_j$'s. \\
 This is the weighted median. 
\end{tabbing}

\subsubsection*{Time Complexity}

Sorting takes $O(n \log n)$ time.  Computing a running sum takes $O(n)$
time.  Finding a scalar crossing in a monotonically increasing
sequence takes $O(n)$ time.  Thus the algorithm is dominated by the
$O(n \log n)$ sorting time.

\subsubsection*{Correctness}
The weighted median value $x_k$ has associated with it a value $y_k$
such that $y_{k-1} \le 1/2$ and $y_{k+1} \ge 1/2$.  Because $y_{k-1}$
is exactly $\sum_{s(i)<s(j)} w_i$, $y_k$ is greater than
$\sum_{x_i<x_k} w_i$.  (It is possible that some values equal to $x_k$
are counted in $y_k$.)  Thus by transitivity, the first of the two
requirements is satisfied.  An analogous argument exists for the
second requirement, using $n-y_{k+1}$.

\subsection*{c. Use {\sc Select} for a $\Theta(n)$ time algorithm.}
Define $M$ to be the value one is looking for, that is redefine the
problem to be find the element $x_k$ such that $\sum_{x_i<x_k} w_i$ is
maximally $< M$.  This allows us to view the problem in an
order-statistic way.  (The problem given is the special case in which
$M = 1/2$).

Modify {\sc Select} as given in section 10.3 by changing steps 4 and 5
to be: \\
4. Partition around the median-of-medians as before. \\
4b. Calculate the sums of the two partitions. \\
5. Use {\sc Select} recursively to find the weighted median element on
the low side if $\mbox{$\sum_{x_i \le x_k} w_i \ge M$}$ and or look for $M -
\sum_{x_i \in \mbox{Left-Partition}} w_i$ on the right side. 

\subsubsection*{Time Complexity}
Since the only change to {\sc Select} occurs in steps 4a and 5, I will show
that the time complexity for the modified steps is the same as the time complexity for
the original steps and thus that the time complexity for {\sc Select} is still
$\Theta(n)$.  

Step 4 itself is unchanged (still $\Theta(n)$).  Step 4b is a running
sum problem and takes $\Theta(n)$ time.  Step 5 is unchanged in terms
of running time.  Since step 4b can be absorbed into the $\Theta(n)$
time of step 4, the running time of {\sc Select} is still $\Theta(n)$.

\subsubsection*{Correctness}
As long as we are always (1) looking for the correct median value in
the (2) correct side, this algorithm is correct.  These are both clear by 
observation of step 5.

%\newpage

\section*{Problem 3a: Inversions and sorting}
The basic algorithm is to perform a {\sc Mergesort} but to count every
time a ``right-half element'' is merged before a ``left-half
element.''  This is done in the {\sc Merge} step of the {\sc Mergesort}.

Standard Merge:
\begin{tabbing}
\hspace{3 em} \= \hspace{3 em} \= \hspace{3 em} 
\= \hspace{3 em} \= \hspace{3 em} \= \hspace{3 em} \= \kill
Merge(L, R) $\rightarrow X$ \\
\> IN: $L = l_1 \ldots l_n$, $R = r_1 \ldots r_m$  \\
\> OUT: $X = x_1 \dots x_{n+m}$ \\ 
\> if ($|L| = 0 \mbox{ and } |R| = 0$) return \\
\> if ($\mbox{first}(L) \le \mbox{first}(R) \mbox{ or } |R| = 0$) \\
\> \> return X = [pop(L), Merge($l_2 \ldots l_n$, R)] \\
\> else ($\mbox{first}(L) > \mbox{first}(R) \mbox{ or } |L| = 0$) \\
\> \> return X = [pop(R), Merge(L, $r_2 \ldots r_m$)] \\
End Merge
\end{tabbing}

Merge with count:
\begin{tabbing}
\hspace{3 em} \= \hspace{3 em} \= \hspace{3 em} 
\= \hspace{3 em} \= \hspace{3 em} \= \hspace{3 em} \= \kill
Merge(L, R) $\rightarrow X$  \\
\> IN: $L = l_1 \ldots l_n$, $R = r_1 \ldots r_m$   \\
\> OUT: $X = x_1 \dots x_{n+m}$  \\
\> if ($|L| = 0 \mbox{ and } |R| = 0$) return   \\
\> if ($\mbox{first}(L) \le \mbox{first}(R) \mbox{ or } |R| = 0$)  \\
\> \> return X = [pop(L), Merge($l_2 \ldots l_n$, R)]  \\
\> else ($\mbox{first}(L) > \mbox{first}(R) \mbox{ or } |L| = 0$)  \\
\> \> increment count by $|L|$  \\
\> \> return X = [pop(R), Merge(L, $r_2 \ldots r_m$)]  \\
End Merge  
\end{tabbing}

\subsection*{Time Complexity}

We have added a single step to {\sc Merge} which takes constant time, 
otherwise {\sc Mergesort} is the same as that given in the book, and 
it takes $O(n \log n)$ time.

\subsection*{Correctness}

Each inversion exists across one and only one merge and it is counted
once and only once in that merge.  Because a singleton cannot be an
inversion (which is by definition a pair of elements), all inversions
must at some point be merged together.  (Thus number counted is $\ge$
number inversions.)  At each merge there are three possible cases for
each inversion, both $x_i$ and $x_j$ are in the left half, both are in
the right half, or one is in the left and the other in the right half.
If the both elements of the inversion are in the left half then they
will be counted during the recursion on the left half, (likewise
during the recursion on the right half if they are both on the right
half).  If one is on each half then it will get counted in the merge
in question.

%\newpage
\section*{Problem 3b: Prove the number of inversions is equal to the
minimum number of swaps of adjacent elements required to sort the list.}

We will prove (A) the minimum number of swaps is $\le$ the number of
inversions and (B) the minimum number of swaps is $\ge$ the number of
inversions.  Thus, since the number of swaps is bounded on both sides
by the number of inversions, it must be equal to the number of
inversions.

\begin{itemize}
\item number of swaps $\le$ number of inversions

\begin{itemize}
\item If there is an inversion, then there are two adjacent
elements $x_i, x_{i+1}$ which form an inversion. 
If we swap these two elements, we decrement the number of inversions
by exactly 1. 
\item If the number of inversions is 0, then the list is sorted.
\end{itemize}

\item number of swaps $\ge$ number of inversions
\begin{itemize}
\item Each swap can decrement the number of inversions by at most
1. 
\item If the number of inversions is $>0$, then the list is not
sorted. 
\end{itemize}
\end{itemize}

Lemma 1: (By contradiction)  Assume that all adjacent elements are
in the correct order.  By transitivty, all elements are in the correct
order.  The list is sorted.  There are no inversions.  Contradiction.
Therefore if there are any inversions, at least one pair of adjacent
elements must be inverted.

Lemma 2: Let $x_i, x_{i+1}$ be an adjacent inversion.  Since the
relations ship between any other elements and each of these two
adjacent elements do not change when these two elements are swapped,
no other inversions are changed.  Thus one and only one inversion can
be removed by a swap of adjacent elements.

QED

\end{document}