% Created 2018-10-18 Thu 07:53
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\usepackage{csquotes}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{algpseudocode}
\usepackage[margin=0.75in]{geometry}
\usepackage{nth}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,shapes.misc,calc,arrows,patterns,decorations.pathreplacing}
\usepackage{ccicons}
\usepackage{calc}
\usepackage{fancyhdr}
\usepackage{fancyvrb}
\usepackage{hyperref}
\usepackage{nopageno}
\usepackage{enumitem}
\usepackage{multicol}
\usepackage{braket}
\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}
\setlength{\columnseprule}{1pt}
\newcommand{\bonusmarksamt}[1]{\textbf{[#1~BONUS~marks]}}
\newcommand{\bonusmarkamt}[0]{\textbf{[1~BONUS~mark]}}
\newcommand{\marksamt}[1]{\textbf{[#1~marks]}}
\newcommand{\markamt}[0]{\textbf{[1~mark]}}
\newcommand{\fillinMC}[1]{\fillinMCmath{\mbox{#1}}}
\newcommand{\fillinMCmath}[1]{\begin{tikzpicture}\draw circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCsoln}[1]{\fillinMCmathsoln{\mbox{#1}}}
\newcommand{\fillinMCmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCAll}[1]{\fillinMCAllmath{\mbox{#1}}}
\newcommand{\fillinMCAllmath}[1]{\begin{tikzpicture}\draw (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinMCAllsoln}[1]{\fillinMCAllmathsoln{\mbox{#1}}}
\newcommand{\fillinMCAllmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinblank}[1]{\fillinblankmath{\mbox{#1}}}
\newcommand{\fillinblankmath}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{\LARGE\phantom{#1}}\endgroup}
\newcommand{\fillinblanksoln}[1]{\fillinblankmathsoln{\mbox{#1}}}
\newcommand{\fillinblankmathsoln}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{{#1}}\endgroup}
\newcommand{\answerbox}[1][3\baselineskip]{%
\noindent\setlength{\fboxrule}{2pt}\framebox[0.7\linewidth]{%
\raisebox{2pt}[0pt][#1]{}%
}\par\medskip%
}
\usepackage{collcell,array}
\newcommand{\shiftdown}[1]{\smash{\raisebox{-.5\normalbaselineskip}{#1}}}
\newcolumntype{C}{>{\collectcell\shiftdown}c<{\endcollectcell}}
\newcommand{\shiftup}[1]{\smash{\raisebox{.5\normalbaselineskip}{#1}}}
\def\sequence#1#2{\dsequence{#1}{1}{#2}}
\def\dsequence#1#2#3{#1_{#2}, \ldots, #1_{#3}}
\newtheorem{fact}{Fact}
\def\imax{$\texttt{S}_{\max}$}
\def\iprevmax{previous\_$\texttt{S}_{\max}$}
\def\deleted{\texttt{covered}}
%\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International License. \ccby}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
\makeatletter
\def\@myproof#1[#2]{\trivlist \item [\hskip\labelsep{\bf #1 {#2}: }]}
\def\@begproof#1{\@ifnextchar[{\@myproof{#1}}{\@myproof{#1}[\unskip$\,$]}}
\newenvironment{solution}{\vskip -10pt\leavevmode\@begproof{Solution}}{\endtrivlist}
\makeatother
\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by-nc/4.0/}{Creative Commons Attribution-NonCommercial 4.0 International License. \ccbync}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
\usepackage{mdframed}
\BeforeBeginEnvironment{minted}{\begin{mdframed}}
\AfterEndEnvironment{minted}{\end{mdframed}}
\date{\today}
\title{CPSC 320 2018W1: Assignment 3}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs 25.2.1 (Org mode 8.2.10)}}
\begin{document}

\maketitle
Please submit this assignment via \href{https://gradescope.com/}{GradeScope} at
\url{https://gradescope.com}. Be sure to identify everyone in your group if
you're making a group submission. (Reminder: groups can include a
maximum of three students; we strongly encourage groups of two.)

Submit by the deadline \textbf{Saturday October 27, 2018 at 10PM}. For credit, 
your group must make a \textbf{single} submission via one group member's account,
marking all other group members in that submission \textbf{using GradeScope's
interface}. Your group's submission \textbf{must}:
\begin{itemize}
\item Be on time.
\item Consist of a single, clearly legible file uploadable to GradeScope
with clearly indicated solutions to the problems. (PDFs produced via
\LaTeX{}, Word, Google Docs, or other editing software work
well. Scanned documents will likely work well. \textbf{High-quality}
photographs are OK if we agree they're legible.)
\item Include prominent numbering that corresponds to the numbering used
in this assignment handout (not the individual quizzes). Put
these \textbf{in order} starting each problem on a new page, ideally. If
not, \textbf{very clearly} and prominently indicate which problem is
answered where! When uploading assignments to gradescope,
marks will be docked if pages are not properly assigned to each question.
\item Include at the start of the document the \textbf{ugrad.cs.ubc.ca e-mail
addresses} of each member of your team. (Please do \textbf{NOT} include
your name on the assignment, however.\footnote{If you don't mind private
  information being stored outside Canada and want an extra
  double-check on your identity, include your student number rather
  than your name.})
\item Include at the start of the document the statement: "All group
members have read and followed the \href{http://blogs.ubc.ca/cpsc3202017W1/syllabus/#conduct}{guidelines for academic conduct
in CPSC 320}. As part of those rules, when collaborating with anyone
outside my group, (1) I and my collaborators took no record but
names (and GradeScope information) away, and (2) after a suitable
break, my group created the assignment I am submitting without help
from anyone other than the course staff." (Go read those
guidelines!)
\item Include at the start of the document your outside-group
collaborators' ugrad.cs.ubc.ca IDs, but \textbf{not} their names. (Be sure
to get those IDs when you collaborate!)
\end{itemize}

Before  we  begin, a  few  notes  on  pseudocode  throughout CPSC  320:  Your
pseudocode need  not compile in  any language,  but it must  communicate your
algorithm  clearly,  concisely,  correctly, and  without  irrelevant  detail.
Reasonable  use of  plain  English is  fine in  such  pseudocode. You  should
envision your  audience as  a capable  CPSC 320  student unfamiliar  with the
problem you are solving. If you choose  to use actual code, note that you may
\textbf{neither} include what we consider to  be irrelevant detail \textbf{nor} assume that
we understand  the particular language  you chose.  (So, for example,  do not
write  \texttt{\#include <iostream>}  at  the  start of  your  pseudocode, and  avoid
idiosyncratic    features   of    your   language    like   Java's    ternary
(question-mark-colon) operator.)

\medskip

\section{Hi Ho, hi ho, we are digging the road}
\label{sec-1}
Recall that the city of Vancouver needs to dig up many roads during the summer in order to
replace  ageing water  pipes. There  are pipes  along $n$  road segments  that need  to be
replaced in a given summer. The process of replacing a pipe consists in
\begin{itemize}
\item first digging a hole
\item then performing the replacement
\item and finally filling in the hole and repaving
\end{itemize}
We will assume all holes  have been dug by the beginning of the  summer. The third part of
the job can be done  by any one of a large number of teams, and  can be performed fully in
parallel. However  the task  of actually  replacing the  pipes requires  a high  degree of
specialization, and hence there is only one team in the city that is capable of performing
it.

Let  us call  the road  segments $R_1,  \ldots R_n$,  and suppose  the job  on road  $R_i$
requires $s_i$ hours  of time for the first  task, and $t_i$ hours of time  for the second
task. Since there is only one team capable  of performing the replacement of the old water
pipes, city managers need  to work out an order in which this  team will replace the pipes
on the $n$  road segments. As soon as  the replacement on one road segment  is complete, a
team in charge of refilling the hole and repaving the road can be called in.

Let us  say that a  \emph{schedule} is an  ordering of the  jobs for the  pipe replacement
team, and  the \emph{completion time} of  the schedule is  the earliest time at  which all
pipes have been  replaced and all roads  restored to their initial  condition (or better).
This is an important  quantity to minimize, since users tend to get  upset when roads have
large holes in them.

In  quiz 3,  you saw  that we  can  obtain an  optimal schedule  by ordering  the jobs  by
decreasing $t_i$ value (that  is, starting with the job whose $t_i$  value is the largest,
etc). To simplify notation,  let us assume that $R_i$ is the  job with the $i^{\scriptsize
th}$ largest  $t_i$ value. That is,  assume that $t_1 \ge  t_2 \ge \cdots \ge  t_{n-1} \ge
t_n$.

\begin{enumerate}
\item Prove that there is an optimal schedule  whose first job \textbf{is} job $R_1$. Hint: consider
what happens if you have an optimal schedule whose first job is not $R_1$, and then you
swap two (carefully chosen) jobs.

\item Using your result from question 1 and mathematical induction, prove that ordering the
job by decreasing $t_i$ value is guaranteed to return an optimal solution.
\end{enumerate}
\section{Lowest common ancestor}
\label{sec-2}
Recall that in a tree rooted at a node $r$, a node $v$ is an \emph{ancestor} of
node  $i$ (where $v$ and $i$ may be equal) if $v$  is on the  path from $r$ to  $i$. Node $v$  is a
\emph{common ancestor} of  nodes $i$ and $j$  if $v$ is an ancestor  of $i$ and
$v$ is also  an ancestor of $j$.  The \emph{lowest common ancestor}  of $i$ and
$j$  is  the common  ancestor  of  $i$ and  $j$  with  the largest  depth.
Biologists are interested  in finding the lowest common  ancestor of pairs
of nodes in trees that model evolutionary relationships among organisms.

On the quiz,  you derived a $\Theta(n)$ algorithm that  takes two node $i$
and $j$ of a tree, and  finds their lowest common ancestor. Unfortunately,
calling  the \verb~Lowest-Common-Ancestor~  algorithm  repeatedly on  different
pairs of nodes will quickly become  inefficient, because a lot of the work
of traversing the tree is repeated each time.

It is  possible to pre-process  the tree  so that, after  $\Theta(n)$ time
pre-processing to build  a data structure that uses  $\Theta(n)$ space, we
can find  the lowest  common ancestor  of two  given nodes $i$ and  $j$ in
$\Theta(d)$ time in the worst case, where $d$ is the depth of the tree.

\begin{enumerate}
\item Describe  the data  structure you will  build, and show  why it  can be
constructed in $\Theta(n)$ time. Hint:  parent pointers may be helpful,
but not sufficient.

\item Now   rewrite  the   \verb~Lowest-Common-Ancestor~  algorithm  to   run  in
$\Theta(d)$ time in the worst case, given the pre-processed tree 
data structure..
\end{enumerate}
\section{Hamming distance}
\label{sec-3}
Let $x$ and $y$ be binary strings of length $n$.  The
\emph{Hamming Distance} between $x$ and $y$, denoted by $H(x,y)$, is
the number of positions where $x$ and $y$ disagree.  That is, if $x
= x_1x_2\ldots x_n$ and $y = y_1y_2\ldots y_n$ then $H(x,y)$ is the
number of positions $i$ for which $x_i \not = y_i$. Sets of strings
that have high Hamming distance from each other are useful as a means
for information encoding in a situation where bits can get corrupted.

A $S$ set of binary strings of length $n$ is an $(n,d)$ \emph{Hamming set}
if the Hamming distance between any pair of strings in $S$ is at least
$d$.

\begin{enumerate}
\item Describe how to construct a $(n,2)$ Hamming set of size
$\Omega(4^{n/3})$. (Hint: there is a construction that is
similar to, but better than, that given in the quiz solution.)

\item For $0\le i \le 2^n-1$, let $s_i$ be the binary string of length
$n$ which encodes the nonnegative number $i$ in binary. For
example, if $n=4$ then $s_0 = 0000$, $s_1 = 0001$, $s_2 = 0010$,
and so on.

Let Set($n,i,d$) be the set of $i'$ in the range 0 to $2^n-1$ such
that $H(s_i,s_{i'}) < d$.  Explain why the size of Set($n,i,d$) is
independent of $i$.

\item The following variant of Algorithm Hamming-Set from the quiz is
essentially the same as an algorithm described in a 1997
U.S. patent by biologist and Nobel Prize winner Sydney Brenner
(patent number 5,604,097, ``Methods for Sorting Polynucleotides
Using Oligonucleotide Tags'').

\begin{tabbing}
xxxxxxx\=xxx\=xxx\=xxx\=xxx\=xxxx\= \kill
\>{\bf Algorithm} Brenner-Hamming-Set($n$,$d$) \\
\>    \\
\>\>   Initialize $M$ to be a list of the $2^n$ binary strings of length n (in arbitrary order) \\
\>\>   $i = 1$ \\
\>\>   Repeat \\
\>\>\>   Set $M$-old to be equal to the list $M$ \\
\>\>\>   Let $s$ be the $i$th string in $M$ \\
\>\>\>   For each string $s'$ occurring after string $s$ in $M$ \\
\>\>\>\>    If $H(s,s') < d$ then remove $s'$ from $M$ \\
\>\>\>   $i$++ \\
\>\>\> Until ($M$-old = $M$) or ($i$ is greater than the size of $M$) \\
\>\>\> Return $M$ \\
\end{tabbing}

Describe an input $(n,d)$ and an initial list $M$ on which
Algorithm Brenner-Hamming-Set($n$,$d$) produces an output that is
\emph{not} a $(n,d)$-Hamming set. Show what the output is. (Brenner
would have benefited from having a CPSC 320 student in his lab!).
\end{enumerate}
\clearpage
\section{Pell numbers}
\label{sec-4}
The infinite sequence of rational approximations to the square root of
2 starts with the numbers 1/1, 3/2, 7/5, 17/12, and 41/29. The
infinite sequence of denominators of this sequence is called the Pell
sequence, so the Pell number sequence begins with 1, 2, 5, 12, and 29.
The Pell numbers are also defined by the following recurrence relation:

\[
P_n = \left\{
\begin{array}{ll}
0, & if n=0, \\
1,  & if n=1, \\
2P_{n-1} + P_{n-2}, & \mbox{otherwise}.
\end{array}
\right.
\]

\begin{enumerate}
\item Use induction to show that

\[
P_n = \frac{(1+\sqrt{2})^n - (1 - \sqrt{2})^n}{2\sqrt{2}}.
\]

\item Write a recursive algorithm Pell($n$) that returns the $n$ th Pell
number.

\item Write a recurrence relation that describes the running time of your
algorithm as a function of $n$.

\item Describe the solution to the recurrence  from part (3) in terms of another
sequence  of numbers  you are  almost certainly  already familiar  with (a
closed form  formula for  the $n^{\textit{\scriptsize  th}}$ term  of that
sequence is easily found online).
\end{enumerate}
% Emacs 25.2.1 (Org mode 8.2.10)
\end{document}
