% ---------
% Compile with "pdflatex hw0".
% --------
%!TEX TS-program = pdflatex
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage{tikz}
%!TEX encoding = UTF-8 Unicode
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{enumerate}
\usepackage{stmaryrd}
\def\Sym#1{\textbf{\texttt{\color{BrickRed}#1}}}
% ---------
% The next following lines change the default text and math fonts and
% make a few other minor cosmetic changes. If you get any error
% messages related to these packages, just comment them out. -- Jeff
% --------
\usepackage[charter]{mathdesign}
\usepackage{berasans,beramono}
\SetMathAlphabet{\mathsf}{bold}{\encodingdefault}{\sfdefault}{b}{\updefault}
\SetMathAlphabet{\mathtt}{bold}{\encodingdefault}{\ttdefault}{b}{\updefault}
\SetMathAlphabet{\mathsf}{normal}{\encodingdefault}{\sfdefault}{\mddefault}{\updefault}
\SetMathAlphabet{\mathtt}{normal}{\encodingdefault}{\ttdefault}{\mddefault}{\updefault}
\usepackage{microtype}
% ---------
% End of cosmetics.
% --------
% ---------
% Redefine suits
% --------
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}
% ---------
% Dashed lines in arrays
% --------
\usepackage{arydshln}
\dashlinedash 0.75pt
\dashlinegap 1.5pt
\hidesolutions
% =========================================================
\begin{document}
\headers{“CS 374”}{Homework 4}{Fall 2015}
\thispagestyle{empty}
\begin{center}
\LARGE
\textbf{“CS 374” Fall 2015 --- Homework 4}
\\
\Large Due Tuesday, October 6, 2015 at 10am
\end{center}
\bigskip
\bigskip
\bigskip
\hrule
\begin{center}
\Large \textbf{••• Some important course policies •••}\\
\end{center}
\hrule
\bigskip
\begin{itemize}
\item \textbf{You may work in groups of up to three people.} However, each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the names and NetIDs of each person contributing.
\item \textbf{You may use any source at your disposal}—paper,
electronic, or human—but you \EMPH{must} cite \EMPH{every} source
that you use. See the academic integrity policies on the course web
site for more details.
\item
\textbf{Submit your pdf solutions in Moodle.}
See instructions on the course website and submit a separate pdf
for each problem. Ideally, your solutions should be typeset in LaTex. If you hand write your homework make sure that the pdf scan is easy to read. Illegible scans will receive no points.
\item
\textbf{Avoid the Three Deadly Sins!} There are a few dangerous writing (and thinking) habits that will trigger an automatic zero on any homework or exam problem. Yes, we are completely serious.
\begin{itemize}\itemsep0pt
\item Give complete solutions, not just examples.
\item Declare all your variables.
\item Never use weak induction.
\end{itemize}
\item
Unlike previous editions of this and other theory courses we are not
using the “I don’t know” policy.
\end{itemize}
\bigskip
\hrule
\begin{center}
\large \textbf{See the course web site for more information.}\\[2ex]\normalsize
If you have any questions about these policies,\\
please don’t hesitate to ask in class, in office hours, or on Piazza.
\end{center}
\hrule
\vfil
\vfil
\vfil
\newpage
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil
%----------------------------------------------------------------------
\def\arraystretch{1.2}
%\hidesolutions
%----------------------------------------------------------------------
\item It is common these days to hear statistics about wealth inequality in
the United States. A typical statement is that the the top 1\% of
earners together make more than ten times the total income of the bottom
70\% of earners. You want to verify these statements on some data
sets. Suppose you are given the income of people as an $n$ element
\emph{unsorted} array $A$, where $A[i]$ gives the income of person
$i$.
\begin{itemize}
\item Describe an $O(n)$-time algorithm that given $A$ checks whether
the top 1\% of earners together make more than ten times the bottom
70\% together. Assume for simplicity that $n$ is a multiple of 100
and that all numbers in $A$ are distinct. Note that sorting $A$ will
easily solve the problem but will take $\Omega(n\log n)$ time.
\item More generally we may want to compute the total earnings of the
top $\alpha$\% of earners for various values of $\alpha$. Suppose we
are given $A$ and $k$ numbers $\alpha_1,\alpha_2,\ldots,\alpha_k$
each of which is a number between $0$ and $100$ and we wish to
compute the total earnings of the top $\alpha_i$\% of earners for
each $1 \le i \le k$. Describe an algorithm for this problem that
runs in $O(n \log k)$ time. Note that sorting will allow you to
solve the problem in $O(n \log n)$ time but when $k \ll n$, $O(n
\log k)$ is faster. Note that an $O(nk)$ time algorithm is relative
easy. {\em Hint:} first sort the $\alpha_i$'s.
\end{itemize}
You should prove the correctness of the second part of the problem.
It helps to write a recursive algorithm that you can use induction
to prove the correctness of.
%----------------------------------------------------------------------
\item Suppose you are given two sets of n points, one set $\{p_1, p_2,
\ldots, p_n\}$ on the line $y = 0$ and another set $\{q_1, q_2,
\ldots, q_n\}$ on the line $y = 1$. Create a set of $n$ line
segments by connecting each point $p_i$ to the corresponding point
$q_i$. Describe and analyze a divide-and-conquer algorithm to
determine how many pairs of these line segments intersect, in $O(n
\log n)$ time. See example below.
\begin{inline}
\includegraphics[height=1.25in]{intersecting-line-segments}\\
\end{inline}
No proof of correctness necessary but you should justify
the running time.
%----------------------------------------------------------------------
%----------------------------------------------------------------------
\item For this problem, a \emph{subtree} of a binary tree means any
connected subgraph. A binary tree is \emph{complete} if every
internal node has two children, and every leaf has exactly the same
depth. Describe and analyze a {\bf recursive} algorithm to compute the
\emph{largest complete subtree} of a given binary tree. Your
algorithm should return both the root and the depth of this subtree.
\begin{inline}
\includegraphics[height=1.25in]{completesubtree}\\
\end{inline}
You do not need to describe or analyze a memoized version of the algorithm.
Briefly justify the correctness of your algorithm by explaining the idea
behind the recursion.
\end{enumerate}
\end{document}
%----------------------------------------------------------------------