\documentstyle [12pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ignore}[1]{}
\newcommand{\remark}[1]{[{\small{\bf Editorial Remark: }#1}]}


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

\begin{document}
\sloppy

{\large
CMU 15-451 \hfill PROBLEM SET \# 3 \hfill FALL 1993
\begin{center}
DUE: Thursday 23 September 1993 \\
3 problems
\end{center}}

\section*{Problem 1 \quad CLR 10-1.a-c}
\noindent
{\bf Largest $i$ numbers in sorted order}

\noindent
Given a set of $n$ numbers, find the $i$ largest in sorted order using
a comparison based algorithm.  Find the algorithm that implements each
of the following methods with the best asymptotic wordt-case running
time, and analyze the running times of the methods in terms of $n$ and
$i$.

\begin{itemize}

\item[{\bf a.}] Sort the numbers and list the $i$ largest.

\item[{\bf b.}] Build a priority queue from the numbers and call {\sc
Extract-Min} $i$ times.

\item[{\bf c.}] Use an order-statistic algorithm to find the $i$th largest
number, partition, and sort the $i$ largest numbers.

\end{itemize}

\section*{Problem 2 \quad CLR 10-2.a-c}

\noindent
{\bf Weighted median}

\noindent
For $n$ distinct elements $x_1, x_2, \ldots, x_n$ with positive weights
$w_1, w_2, \ldots, w_n$ such that $\sum_{i=1}^n w_i = 1$, the {\em
weighted median} is the element $x_k$ satisfying 
$$ \sum_{x_i<x_k} w_i \le \frac{1}{2}  \mbox{\hspace{1 in} and \hspace{1 in}}
\sum_{x_i>x_k} w_i \le \frac{1}{2} $$.

\begin{itemize}

\item[{\bf a.}] Argue that the median of $x_1, x_2, \ldots, x_n$ is the
weighted median of the $x_i$ with weights $w_i = 1/n$ for
$i=1,2,\ldots, n$.

\item[{\bf b.}] Show how to compute the weighted median of $n$ elements in
$O(n \log n)$ worst case time using sorting.

\item[{\bf c.}] Show how to compute the weighted median in $\Theta(n)$
worst-case time using a linear-time median algorithm such as {\sc
Select} from Section $10.3$.

\end{itemize}

\section*{Problem 3}

\noindent
{\bf Inversions and sorting}

Given $n$ distinct elements $x_1, x_2, \ldots, x_n$, an inversion is a
pair of elements $x_i, x_j \mbox{$(1 \le i < j \le n)$}$ such that $x_i > x_j$.
In other words, the number of inversions is the number of pairs in the
wrong order.

\begin{itemize}

\item[{\bf a.}] Prove that the number of inversions is equal to the minimum
number of swaps of adjacent elements required to sort $x_1, x_2,
\ldots, x_n$.

\item[{\bf b.}] Give an algorithm to compute the number of inversions in
$x_1, x_2, \ldots, x_n$ in $O(n \log n)$ worst-case time.
(Hint: consider a variant of merge sort.)

\end{itemize}

\end{document}