% Created 2017-11-02 Thu 07:43 \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{algpseudocode} \usepackage[margin=0.75in]{geometry} \usepackage{nth} \usepackage{tikz} \usetikzlibrary{positioning,chains,fit,shapes,calc,arrows} \usepackage{ccicons} \usepackage{fancyhdr} \usepackage{hyperref} \usepackage{nopageno} \usepackage{enumitem} \usepackage{multicol} \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{\fillinMCAll}[1]{\fillinMCAllmath{\mbox{#1}}} \newcommand{\fillinMCAllmath}[1]{\begin{tikzpicture}\draw (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% } \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} %\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} \date{\today} \title{CPSC 320 2017W1: Assignment 4} \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 (which we encourage!). Submit by the deadline \textbf{Friday 17 Nov 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! \item Include at the start of the document the \textbf{ugrad.cs.ubc.ca e-mail addresses} of each member of your team. (No names are necessary.) \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 e-mail addresses. (Be sure to get those when you collaborate!) \end{itemize} \section{Making Every Second Count} \label{sec-1} Aconcagua.ca sells storage on both an auction and fixed-price basis. They want to use historical auction data to investigate their fixed price choices. For $n$ seconds, they have the price point reached in each second in their auctions. They want to find the largest price-over-time stretch in their data. That is, given an array $A$ of $n$ price points, they want to find the largest possible value of $f(i,d) = d*\min(A[i],A[i+1],\ldots,A[i+d-1])$ where $i$ is the index of the left end of a stretch of seconds, $d$ is the duration in seconds of that stretch, and so the function $f$ computes the duration multiplied by the minimum price over that period. (Prices are positive, $d \geq 0$, for all values of $i$, $f(i,0) = 0$, and for legal indexes $i$ into $A$, $f(i,1) = A[i]$.) For example, the best stretch is underlined in the following price array: $[8, 2, \underline{9, 5, 6, 5}, 3, 1]$. Using 1-based indexing, the value for this optimal stretch starting at index 3 and running for 4 seconds is $f(3,4) = 4*\min(9, 5, 6, 5) = 4*5 = 20$. \begin{enumerate} \item Write out two trivial instances of the Aconcagua problem. \begin{enumerate} \item First instance: \item Second instance: \end{enumerate} \item Fill in the blanks below with the optimal values for $i$ and $d$, and $f(i, d)$ in each array. You \textbf{MUST} use 1-based indexing. (The first element of each array has an index of 1.) \begin{enumerate} \item $[1, 9, 4, 7, 4, 2, 8]$ Value of $i$: \fillinblank{MM} \medskip Value of $d$: \fillinblank{MM} \medskip Value of $f(i,d)$: \fillinblank{MM} \medskip \item $[18, 6, 8, 3, 4, 5, 11]$ Value of $i$: \fillinblank{MM} \medskip Value of $d$: \fillinblank{MM} \medskip Value of $f(i,d)$: \fillinblank{MM} \medskip \item $[2, 2, 2, 2]$ Value of $i$: \fillinblank{MM} \medskip Value of $d$: \fillinblank{MM} \medskip Value of $f(i,d)$: \fillinblank{MM} \medskip \end{enumerate} \item Fill in \textbf{best} choice of circles among each set below to complete design of a \textbf{brute force} algorithm to solve the "Aconcagua" problem and analyse its runtime in terms of $n$, the length of $A$. A valid solution to the Aconcagua problem is \begin{tabular}{l} $\fillinMC{a pair of values for i and d}$\\ $\fillinMC{a value for f(i, d)}$\\ $\fillinMC{a subset of A}$\\ \end{tabular} . However, a better quantity to consider in designing a brute force approach is \begin{tabular}{l} $\fillinMC{a pair of values for i and d}$\\ $\fillinMC{a value for f(i, d)}$\\ $\fillinMC{a subset of A}$\\ \end{tabular} . There are \begin{tabular}{l} $\fillinMCmath{O(n)}$\\ $\fillinMCmath{O(n\lg n)}$\\ $\fillinMCmath{O(n^2)}$\\ $\fillinMCmath{O(n^3)}$\\ $\fillinMCmath{O(2^n)}$\\ \end{tabular} of these quantities. Given a candidate quantity, a brute force approach to computing its $f$ value would take \begin{tabular}{l} $\fillinMCmath{O(1)}$\\ $\fillinMCmath{O(d)}$\\ $\fillinMCmath{O(f)}$\\ $\fillinMCmath{O(i)}$\\ $\fillinMCmath{O(n)}$\\ \end{tabular} to run. Overall the resulting natural brute force algorithm will take \begin{tabular}{l} $\fillinMCmath{O(n)}$\\ $\fillinMCmath{O(n\lg n)}$\\ $\fillinMCmath{O(n^2)}$\\ $\fillinMCmath{O(n^3)}$\\ $\fillinMCmath{O(2^n)}$\\ \end{tabular} time to run, which is \begin{tabular}{l} $\fillinMC{polynomial}$\\ $\fillinMC{exponential}$\\ \end{tabular} . \bigskip \item Consider again the example array: $[8, 2, 9, 5, 6, 5, 3, 1]$. Imagine that you are told that the solution \textbf{must} use the elements at indexes 4 and 5 (i.e., elements 5 and 6, using 1-based indexing). You begin by considering the smallest stretch of the array that includes these two elements: $i=4, d=2$ (i.e., elements 5 and 6 only) and repeatedly expand that candidate "stretch" to include one more element either to the left or right of the existing stretch while maintaining the invariant that the stretch you have chosen is the best of that length (value of $d$) that includes indexes 4 and 5 until the stretch includes the entire array. Finish the following table describing this expansion, thinking carefully about why you make the choice you do at each point: \begin{center} \begin{tabular}{rrrr} $i$ & $d$ & minimum & $f(i,d)$\\ \hline 4 & 2 & 5 & 10\\ 3 & 3 & 5 & 15\\ 3 & 4 & 5 & 20\\ $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$\\ $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$\\ $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$ & $\fillinblank{M}$\\ 1 & 8 & 1 & 8\\ \end{tabular} \end{center} \end{enumerate} \subsection{Quiz Solution} \label{sec-1-1} \begin{enumerate} \item There are many reasonable trivial solutions to the problem. For example: \begin{itemize} \item A length 0 array has a maximum $f$ value of 0. \item A length 1 array has a maximum $f$ value of $A[1]$. \item An array of any length $n \geq 1$ filled with all identical elements has a maximum $f$ value of $A[1] * n$. (You may or may not consider that last trivial.) \end{itemize} \item \begin{enumerate} \item $[1, \underline{9, 4, 7, 4}, 2, 8]$ $i = 2, d = 4, f(i,d) = 16$ \item $[\underline{18, 6, 8, 3, 4, 5, 11}]$ $i = 1, d = 7, f(i,d) = 21$ \item $[\underline{2, 2, 2, 2}]$ $i = 1, d = 4, f(i,d) = 8$ \end{enumerate} \item A valid solution to the Aconcagua problem is \textbf{a value for $f(i, d)$}. However, a better quantity to consider in designing a brute force approach is \textbf{a pair of values for $i$ and $d$}. There are \textbf{$O(n^2)$} of these quantities. Given a candidate quantity, a brute force approach to computing its $f$ value would take \textbf{$O(d)$} to run. Overall the resulting natural brute force algorithm will take \textbf{$O(n^3)$} time to run, which is \textbf{polynomial}. \item Consider again the example array: $[8, 2, 9, 5, 6, 5, 3, 1]$. \ldots Finish the following table describing this expansion, thinking carefully about why you make the choice you do at each point: \begin{center} \begin{tabular}{rrrr} $i$ & $d$ & minimum & $f(i,d)$\\ \hline 4 & 2 & 5 & 10\\ 3 & 3 & 5 & 15\\ 3 & 4 & 5 & 20\\ \textbf{3} & \textbf{5} & \textbf{3} & \textbf{15}\\ \textbf{2} & \textbf{6} & \textbf{2} & \textbf{12}\\ \textbf{1} & \textbf{7} & \textbf{2} & \textbf{14}\\ 1 & 8 & 1 & 8\\ \end{tabular} \end{center} (At each step, we just expand the stretch in the direction of the larger value on the border of the stretch, or the only allowable stretch once we reach a boundary.) \end{enumerate} \subsection{Assignment} \label{sec-1-2} \begin{enumerate} \item Give pseudo-code for the natural brute force algorithm to solve the Aconcagua problem in $\Theta(n^3)$ time. \begin{verbatim} BruteSolveAcon(A, n): \end{verbatim} \item Give pseudocode for an efficient \sout{divide-and-conquaguar} divide-and-conquer algorithm for finding the optimal price stretch based on the insight in quiz question 4. \begin{verbatim} Conquaguar(A, n): \end{verbatim} \item Give and briefly justify a good asymptotic bound on the runtime of your algorithm. \item Prove that your algorithm implementing the insight from quiz question 4 has (in general, not just for the array from that question) the property described in that question. Specifically: at each step, it finds the best stretch of the length (value of $d$) under consideration that includes the middle indexes of the array. \end{enumerate} \section{Quadsires} \label{sec-2} The popular augmented reality game Lokimon Go maintains a large map of sites of interest---like Lokistops and Gyms---each with $x$ and $y$ coordinates. (Longitude and latitude, but for our purposes, we'll take these to be integer $x$ and $y$ on a Cartesian grid.) These are stored in a type of "quad tree" data structure. Specifically, the structure is a 4-ary tree. Each node \texttt{n} is associated with a Lokimon Go site of interest \texttt{n.site}, represented simply as a $(x, y)$ coordinate pair giving the location of the site (\texttt{n.site} for the pair or \texttt{n.site.x} and \texttt{n.site.y} for the individual coordinates). The node's four subtrees are \texttt{n.NE}, \texttt{n.SE}, \texttt{n.SW}, and \texttt{n.NW}. These are (respectively): the area to the northeast (higher $x$ and $y$ values), southeast (higher $x$ and lower $y$ values), southwest (lower $x$ and $y$ values), and northwest (lower $x$ and higher $y$ values). Some of these subtrees may be empty (represented by the special quad tree value \texttt{EMPTY}) if they contain no sites of interest. There are some boundary cases: No two sites have the \textbf{same} coordinates. Sites that are due north or due east are both included in the \texttt{NE} subtree, due south in the \texttt{SE} subtree, and due west in the \texttt{NW} subtree. For example, on the left below is a set of sites we might want to put into a Lokimon Go quad tree. On the right is that set in a possible quad tree. The root is the largest dot at $(1, 4)$ with lines separating out its NE, SE, SW, and NW quadrants. It has three non-empty subtrees, and each root of these subtrees is drawn with a slightly smaller dot. The NE is rooted at $(3, 5)$, the SE at $(4, 3)$, and the NW at $(0, 5)$. Only the SE subtree has further children. It has a SW subtree (rooted at $(3, 1)$) which in turn has a NW subtree (rooted at $(2, 2)$). \begin{tikzpicture} \draw[thick,->] (0,0) -- (4.5,0) node[anchor=north west] {x axis}; \draw[thick,->] (0,0) -- (0,5.5) node[anchor=south east] {y axis}; \foreach \x in {0,1,2,3,4} \draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$}; \foreach \y in {0,1,2,3,4,5} \draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$}; \fill (1, 4) circle (0.1); \fill (0, 5) circle (0.1); \fill (3, 5) circle (0.1); \fill (4, 3) circle (0.1); \fill (3, 1) circle (0.1); \fill (2, 2) circle (0.1); \end{tikzpicture} \begin{tikzpicture} \draw[thick,->] (0,0) -- (4.5,0) node[anchor=north west] {x axis}; \draw[thick,->] (0,0) -- (0,5.5) node[anchor=south east] {y axis}; \foreach \x in {0,1,2,3,4} \draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$}; \foreach \y in {0,1,2,3,4,5} \draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$}; \draw[gray,ultra thick] (0, 4) -- (4.5, 4); \draw[gray,ultra thick] (1, 0) -- (1, 5.5); \fill (1, 4) circle (0.2); \draw[gray,thick] (0, 5) -- (1, 5); \draw[gray,thick] (0, 4) -- (0, 5.5); \fill (0, 5) circle (0.15); \draw[gray,thick] (1, 5) -- (4.5, 5); \draw[gray,thick] (3, 4) -- (3, 5.5); \fill (3, 5) circle (0.15); \draw[gray,thick] (1, 3) -- (4.5, 3); \draw[gray,thick] (4, 0) -- (4, 4); \fill (4, 3) circle (0.15); \draw[gray,thin] (1, 1) -- (4, 1); \draw[gray,thin] (3, 0) -- (3, 3); \fill (3, 1) circle (0.1); \draw[gray,very thin] (1, 2) -- (3, 2); \draw[gray,very thin] (2, 1) -- (2, 3); \fill (2, 2) circle (0.05); \end{tikzpicture} We could then search for a site like $(2, 2)$ by accessing the root, which is at $(1, 4)$, observing that $(2, 2)$ is to the SW of the root, and recursing into the SW subtree of the root. We also define a rectangle $((x_{lo}, y_{lo}), (x_{hi}, y_{hi}))$ to contain the set of sites with coordinates $(x, y)$ such that $x$ is between $x_{lo}$ and $x_{hi}$ and $y$ is between $y_{lo}$ and $y_{hi}$. (We are intentionally vague on the boundary conditions for the moment. However, if $x_{lo} > x_{hi}$ or $y_{lo} > y_{hi}$, the rectangle is empty.) We gave a rough outline of a good algorithm for searching a quadtree for a site above. Assume that \texttt{Search(qt, pt)} is an efficient and correct implementation of this algorithm that takes a quadtree \texttt{qt} and $(x, y)$ coordinate pair \texttt{pt} and produces the quad tree node containing that site (if any) or the special empty quad tree value \texttt{EMPTY} (otherwise). \begin{enumerate} \item This algorithm will have two base cases. What will they be? Fill in the boxes next to the \textbf{TWO} that apply: \begin{tabular}{l} $\fillinMCAll{\texttt{qt} is the root node of the quad tree}$\\ $\fillinMCAll{\texttt{pt} is (0, 0)}$\\ $\fillinMCAll{\texttt{qt} is \texttt{EMPTY}}$\\ $\fillinMCAll{\texttt{qt.site} is equal to \texttt{pt}}$\\ $\fillinMCAll{\texttt{qt.site.value} is 0}$\\ \end{tabular} \item Let \texttt{pt} be $(x_p, y_p)$ and the coordinates of \texttt{qt.site} be $(x_q, y_q)$. If $x_p < x_q$ and $y_p \geq y_q$, which subtree should we recurse into? Fill in the circle next to the correct answer. \begin{tabular}{l} $\fillinMC{NE}$\\ $\fillinMC{SE}$\\ $\fillinMC{SW}$\\ $\fillinMC{NW}$\\ \end{tabular} \item Give a good big-O bound on the worst-case runtime of \texttt{Search} in terms of each of the following variables or write "none" if no such bound can be given. \begin{enumerate} \item The number of nodes $e$ in \texttt{qt} that are to the east of (have $x$ coordinates \emph{at least as large} as) \texttt{pt}: $\fillinblank{MMMM}$ \item The number of nodes $n$ in \texttt{qt}: $\fillinblank{MMMM}$ \item The height $h$ of \texttt{qt}: $\fillinblank{MMMM}$ \end{enumerate} \item We can use a rectangle to define the portion of the $(x, y)$ plane contained in each subtree of the quadtree. So, the root contains $((-\infty, -\infty), (\infty, \infty))$, but the root's SE subtree contains only $((root.site.x, -\infty), (\infty, root.site.y))$. If a given subtree contains the rectangle $((x_{lo}, y_{lo}), (x_{hi}, y_{hi}))$, we can ask whether the subtree (and its rectangle) should contain sites on its northern ($y = y_{hi}$), eastern ($x = x_{hi}$), southern ($y = y_{lo}$), and western ($x = x_{lo}$) boundaries. For each of the following indicate the \textbf{best} choice about whether a subtree should contain sites on these boundaries (\textbf{YES}) or should not (\textbf{NO}) based on the definitions above. Do not worry about infinite values ($\infty$ and $-\infty$) in these choices. \begin{tabular}{l|ll} Boundary & \textbf{YES} & \textbf{NO}\\ \hline Northern: & $\fillinMC{}$ & $\fillinMC{}$\\ Eastern: & $\fillinMC{}$ & $\fillinMC{}$\\ Southern: & $\fillinMC{}$ & $\fillinMC{}$\\ Western: & $\fillinMC{}$ & $\fillinMC{}$\\ \end{tabular} \item Assume we add a field \texttt{box} to each node that is a four-tuple: \texttt{(xlo, xhi, ylo, yhi)}, where \texttt{n.box} should contain the boundaries for the rectangle representing the portion of the $(x, y)$ plane contained in the subtree rooted at \texttt{n}. Complete the following algorithm for setting correct \texttt{box} boundaries on the nodes of a quad-tree, given that the given parameters \texttt{(xlo, xhi, ylo, yhi)} are correct boundaries for the subtree \texttt{qt}. Note that we only ask for the NE and SW subtrees, leaving \ldots for the parameters for the recursive calls on the NW and SE subtrees. You should assume that the SE and NW subtrees are handled correctly. \setlength{\fboxsep}{1em} \setlength{\fboxrule}{2pt} \begin{algorithmic} \Procedure{SetBox}{qt, xlo, xhi, ylo, yhi} \State x = qt.site.x \State y = qt.site.y \If {root is not EMPTY} \State qt.box = (xlo, xhi, ylo, yhi) \State \Call{SetBox}{qt.NE, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}} \State \Call{SetBox}{qt.SE, \ldots, \ldots, \ldots, \ldots} \State \Call{SetBox}{qt.SW, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}, \fbox{\strut\rule{3em}{0em}}} \State \Call{SetBox}{qt.NW, \ldots, \ldots, \ldots, \ldots} \EndIf \EndProcedure \end{algorithmic} \item Give a good big-O bound on the worst-case runtime of a correct and efficient implementation of \texttt{SetBox} in terms of each of the following variables or write "none" if no such bound can be given. \begin{enumerate} \item The number of nodes $e$ in \texttt{qt} that are to the east of (have $x$ coordinates \emph{at least as large} as) \texttt{xlo}: $\fillinblank{MMMM}$ \item The number of nodes $n$ in \texttt{qt}: $\fillinblank{MMMM}$ \item The height $h$ of \texttt{qt}: $\fillinblank{MMMM}$ \end{enumerate} \end{enumerate} \subsection{Quiz Solution} \label{sec-2-1} \begin{enumerate} \item Base cases: \texttt{qt} is \texttt{EMPTY}, \texttt{qt.site} is equal to \texttt{pt}. \item NW (because smaller $x$ is W and larger $y$ is N) \item The algorithm traverses a single path from root to target or leaf. \begin{enumerate} \item The number of nodes $e$ in \texttt{qt} that are to the east of (have $x$ coordinates \emph{at least as large} as) \texttt{pt}: "none" \item The number of nodes $n$ in \texttt{qt}: $O(n)$ \item The height $h$ of \texttt{qt}: $O(h)$ \end{enumerate} \item \begin{tabular}{l|l} Boundary & \textbf{SOLUTION}\\ \hline Northern: & \textbf{NO}\\ Eastern: & \textbf{NO}\\ Southern: & \textbf{YES}\\ Western: & \textbf{YES}\\ \end{tabular} (Why? Consider which directions from a root node are included in each of the subtrees. E.g., because sites due north of the root are included in the NE subtree, the NE subtree must include its western boundary (which is that due north line).) \item \begin{algorithmic} \Procedure{SetBox}{qt, xlo, xhi, ylo, yhi} \State x = qt.site.x \State y = qt.site.y \If {root is not EMPTY} \State qt.box = (xlo, xhi, ylo, yhi) \State \Call{SetBox}{qt.NE, qt.site.x, xhi, qt.site.y, yhi} \State \Call{SetBox}{qt.SE, \ldots, \ldots, \ldots, \ldots} \State \Call{SetBox}{qt.SW, xlo, qt.site.x, ylo, qt.site.y} \State \Call{SetBox}{qt.NW, \ldots, \ldots, \ldots, \ldots} \EndIf \EndProcedure \end{algorithmic} \item The algorithm spends constant time at each node. \begin{enumerate} \item The number of nodes $e$ in \texttt{qt} that are to the east of (have $x$ coordinates \emph{at least as large} as) \texttt{xlo}: $O(e)$ \item The number of nodes $n$ in \texttt{qt}: $O(n)$ \item The height $h$ of \texttt{qt}: $O(4^h)$ \end{enumerate} \end{enumerate} \subsection{Assignment} \label{sec-2-2} We add to each node a non-negative integer \texttt{freq} field representing the frequency at which we expect that node's site to be accessed in Lokimon Go. We want higher-frequency nodes to be closer to the root of the tree. In particular, if a node is $k$ steps from the root (where for the root, $k = 0$), then we assign it a cost of $k * \texttt{freq}$. The cost of a whole tree is the sum of the costs of each of its nodes. \begin{enumerate} \item Give efficient pseudocode for a function \texttt{Cost} that computes the total cost of a tree \texttt{qt} (that has \texttt{freq} fields). \begin{verbatim} Cost(qt): \end{verbatim} \item Given a set of sites and their frequencies, we can ask which is the optimal quadtree (i.e., a quadtree that has minimal cost among all possible quadtrees built from the same sites). Give pseudocode for a brute-force, recursive algorithm to find the total cost of the optimal quadtree for a given set of sites with their frequencies. \emph{Hint:} Add two "fake" zero-frequency sites at $(-\infty, -\infty)$ and $(\infty, \infty)$. A subproblem can be described by a rectangle that could be the box associated with a subtree of the final quadtree. A rectangle is an $(x, y)$ coordinate for the lower-left corner and an $(x, y)$ coordinate for the upper-right corner. Now, how can you concisely describe a subproblem? \begin{verbatim} BruteBuildQT(sites, freqs, n): \end{verbatim} \item Give pseudocode for a memoized version of your brute-force algorithm. Your memoized algorithm must run in worst-case $O(n^3)$ time (for $n$ sites). \begin{verbatim} MemoizedBuildQT(sites, freqs, n): \end{verbatim} \end{enumerate} \section{Shreddin' the Gnar} \label{sec-3} Enough of all this hard work, it's time to start thinking about the snowboarding season! Cypress is opening a huge new run with a sequence of jumping ramps designed to delight. Every day, they'll hold a contest to see who can catch the most air on the way down the mountain. You are tasked with planning the winning route, according to the following rules: whenever you reach a ramp while on the ground, you can either use that ramp to jump through the air, possibly flying over one or more ramps, or shred past that ramp and stay on the ground. Obviously, if you fly \emph{over} a ramp, you cannot use that ramp to increase your air time. Based on observation and experimentation, you have assembled the following data: an array $R[1\ldots n]$, where $R[i]$ is the distance from the top of the hill to the $i^{th}$ ramp, and an array $L[1\ldots n]$, where $L[i]$ is the distance any boarder who takes the $i^{th}$ ramp will travel through the air. For simplicity, you may assume that array $R$ is sorted by distance, so that the ramps are numbered $1\ldots n$ down the mountain. In this part of the problem we will design an algorithm to find an optimal solution. Don't forget the definition of $N(i)$: For any index $i$, let $N(i)$ denote the smallest index $j$ such that $R[j] > R[i] + L[i]$. You may also find it convenient to define $R[n+1] = \infty$. \subsection{Quiz and Solution} \label{sec-3-1} \begin{enumerate} \item A reasonable definition for an algorithm to solve this problem would be $MA(i)$: \begin{tabular}{l} $\fillinMCsoln{The maximum distance spent in the air starting on the ground at ramp i.}$\\ $\fillinMC{The maximum number of ramps taken before ramp i.}$\\ $\fillinMC{The maximum number of ramps taken after starting on the ground at ramp i.}$\\ $\fillinMC{The minimum number of ramps missed after starting on the ground at ramp i.}$\\ $\fillinMC{The single longest jump remaining after and including ramp i.}$\\ $\fillinMC{The minimum total distance spent in the air before ramp i.}$\\ \end{tabular} \item We can solve the problem by calling the algorithm as: $\fillinMCmathsoln{MA(1)}$ $\fillinMCmath{MA(n)}$ (choose one). \item A base case for the problem is: $MA(i) = \fillinblank{MMM}$ if $\fillinMCmathsoln{i > n}$ $\fillinMCmath{i < n}$ (choose one). \item Suppose you choose not to take ramp $i$. Then, $MA(i)$ is just: \begin{tabular}{l} $\fillinMCmath{N(i)}$\\ $\fillinMCmath{MA(i)}$\\ $\fillinMCmathsoln{MA(i+1)}$\\ $\fillinMCmath{MA(N(i))}$\\ $\fillinMC{None of these.}$\\ \end{tabular} \item Suppose you choose to take ramp $i$. In that case, $MA(i)$ is: \begin{tabular}{l} $\fillinMCmath{L[i] + MA(i+1)}$\\ $\fillinMCmath{R[i+1] + MA(i+1)}$\\ $\fillinMCmath{L[N(i)] + MA(i+1)}$\\ $\fillinMCmathsoln{L[i] + MA(N(i))}$\\ $\fillinMC{None of these.}$\\ \end{tabular} \item The recursive case of the dynamic programming algorithm you can use to solve this problem takes the $\fillinMCmathsoln{\max}$ $\fillinMCmath{\min}$ (choose one) of the values in the last two parts. \item Given the algorithm you have designed by your selections above, a reasonable approach to memoizing the computation would require $\underline{\phantom{MMM}}$ space. \begin{tabular}{l} $\fillinMCmath{O(1)}$\\ $\fillinMCmath{O(\log n)}$\\ $\fillinMCmathsoln{O(n)}$\\ $\fillinMCmath{O(n\log n)}$\\ $\fillinMCmath{O(n^2)}$\\ $\fillinMC{We don't have enough information to answer the question.}$\\ \end{tabular} \end{enumerate} \subsection{Assignment} \label{sec-3-2} Putting together the results from the quiz\ldots Let $\text{MA}(i)$ denote the maximum distance any snowboarder can spend in the air starting on the ground at the $i^{th}$ ramp. We need to compute $\text{MA}(1)$. This function satisfies the following recurrence: \[ \text{MA}(i) = \begin{cases} 0 & i > n \\ \max \left\{ \begin{array}{l} \text{MA}(i+1)\\ L[i]+\text{MA}(N(i))\end{array} \right\} & 1\leq i \leq n\\ \end{cases} \] \begin{enumerate} \item Complete the pseudocode below to define a dynamic programming (iterative memoized) algorithm for computing $\text{MA}(i)$. Assume $N(i)$ is already implemented, but think about how it works and about its running time on data of size $i$. Write \textbf{clearly} and \textbf{carefully} and follow the existing notation, as some minor differences in notation can also indicate substantial misunderstandings. (Please do use the typical $\max$ function available in most languages.) \begin{algorithmic} \Function{MaxAir}{$R[1 .. n], L[1 .. n]$} \State $R[n+1]\gets\infty$ \State $\text{MA}[n + 1]\gets \fillinblankmath{M}$ \For {$i = n \text{ \bf{down to} } 1$} \State $\text{MA}[i] \gets \fillinblankmath{MMMMMMMMMMMMMMMMMM}$ \EndFor \State\Return $\text{MA}[1]$ \end{algorithmic} \item Give a good upper bound on the running time of $\text{MaxAir}$ on data of size $n$. \item Uh Oh. The Cypress ski patrol heard about the contest and protested that it would result in too many injuries. In response, Cypress imposed a limit on the number of jumps that any snowboarder can take as they navigate the slope. Reformulate the problem and its solution using this new information: \begin{enumerate} \item The problem is now parameterized by two input variables. Rewrite the definition of the function $\text{MA}(i,j)$ in English. Let $\text{MA}(i,j)$ denote\ldots \item Define the recursive function that could be used to compute $\text{MA}(i,j)$. \item Write pseudocode to define a dynamic programming (iterative memoized) algorithm for computing $\text{MA}(i,j)$. \item What is the running time of your algorithm? \end{enumerate} \end{enumerate} \section{Recurring Nightmare} \label{sec-4} \subsection{Quiz and Answers} \label{sec-4-1} Below you will find five recurrences that should be familiar to you. Identify the problem context in which you've seen each recurrence and write it in the answer box, and also to discuss how each function relates to the problem that it solves. Annotate your answer with an explanation for any recurrence which is not a worst case analysis of an upper bound on the running time. \begin{enumerate} \item Running time of $\fillinblank{MMMMMM}$ on an array of size $n$: \[ T(n) = \begin{cases} 0 & n = 0 \\ T(3n/4) + T(n/4) + n & n > 0 \end{cases} \] This is much like the average-case analysis (or the similar expected analysis) for quicksort. Asymptotic closed form: $T(n) = \Theta(n\log n)$ \item Running time of $\fillinblank{MMMMMM}$ on an array of size $n$: \[ T(n) = \begin{cases} 0 & n = 0 \\ T(n-1) + T(1) + n & n > 0 \end{cases} \] This is much like the worst-case analysis for quicksort. Asymptotic closed form: $T(n) = \Theta(n^2)$ \item Running time of $\fillinblank{MMMMMM}$ on an array of size $n$: \[ T(n) = \begin{cases} 0 & n = 0 \\ T(3n/4) + T(n/5) + n & n > 0 \end{cases} \] This is much like the worst-case analysis for deterministic select. Asymptotic closed form: $T(n) = \Theta(n)$ \item Running time of $\fillinblank{MMMMMM}$ on an array of size $n$: \[ T(n) = \begin{cases} 0 & n = 0 \\ 2T(n/2) + n & n > 0 \end{cases} \] This is much like the worst-case analysis for mergesort. Asymptotic closed form: $T(n) = \Theta(n\log n)$ \item Running time of $\fillinblank{MMMMMM}$ on input of magnitude $n$: \[ T(n) \geq \begin{cases} 1 & n \in \{0, 1, \ldots, 24\} \\ 3T(n-25) + 1 & n > 24 \end{cases} \] This is much like the lower-bound we developed on the runtime of our "brute force" recursive coin-changing algorithm. Note that since we only know that $T(n) \geq$ the cases on the right, this is an $\Omega$ bound, not a $\Theta$ bound. Asymptotic closed form: $T(n) = \Omega(c^n), c>1$ (A more specific function than $c^n$ would be fine, but the key point on this recurrence in class was that its solution is exponential.) \end{enumerate} \subsection{Assignment} \label{sec-4-2} \begin{enumerate} \item Give an asymptotic solution to the recurrence below. In particular, follow these steps: draw a recurrence tree and show your work as you develop a \emph{guess} at the solution; then, prove that your guess is correct via induction. \[ T(n) = \begin{cases} 1 & n = 1 \\ 3T(n/2) + n & n > 1 \end{cases} \] \item Give an asymptotic solution to the recurrence below by substituting $U(n) = n\cdot T(n)$, noting the well-known bound on the more familiar recurrence you find, and then deriving the bound on the original function $T(n)$. \textbf{Show} your steps using the substitution to get a more familiar recurrence and then transforming this back into a solution for $T(n)$. \[ T(n) = \begin{cases} 1 & n = 1 \\ \frac{1}{4}T(\frac{n}{4}) + \frac{3}{4}T(\frac{3n}{4}) + 1 & n > 1 \end{cases} \] \item Give an asymptotic solution to the recurrence below by narrowing in on a tight bound. Loose bounds---which you need not prove---of $\Omega(n)$ and $O(n\log n)$ are easy to establish. What functions lie between those? Guess and prove! \emph{Hint:} consider using functions like $\sqrt{\lg x}$, $\lg \lg x$, and $\lg^* x$. \[ T(n) = \begin{cases} 2 & n = 2 \\ \sqrt{n}\cdot T(\sqrt{n}) + n & n > 2 \end{cases} \] \end{enumerate} % Emacs 25.2.1 (Org mode 8.2.10) \end{document}