% Created 2018-11-07 Wed 18:37
\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}
\def\sopt{S_{\textit{\scriptsize opt}}}
\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 4}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs 25.2.2 (Org mode 8.2.10)}}
\begin{document}

\maketitle
\section{Nuts and bolts}
\label{sec-1}
\begin{enumerate}
\item In  the quiz, you investigated  two different algorithms for  the Nuts and
Bolts  problem:  algorithm  \verb~Nuts-and-Bolts~ is  simple  but  inefficient,
running in  $O(n^2)$ time  in both  the average case  and the  worst case.
Algorithm \verb~NB-Improved~  is much better, but  assumes irrealistically that
the nuts are given to you sorted by size.

After thinking about the  version of the problem where nuts  come in a bag
for a  while, you realize  that you might be  able to accomplish  the task
more efficiently by using the nut and  bolt you matched as a way to filter
the rest.

\begin{tabbing}
xxxxxxx\=xxx\=xxx\=xxx\=xxx\=xxxx\=xxxx\= \kill
\> {\bf Algorithm} NB-Quick(Nut-Set, Bolt-Set) \\
\>\> If Nut-Set is empty, then \\
\>\>\>   Return the empty set \\
\>\> Else If Nut-Set contains exactly one nut, say $N$, then \\
\>\>\>   Let $B$ be the single bolt in Bolt-Set \\
\>\>\>   Return $\{ (N,B) \}$ \\
\>\> Else \\
\>\>\>   Remove a nut, say $N$, from Nut-Set \\
\>\>\>   Partner-found $=$ False \\
\>\>\>   Tried-Bolts $= \emptyset$ \\
\>\>\>   While not Partner-found \\
\>\>\>\>    Remove any bolt, say $B$, from Bolt-Set \\
\>\>\>\>    If bolt $B$ threads into nut $N$ then \\
\>\>\>\>\>    Partner-found $=$ True \\
\>\>\>\>    Else \\
\>\>\>\>\>     Add $B$ to Tried-Bolts         \\
\>\>\>   For each nut in Nut-Set\\
\>\>\>\>    If the nut is too lose for $B$\\
\>\>\>\>\>    Add it to the set Loose-Nuts\\
\>\>\>\>  Else add it to the set Tight-Nuts\\
\>\>\>   For each bolt in Bolt-Set $\cup$ Tried-Bolts\\
\>\>\>\>    If the bolt is too large for $N$\\
\>\>\>\>\>    Add it to the set Large-Bolts\\
\>\>\>\>  Else add it to the set Small-Bolts\\
\>\>\> Return $\{ (N,B) \} \cup$ NB-Quick(Loose-Nuts, Large-Bolts)\\
\>\>\> \phantom{Return $\{ (N,B) \}$}$\cup$ NB-Quick(Tight-Nuts, Small-Bolts)
\end{tabbing}

Consider  the case  where,  at  every recursive  call,  both  of the  sets
Tight-Nuts and  Loose-Nuts have size  in the range $[n/k,  (k-1)n/k]$, for
some  integer $k  > 2$.  Write  a recurrence  relation that  gives a  good
asymptotic (big-$O$) \emph{upper-bound} on the  running time of this algorithm,
as a function of both $n$ and $k$.

\[
   T'(n) \le \left\{ \begin{array}{ll} 
                    c, \qquad \qquad \qquad \qquad\mbox{when $n=0$ or $n=1$} & \mbox{// base cases} \\[.3in]
                    \fillinblankmath{XXXXXXXXXXXXXXXXXX} & // \mbox{recursive case} \\
                    \end{array} \right.
   \]

\item Which of the following relationships holds between the function $T$
from question 1, and the function $T'$ from question 3 of the nuts
and bolts question from quiz 4?

\hspace{.5in}
$\fillinMCmath{T' \in o(T)}$   \hspace{.5in}
$\fillinMCmath{T' \in \Theta(T)}$   \hspace{.5in}
$\fillinMCmath{T' \in \omega(T)}$   \hspace{.5in}
\fillinMC{None of these hold}   \hspace{.5in}
\end{enumerate}
\newpage

\section{Array-chopping}
\label{sec-2}
An arithmetic  array is one  whose elements  form an arithmetic  sequence, in
order---i.e., they're arrays of the form $A = [a_1, a_1 + c, a_1 + 2c, \ldots
, a_1 + (n  - 1)c]$, where $A$ has length $n$ (for  $n \geq 2$). You're given
an arithmetic  array with $k$ elements  missing from somewhere in  the middle
(i.e., it's not the first or  last element that's been removed). For example,
the missing numbers in  $[3, 6, 12, 18, 24, 27]$ are $9$,  $15$ and $21$. The
missing numbers in $[1, 22, 29, 36]$ are $8$ and $15$.

\begin{enumerate}
\item Give an example that shows that if  you are not told what $k$ is, then you
can not determine $c$, no matter how many elements the array you are given
contains.

\item Suppose now  that you are not told  $k$, but you are given  an upper bound
$K$ on its value. You will be able to determine $c$ and $k$ as long as the
array you receive contains at least $f(K)$ elements. What is $f(K)$?

\[
   f(K) = \fillinblankmath{XXXXXXXX}
   \]

\item Describe an algorithm to compute the values of $c$ and $k$, assuming you
know $K$ and are given an array with at least $f(K)$ elements.

\item Finally suppose  that you  are told  what $k$  is. Describe  an efficient
algorithm that takes as input the array  and the value of $k$, and returns
an array containing all missing elements.

\item What is  the worst-case running time  of your algorithm, as  a function of
$k$ and the length $n$ of the array?
\end{enumerate}
\section{More longest common subsequences}
\label{sec-3}
An instance of the 3-sequence longest common subsequence problem
(3LLCS) consists of three sequences $x = x_1 x2 \ldots x_n$, $y = y_1
y_2 \ldots y_n$ and $z = z_1 z_2 \ldots z_n$; for simplicity we
assume that all are of the same length. The problem is to find the
length of the longest sequence that is a subsequence of all three
sequences. We denote this length by 3LLCS$(x,y,z)$.

\begin{enumerate}
\item What is 3LLCS(brute, force, searches)?

\item Give  a  recurrence that  expresses 3LLCS$(x,y,z)$  in terms  of 3LLCS  of
smaller strings.

\item Design a  polynomial-time, iterative,  dynamic programming  algorithm for
solving  this problem.  (You  may well  want to  first  design a  memoized
recursive  algorithm for  the problem,  but you  do not  need to  submit a
description of this algorithm.)

\item State  what is the running  time of your algorithm  of part 3 (you  do not
need to provide justification).

\item Describe  how to adapt  your algorithm so that  it returns the  the actual
longest  common subsequence  of the  three input  sequences (not  just the
length).

\item\relax [Bonus] Give an  example that proves that the LCS  of three sequences $x$,
$y$ and $z$ can be \textbf{neither} of LCS($x$, LCS($y$, $z$)), LCS($y$, LCS($x$,
$z$)), LCS($z$, LCS($x$, $y$)).
\end{enumerate}
\newpage

\section{DNA free energies}
\label{sec-4}
Free energy is a fundamental  property of DNA duplexes (double-stranded DNA),
and identifying collections  of DNA strands with a particular  free energy is
useful in many biotechnologies. You will  tackle a simplified version of this
problem here.

\begin{itemize}
\item Let $s = s_1 s_2 \ldots s_n$ be a string over the alphabet $\{A,C,G,T\}$.
(The string represents  a DNA sequence, which can form  a duplex with its
Watson-Crick  complement,  but  these  details  need  not  concern  you.)
Throughout assume that $n \ge 2$.

\item Let $F$ be a table $F[x:y]$ of 16 nonnegative parameters, where $x,y
    \in \{A,C,G,T\}$.

\item Let $\Delta G(s)$ be the sum
\[
    F[s_1:s_2] + F[s_2:s_3] + \ldots + F[s_{n-1}:s_n].
    \]
For example, if some of the table entries are as follows;
\[
    F[A:A] = 2, \;\;\; F[A:C] = 3, \;\;\; F[C:T] = 7, \;\;\;
    F[T:A] = 4, \;\;\; F[C:G] = 12,
    \]
then $\Delta G(AACTACG) = 31$, $\Delta G(CT) = 7$, and $\Delta G(AAA) = 4$.

\item For any integer $g$, let $\#\Delta(n,g)$ be the total number of
length-$n$ strings over alphabet $\{A,C,G,T\}$ that have $\Delta G = g$.

\item Let $\#\Delta(n,g,X)$ be the total number of length-$n$ strings $s$ that
start with the letter $X$ and have $\Delta G(s) = g$.
\end{itemize}


\begin{enumerate}
\item Which of the following recurrences is correct for $\#\Delta(n,g,X)$?
You do not need to explain your answer here, just circle which option
you believe to be correct.  Assume that for all of the cases, the
base conditions are

\[
\#\Delta(n,g,X) =
\left\{
\begin{array}{ll}
0, & \mbox{ if $n \ge 2$ and $g < 0$},  \\
\mbox{the number of table entries $F[X:Y]$ that have value $= g$}, &\mbox{ if $n = 2$ and $g \ge 0$}.
\end{array}
\right.
\]

$\fillinMCmath{\#\Delta(n,g,X) = \displaystyle{\sum_{Y \in \{A,C,G,T\}}}\#\Delta(n-1, g - F[X:Y], Y), \;\;n > 2, g \ge 0}$

$\fillinMCmath{\#\Delta(n,g,X) = \displaystyle{\sum_{Y \in \{A,C,G,T\}}}(F[X:Y] + \#\Delta(n-1, g - F[X:Y], Y)), \;\; n > 2, g \ge 0}$

$\fillinMCmath{\#\Delta(n,g,X) = \displaystyle{\sum_{Y \in \{A,C,G,T\}}}\#\Delta(n-2, g - F[X:Y], Y), \;\; n > 2, g \ge 0}$

$\fillinMCmath{\#\Delta(n,g,X) = \displaystyle{\sum_{Y \in \{A,C,G,T\}}}(F[X:Y] + \#\Delta(n-2, g - F[X:Y], Y)), \;\; n > 2, g \ge 0}$

\item Give an expression for $\#\Delta(n,g)$ in terms of $\#\Delta(n,g,X), X \in \{A,C,G,T\}$.

\item Design a memoized recursive algorithm that computes $\Delta(n,g,X)$ when $n \ge 2$ and $X \in \{A,C,G,T\}$.
Your algorithm should have running time $O(ng)$.

\item Explain why the running time of your algorithm is $O(ng)$.
\end{enumerate}
% Emacs 25.2.2 (Org mode 8.2.10)
\end{document}