% Created 2018-03-13 Tue 19:36 \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}} \def\ith{$i^{\textrm{\scriptsize th}}$} \newtheorem{fact}{Fact} \def\imax{$\texttt{S}_{\max}$} \def\iprevmax{previous\_$\texttt{S}_{\max}$} \def\deleted{\texttt{covered}} \def\infinity{$\infty$} %\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} \usepackage{mdframed} \BeforeBeginEnvironment{minted}{\begin{mdframed}} \AfterEndEnvironment{minted}{\end{mdframed}} \date{} \title{CPSC 320 2017W2: Assignment 4} \hypersetup{ pdfkeywords={}, pdfsubject={}, pdfcreator={Emacs 25.2.1 (Org mode 8.2.10)}} \begin{document} \maketitle \textbf{BE SURE TO READ THE UNUSUAL, INDENTED DUE DATE NOTES BELOW!} 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.) Remember that this assignment is based on the collected quizzes and quiz solutions. You will likely want to refer to those where you need more details on assignment questions. \begin{quote} Submit by the \textbf{UNUSUAL} deadline \textbf{Thursday 22 Mar at 10PM}. \textbf{If your last submission} is no later than Tuesday 20 Mar at 10PM, each member of your group will also receive one bonus point and a tiny, secret smile from a member of the course staff. \end{quote} For credit, your group must make a \textbf{single} submission via one group member's account, marking all other group members and the pages associated with each problem 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. (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} \section{The elements go up and down} \label{sec-1} Let $A$ be an integer array with $n$ elements in total. In the tutorial, you designed an $O(\log n)$ time algorithm to find the largest element of $A$ in the case where $A$ consists of two sections: first one with numbers strictly increasing followed by one with numbers strictly decreasing. This algorithm divided the array in thirds, and called itself recursively on two-thirds of the original array. You also saw that in the case where $A$ consists of three sections: first one with numbers strictly increasing followed by one with numbers strictly decreasing, followed by another section with numbers strictly increasing, then dividing the array into quarters did not help. Now prove an $\Omega(n)$ lower bound on the worst-case time complexity of any correct algorithm to finds the largest element of $A$ in the case where it consists of three sections as described above. \emph{Hint:} show that the task requires looking at every single element of $A$ by filling in a proof structure like this one (where you may will need to fill in the large gaps below): \begin{quote} We prove by contradiction that any correct algorithm for this problem \textbf{must} look at every element in the array. Suppose not\ldots{} For each element $A[i]$ the algorithm accesses, we produce the value \ldots{} but we do not yet commit to other values. \ldots{} When the algorithm returns its result, we invalidate its answer by selecting the remaining, unaccessed values as follows \ldots{} \end{quote} \section{Essay Assignment, Essay Assignment Again} \label{sec-2} Your company manages a large group of freelance writers. Given a large group of essays (e.g., newspaper articles), you want to assign each writer exactly one essay to write. (We assume the number of writers and essays is equal.) Each writer gives a non-negative valuation (number) for each essay, essentially how much they like that essay. We assume that valuations are directly comparable and additive; so, e.g., a valuation of 6 for one writer is exactly twice as good as a valuation of 3 for another a valuation of 9 is as much better than 6 as 6 is than 3. However, \textbf{essays} have no valuation or preference over writers. You want to find a valid assignment of essays to writers (a perfect matching) of highest quality. \begin{enumerate} \item Consider \textbf{Algorithm 2} from the quizzes: Repeatedly pick an arbitrary remaining (unassigned) writer. Assign the remaining essay that they value highest to that writer. Repeat until all essays are assigned. (Break ties arbitrarily.) \begin{enumerate} \item Give a very small but non-trivial instance of the problem and the solution produced by this algorithm. \item Sketch the key points in a proof that the following property holds in any solution produced by this algorithm: no two writers would (strictly) prefer to switch essays with each other than complete the essays assigned to them. \item Give and briefly explain a small counterexample to the optimality of the algorithm according to this metric: an optimal assignment maximizes the total for each writer $w$ of $w$'s valuation for the essay assigned to $w$. \textbf{For this part only}, assume that rather than picking an arbitrary writer, the algorithm picks the "first" remaining writer, in the order the writers were initially supplied as input. (I.e., you---perhaps fiendishly---pick a single, consistent order that the algorithm must use as it selects writers to assign.) \end{enumerate} \item The "weighted maximum matching" problem is an adaptation of the maximum matching problem to weighted graphs. An instance of the problem is an undirected, weighted graph\footnote{With no self-loops and at most a single edge between two vertices. I.e., a normal undirected, weighted graph.} $G = (V, E)$ where $w(e)$ is an integer weight for edge $e$. A valid solution is a set of edges $E' \subseteq E$ such that no vertex is incident on two different edges in $E'$. An optimal solution is a valid solution of maximum total weight $\sum_{e \in E'} w(e)$. Give a good reduction from our essay assignment problem---with the metric that an optimal assignment maximizes the total of each writer's valuation of their assigned essay---to weighted maximum matching. \item Consider \textbf{Algorithm 1} from the quiz: Repeatedly pick the remaining (unassigned) essay with the highest valuation from any one remaining writer. Assign that essay to that writer. Repeat until all essays are assigned. (Break ties arbitrarily.) Somewhat surprisingly, this can be considered an implementation of \textbf{algorithm 2} (described above). Briefly but clearly justify this statement. \end{enumerate} \section{Marvelous Medians} \label{sec-3} Suppose that we are given an unsorted array $A$ with $n$ elements, and another \emph{sorted} array \emph{Positions} with $k$ distinct elements chosen from the set $\{ 1, 2, \ldots, n \}$. In the tutorial, you gave an $O(n\log k)$ time algorithm to find the Positions$[1]$, Positions$[2]$, \ldots, Positions$[k]$ smallest elements of $A$. For instance, if $A = (16, 3, 19, 12, 16, 21, 18, 10)$ and Positions = $(3, 5, 8)$, then the solution is the array $(12, 16, 21)$ because $12$ is the third smallest element of $A$, $16$ is the fifth smallest element of $A$, and $21$ is the eigth smallest element of $A$. Suppose now that instead of receiving the positions all at once, you get a sequence of $k$ queries of the form ``what is the \ith{} smallest element of $A$'', and that you must respond to each query when it is received. \begin{enumerate} \item Asymptotically, for which values of $k$ (the number of queries) is the best solution to sort the array $A$ and then answer each query in $\Theta(1)$ time? When $k \in \fillinblank{\Omega(\log n)}$ \item Now, instead of only queries for the \ith{} smallest element of $A$, you receive a sequence of requests where each request is one of \begin{itemize} \item insert a new element $x$ into $A$ \item delete an element $x$ from $A$ \item query for the \ith{} smallest element of $A$ \end{itemize} Keeping the elements in a sorted array $A$ is no longer an option. One alternative is to store the elements in a balanced binary search tree $T$. We will keep in each node the size of the subtree rooted at that node (the sizes are in parentheses in the following example). This size information can be maintained when insertions and deletions are performed on the tree without affecting the running times of these operations. \includegraphics[width=4.5in]{figures/2017W2-augmented-bst.png} Write an algorithm that takes a binary search tree $T$ (with the size information) and an integer $i$, and returns the \ith{} smallest element of the tree $T$. \item Finally, write an algorithm that takes a binary search tree $T$ (with the size information) and a key $x$, and returns the rank of $x$ in $T$. The smallest element of $T$ has rank $1$, the second smallest element of $T$ has rank $2$, etc. You may assume that $x$ is present in the tree. \end{enumerate} \section{Mastering recurrences} \label{sec-4} Consider case 3 of the Master theorem: $f(n) \in \Omega(n^{\log_b a + \varepsilon})$ for some $\varepsilon > 0$, and $af(n/b) < \delta f(n)$ for some $\delta < 1$ and all sufficiently large values of $n$. If the regularity condition holds, then we can prove by induction that $a^j f(n/b^j) \le \delta^j f(n)$. \textbf{Use} (i.e., assume) this fact to prove that, if the conditions for case 3 of the Master theorem hold, then $T(n) \in \Theta(f(n))$. \section{WestGrid (and North/East/SouthGrid)} \label{sec-5} As transistor densities continue to increase but processor speed and the complexity (in transistors) of processors does not, chip manufacturers turn more and more to on-chip multi-core solutions to provide additional performance. The 2-D nature of VLSI chips thus makes communication on a 2-D grid important. In this problem, we imagine a $n\times n$ grid of processors, also called nodes. Each node is described by its $(x, y)$ coordinate pair, where the upper-leftmost node is $(1, 1)$ and the lower-rightmost node is $(n, n)$, and by a single positive integer $\textit{grid}[x,y]$ describing its congestion level (how busy it is). The quiz solution included algorithms for finding the maximum congestion of any node at or northwest of a specific node and the maximum congestion overall of any node that does not share the same $x$ or $y$ coordinates with a given node: \begin{description} \item[{Congestion at or to the northwest of a node:}] \[ NWC(x, y) = \begin{dcases} 0 & \textrm{if } x < 1 \textrm{ or } y < 1 \\ \max(NWC(x-1, y), NWC(x, y-1), \textit{grid}[x, y]) & \textrm{otherwise} \end{dcases} \] \item[{Maximum congestion outside of a nodes row/column:}] \begin{verbatim} MaxC(x, y): return max(NWC(x - 1, y - 1), NEC(x + 1, y - 1), SEC(x + 1, y + 1), SWC(x - 1, y + 1)) \end{verbatim} \end{description} Now, solve these problems: \begin{enumerate} \item Give a complete (not just northwest!), dynamic programming approach to efficiently prepare to answer repeated calls to \verb~MaxC~. You may set aside memory to be used and reused on calls to \verb~MaxC~ up to at most big $O$ of the amount of memory the initial input grid uses, but you should make clear what memory you're using and what values in that memory mean. Specify a pre-processing function \verb~PrepareMaxC~ to be called once before all calls to \verb~MaxC~. \verb~PrepareMaxC~ can assume access to \emph{grid}. The query function \verb~MaxC~ can also assume access to \emph{grid} and to any data structures you indicate are shared with \verb~PrepareMaxC~. Make clear how \verb~PrepareMaxC~ should be called. Your priority is to make \verb~MaxC~ as efficient in terms of asymptotic runtime as possible. Within that constraint, you should make \verb~PrepareMaxC~ as efficient in terms of asymptotic runtime as possible and ensure both use no more than the space restrictions laid out above. \item Give and briefly justify the runtime and memory usage of \verb~PrepareMaxC~ and \verb~MaxC~ in terms of $n$, the grid dimension. \end{enumerate} % Emacs 25.2.1 (Org mode 8.2.10) \end{document}