% -*- compile-command: "rubber -d hw.6.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace}
\usepackage[linesnumbered,ruled]{algorithm2e}
% \usepackage[left=.75in,top=.75in,right=.75in,bottom=.75in]{geometry}

\usepackage{qrcode, enumitem}

\pagestyle{fancy}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 280: Algorithms -- Spring 2016}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 6}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, March 4}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\begin{question} \label{q:alg-choice} Suppose you are choosing between
  the following three algorithms:
\begin{enumerate}
\item Algorithm A solves problems by dividing them into five
  subproblems of half the size, recursively solving each subproblem,
  and then combining the solutions in linear time.
\item Algorithm B solves problems of size $n$ by recursively solving
  two subproblems of size $n-1$ and then combining the solutions in
  constant time.
\item Algorithm C solves problems of size $n$ by dividing them into
  nine subproblems of size $n/3$, recursively solving each subproblem,
  and then combining the solutions in $O(n^{2})$ time.
\end{enumerate}
What are the running times of each of these algorithms (in asymptotic
notation) and which would you choose?
\end{question}

\begin{question}[K\&T 5.1]
You are interested in analyzing some hard-to-obtain data from two
separate databases.  Each database contains $n$ numerical values---so
there are $2n$ values total---and you may assume that no two values
are the same.  You'd like to determine the median of this set of $2n$
values, which we define to be the $n$th smallest value.

However, the only way you can access these values is through
\emph{queries} to the databases.  In a single query, you can specify a
value $k$ to one of the two databases, and the chosen database will
return the $k$th smallest value that it contains.  Since queries are
expensive, you would like to compute the median using as few queries
as possible.

Give an algorithm that finds the median value using at most $O(\log
n)$ queries.
\end{question}


\begin{question} \label{q:fib}
  Recall that the \emph{Fibonacci numbers} $F_n$ are defined
  recursively by
  \begin{align*}
    F_0 &= 0 \\
    F_1 &= 1 \\
    F_n &= F_{n-1} + F_{n-2},
  \end{align*}
  with the first few given by $0,1,1,2,3,5,8,13,21,34,55,\dots$  You
  may assume the following facts:
  \begin{itemize}
  \item $F_n$ is $O(\phi^n)$ (where $\phi$ is the golden ratio,
    $(1+\sqrt 5)/2$).
  \item In addition to their definition, Fibonacci numbers satisfy the
    following recurrences:
    \begin{align*}
      F_{2n+1} & = F_n^2 + F_{n+1}^2 \\
      F_{2n} &= 2F_n F_{n+1} - F_n^2
    \end{align*}
  \end{itemize}
  Design an efficient algorithm to compute $F_n$, and analyze its
  running time.  Be careful to include the time needed for any
  multiplications and additions; since the algorithm may need to deal
  with very large numbers, you may \emph{not} assume that arithmetic
  operations take $O(1)$ time.

  \marginnote{\emph{\ref{q:fib}}\quad\qrcode{First,\ determine\ the\
      number\ of\ bits\ needed\ to\ represent\ F_n.}}
\end{question}

\begin{question} \label{q:maj} An array $A[1\ldots n]$ is said to have
  a {\em majority element} if more than half of its entries are the
  same.  Given an array, the task is to design an efficient algorithm
  to tell whether the array has a majority element, and, if so, to
  find that element.  The elements of the array are \emph{not}
  necessarily from some ordered domain like the integers, and so there
  can be no comparisons of the form $A[i] > A[j]$.  You should think
  of the array elements as, say, JPEG files.  However, you {\em can}
  answer questions of the form: $A[i] = A[j]$ in $O(1)$ time.

  \begin{enumerate}[label=(\alph*)]
  \item Show how to solve this problem in $O(n \log n)$
    time. \marginnote{\emph{\ref{q:maj}a}\quad\qrcode{Split\
        the\ array\ into\ two\ equal-size\ subarrays.\ Would\ it\
        help\ to\ know\ their\ majority\ elements?}}  Make sure to
    prove that your algorithm is correct (via induction) and give a
    recurrence relation for the running time of your algorithm.

    \item Can you give a linear-time algorithm?
      \marginnote[1in]{\emph{\ref{q:maj}b}\quad\qrcode{Pair\ up\ A's\
          elements.\ \ For\ each\ pair,\ if\ the\ two\ elements\ are\
          different,\ discard\ both\ of\ them;\ if\ they\ are\ the\
          same,\ keep\ just\ one.\  Show\ that\ afterwards,\ there\
          are\ at\ most\ n/2\ elements\ left,\ and\ that\ they\ have\
          a\ majority\ element\ if\ A\ does.}}
\end{enumerate}
\end{question}

\subsection*{Extra Credit}


This question adapted from the Design and Analysis of Algorithms
course at the University of Konstanz by Dr. Ulrik Brandes and
Dr. Sabine Cornelsen.

\begin{question}[Least Common Ancestor] \label{q:lca} Let $T =(V,E)$
  be an oriented tree with root $r \in V$ and let $P \subseteq \{
  \{u,v\} \,|\, u,v \in V \}$ be a set of unordered pairs of
  vertices. For each $v \in V$ let $\Pi_{v} = \{r, . . . , v\}
  \subseteq V$ denote the sequence of vertices along the path from $r$
  to $v$ and let $d(v) = |\Pi_{v}| - 1$ denote the depth of $v \in T$.
  The {\em least common ancestor} of pair $\{u,v\} \in P$ is defined
  as $\overline{w} \in V$ with $\overline{w} \in \Pi_{v} \cap \Pi_{u}$
  and $d(\overline{w}) > d(w)$ for all $w \in \Pi_{v} \cap \Pi_{u}$.

  Algorithm LCA($r$) traverses $T$ to determine the least common
  ancestors of all pairs $\{u, v\} \in P$ . At the beginning, all
  vertices are unmarked.

\begin{algorithm}[H]
\SetKwFunction{ms}{Makeset}
\SetKwFunction{union}{Union}
\SetKwFunction{find}{Find}
\SetKwData{anc}{ancestor}

\ms($u$) \\
$\anc[\find(u)] \longleftarrow u$\\
\ForEach{child $v$ of $u$ in $T$} {
	LCA($v$) \\
	$\union(\find(u), \find(v))$ \\
	$\anc[\find(u)] \longleftarrow u$}
mark $u$ \\
\ForEach{$v$ with $\{u,v\} \in P$}{
	\If{$v$ is marked}{
		print ``LCA('' + $u$ + ``,'' + $v$ + ``) is'' + $\anc[\find(v)]$
	}
}
\caption{LCA($u$)}
\end{algorithm}

\begin{enumerate}[label=(\alph*)]
\item Show that, when Line 8 in LCA($u$) is executed, the set {\sc
    Find($u$)} contains all vertices of the subtree $T_{u} \subseteq
  T$ with root $u$.

  \marginnote{\emph{\ref{q:lca}a}\quad\qrcode{Do\ an\ induction\
      on\ the\ height\ h(u)\ of\ u.\ (h(u)\ =\ 0\ if\ u\ is\ a\
      leaf.)}}
\item Show that the number of sets in the Union-Find data structure at
  the time of a call to LCA($v$) equals $d(v)$.

  \marginnote[1in]{\emph{\ref{q:lca}b}\quad\qrcode{The\ recursive\ calls\
      of\ LCA\ specify\ a\ traversal\ order\ of\ T\ which\ induces\
      an\ order\ on\ V.\ Do\ an\ induction\ on\ the\ position\ of\ v\
      in\ this\ order.}}

\item Prove that LCA($r$) determines the least common ancestors of all
  $\{u, v\} \in P$ correctly.

  \marginnote[1in]{\emph{\ref{q:lca}c}\quad\qrcode{Differentiate\ two\
      cases:\ when\ one\ of\ u,\ v\ is\ in\ the\ other's\ subtree;\
      and\ when\ neither\ is\ in\ the\ other's\ subtree.}}
\item[(d)] Analyze the running time of LCA($r$).
\end{enumerate}

\end{question}

\end{document}
