% Created 2017-09-27 Wed 12:22 \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{amsmath} \usepackage{algpseudocode} \usepackage[margin=0.75in]{geometry} \usepackage{nth} \usepackage{tikz} \usetikzlibrary{positioning,chains,fit,shapes,calc} \usepackage{ccicons} \usepackage{fancyhdr} \usepackage{hyperref} \usepackage{nopageno} \usepackage{enumitem} \algnewcommand\algorithmicforeach{\textbf{for each}} \algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo} \newcommand{\marksamt}[1]{\textbf{[#1~marks]}} \newcommand{\markamt}[1]{\textbf{[#1~mark]}} \newcommand{\fillinMC}[1]{\fillinMCmath{\mbox{#1}}} \newcommand{\fillinMCmath}[1]{\begin{tikzpicture}\draw 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{\fillinblank}[1]{\fillinblankmath{\mbox{#1}}} \newcommand{\fillinblankmath}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{\LARGE\phantom{#1}}\endgroup} \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 2} \hypersetup{ pdfkeywords={}, pdfsubject={}, pdfcreator={Emacs 25.2.1 (Org mode 8.2.10)}} \begin{document} \maketitle \textbf{WARNING:} We reserve the right to add some questions to this assignment after the midterm exam. 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 13 Oct 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{eXtreme True And/Or False} \label{sec-1} Each of the following problems presents a scenario in a graph and a statement about that scenario. For each one, indicate by filling in the appropriate circle whether: \begin{enumerate} \item The statement is \textbf{ALWAYS} true, i.e., true in \emph{every} graph matching the scenario. \item The statement is \textbf{SOMETIMES} true, i.e., true in some graph matching the scenario but also false in some such instance. \item The statement is \textbf{NEVER} true, i.e., true in \emph{none} of the graphs matching the scenario. \end{enumerate} Recall: $|V| = n, |E| = m$. A vertex's \emph{degree} is the number of edges incident on it. For directed graphs, a vertex's \emph{in-degree} is the number of edges ending at the vertex and the \emph{out-degree} is the number starting from it. A \emph{path} of length $k$ is a list of $k+1$ vertices with an edge between each consecutive pair of vertices. A \emph{simple path} repeats no vertex. A \emph{cycle} is a path that starts and ends at the same vertex. A \emph{simple cycle} repeats no other vertex. \begin{enumerate} \item \textbf{Scenario:} A directed graph with $n \geq 2$. \textbf{Statement:} The out-degree of each vertex is larger than its in-degree. $\fillinMC{ALWAYS}$ $\fillinMC{SOMETIMES}$ $\fillinMC{NEVER}$ \item \textbf{Scenario:} A non-empty DAG with a single, unique topological ordering. \textbf{Statement:} Any two different vertices in the graph have exactly one edge between them (i.e., an edge going one direction or the other, but not both edges). $\fillinMC{ALWAYS}$ $\fillinMC{SOMETIMES}$ $\fillinMC{NEVER}$ \item \textbf{Scenario:} A strongly-connected, directed graph with $n \geq 2$. \textbf{Statement:} A simple cycle of length $n$ exists. $\fillinMC{ALWAYS}$ $\fillinMC{SOMETIMES}$ $\fillinMC{NEVER}$ \item \textbf{Scenario:} A connected, undirected graph with $n \geq 2$. \textbf{Statement:} A path---not necessarily simple---of length $2n$ exists that visits every node. $\fillinMC{ALWAYS}$ $\fillinMC{SOMETIMES}$ $\fillinMC{NEVER}$ \end{enumerate} \subsection{Quiz Solution} \label{sec-1-1} \begin{enumerate} \item \textbf{SOLUTION:} NEVER \item \textbf{SOLUTION:} SOMETIMES \item \textbf{SOLUTION:} SOMETIMES \item \textbf{SOLUTION:} ALWAYS \end{enumerate} \subsection{Assignment} \label{sec-1-2} On the assignment, for each of the problems above, please \textbf{briefly} justify the answer. Justify an \textbf{ALWAYS} answer by giving a small instance that fits the scenario for which the statement is true and then briefly sketching the key points in a proof that the statement is true for all instances that fit the scenario. Justify a \textbf{NEVER} answer by giving a small instance that fits the scenario for which the statement is \textbf{false} and then briefly sketching the key points in a proof that the statement is \textbf{false} for all instances that fit the scenario. Justify a \textbf{SOMETIMES} answer by giving \textbf{two} small instances that fit the scenario: one for which the statement is true and one for which the statement is false. \section{O'd to a Pair of Runtimes} \label{sec-2} The pairs of functions below represent algorithm runtimes on an \textbf{undirected, connected} graph with $n$ vertices and $m$ edges. \textbf{ASSUME $m>0$.} For each pair, fill in the circle next to the best choice of: \begin{description} \item[{\textbf{LEFT}:}] the left function is big-$O$ of the right, i.e., left $\in$ O(right) \item[{\textbf{RIGHT}:}] the right function is big-$O$ of the left, i.e., right $\in$ O(left) \item[{\textbf{SAME}:}] the two functions are $\Theta$ of each other, i.e., left $\in$ $\Theta$(right) \item[{\textbf{INCOMPARABLE}:}] none of the previous relationships holds for all allowed values of $n$ and $m$. \end{description} Do not choose \textbf{LEFT} or \textbf{RIGHT} if \textbf{SAME} is true. The first one is filled in for you. \renewcommand{\arraystretch}{1.5} \begin{center} \begin{tabular}{lll} Left Function & Right Function & Answer\\ \hline $n$ & $n^2$ & \textbf{LEFT}\\ \hline $n + 3$ & $m$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \hline $n lg n$ & $m$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \hline $n^2$ & $3m + \lg n$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \hline $m^2 \lg n$ & $2^n$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \hline $2^{\log_{10} m}$ & $2^n$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \hline $\frac{m}{\lg n}$ & $1$ & $\fillinMC{LEFT}$\\ & & $\fillinMC{RIGHT}$\\ & & $\fillinMC{SAME}$\\ & & $\fillinMC{INCOMPARABLE}$\\ \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \subsection{Quiz Solution} \label{sec-2-1} \renewcommand{\arraystretch}{1.5} \begin{center} \begin{tabular}{lll} Left Function & Right Function & Answer\\ \hline $n$ & $n^2$ & \textbf{LEFT}\\ $n + 3$ & $m$ & \textbf{LEFT}\\ $n lg n$ & $m$ & \textbf{INCOMPARABLE}\\ $n^2$ & $3m + \lg n$ & \textbf{RIGHT}\\ $m^2 \lg n$ & $2^n$ & \textbf{LEFT}\\ $2^{\log_{10} m}$ & $2^n$ & \textbf{LEFT}\\ $\frac{m}{\lg n}$ & $1$ & \textbf{RIGHT}\\ \end{tabular} \end{center} \renewcommand{\arraystretch}{1} \subsection{Assignment} \label{sec-2-2} On the assignment: \begin{itemize} \item For your own reference (not graded, but \textbf{crucial}), indicate the maximum and minimum values of $m$ in terms of $n$ for the scenario described in the problem. \item Give a good $\Theta$-bound on each of the following functions from above: \begin{enumerate} \item $3m + \lg n$ \item $m^2 \lg n$ \item $2^{\log_{10} m}$ \item $\frac{m}{\lg n}$ \end{enumerate} Notes: \begin{itemize} \item Where possible, use logs base 2 (i.e., $\lg$). \item If a decimal number like 4.48 is important, round to the tenths place, like 4.5. (Technically, that will make your $\Theta$ bound incorrect, but we won't worry about that for this problem.) \item If possible, express your bound in terms of a single variable $m$ or $n$ rather than both $m$ and $n$. \end{itemize} \item For the one problem whose answer is \textbf{INCOMPARABLE}, \textbf{briefly} justify why neither function is big-O of the other. \end{itemize} \section{Slapping on a Bandwidth-Aid} \label{sec-3} \textbf{Recall:} EDP's input is an undirected, unweighted graph $G = (V, E)$ plus a set of distribution points $D = \{d_1, d_2, \ldots, d_k\}$ each a vertex in $V$ and a single aid location $a \in V$ that is not in $D$. The output is the number of non-overlapping paths leading from some $d_i$ to $a$. Paths may lead from different distribution points. \medskip You have an efficient algorithm to solve the "network bandwidth problem" (NBP). NBP's input is a \textbf{weighted}, \textbf{directed} graph $G = (V, E)$ (where the tuple $(u, v, w) \in E$ represents a \textbf{directed} edge from $u$ to $v$ with \textbf{integer weight} $w$) and designated source and target vertices $s$ and $t$. A node in the graph is a server and an edge is a network link between servers, weighted by its bandwidth---the maximum number of bytes per second the link can carry. (A weight of $\infty$ is also allowed, indicating unlimited bandwidth.) NBP's output is the maximum bandwidth that can be carried from $s$ to $t$. Notes: The bandwidth on any link cannot exceed that link's weight. The bandwidth coming \textbf{out of} $s$ is unlimited but none can go in, while unlimited bandwidth can go \textbf{into} $t$ but none can come out. Otherwise, for any node $v$, the bandwidth coming into the node must equal the bandwidth coming out. \textbf{Assume only integral} (or infinite for links with weight $\infty$) \textbf{amounts of bandwidth can be used on each edge.} \textbf{Fill in the boxes to complete this reduction that solves EDP using NBP:} Convert an instance of EDP to an instance of NBP: \begin{enumerate} \item For each node $v \in V_{EDP}$, generate $\fillinblankmath{\mbox{a corresponding node } v}$ in $V_{NBP}$. \item For each undirected edge $(u, v) \in E_{EDP}$, generate $\fillinblankmath{\mbox{two edges: } (v, u, 1), (u, v, 1)}$ in $E_{NBP}$. \item Generate one additional vertex $v'$ in $V_{NBP}$. \item For each distribution point $d \in D$, generate $\fillinblankmath{\mbox{an edge } (v', d, \infty) \in E_{NBP}}$. \item Finally, let $s = \fillinblankmath{v'}$ and $t = \fillinblankmath{a}$. \end{enumerate} Convert an instance of NBP to EDP:\medskip Let the solution to EDP be $\fillinblank{the solution to NBP}$. \subsection{Quiz Solution} \label{sec-3-1} First, two \textbf{clarifications}: \begin{enumerate} \item Paths being "non-overlapping" means they do not share \textbf{edges}. (They must share at least one vertex, the aid location to reach. They may also share other vertices, but they must use different edges between the vertices.) \item A single distribution point can be the source of many disjoint paths to the aid location. \end{enumerate} If you made different assumptions that are \textbf{reasonable in the given context of the problem} and led you to an alternative, correct solution, we intend to give you full credit for your quiz solution. (As always, you can object to our grading \emph{once we return it} if you have concerns. Please don't object before you see your grade! \smiley{}) Now, \textbf{on to our solution}, which respects these clarifications. Convert an instance of EDP to an instance of NBP: \begin{enumerate} \item For each node $v \in V_{EDP}$, generate a corresponding node $v$ in $V_{NBP}$. \item For each undirected edge $(u, v) \in E_{EDP}$, generate two edges: $(v, u, 1), (u, v, 1)$ in $E_{NBP}$. \item Generate one additional vertex $v'$ in $V_{NBP}$. \item For each distribution point $d \in D$, generate an edge $(v', d, \infty) \in E_{NBP}$. \item Finally, let $s = v'$ and $t = a$. \end{enumerate} Convert an instance of NBP to EDP:\medskip Let the solution to EDP be the solution to NBP. (Where a solution of $\infty$ means that the target is also a distribution point, in which case, it's not clear what a correct solution is anyway.) \subsection{Assignment} \label{sec-3-2} (Be sure to read clarifications in the quiz section above.) Now, consider this \textbf{incorrect} reduction from EDP to NBP. \begin{quote} Convert an instance of EDP to an instance of NBP: \begin{enumerate} \item For each node $v \in V_{EDP}$, generate a corresponding node $v$ in $V_{NBP}$. \item For each undirected edge $(u, v) \in E_{EDP}$, generate two edges: $(v, u, 1), (u, v, 1)$ in $E_{NBP}$. \item Generate one additional vertex $v'$ in $V_{NBP}$. \item For each distribution point $d \in D$, generate an edge $(v', d, 1) \in E_{NBP}$. \item Finally, let $s = v'$ and $t = a$. \end{enumerate} Convert an instance of NBP to EDP: Let the solution to EDP be the solution to NBP. \end{quote} Now, do the following: \begin{enumerate} \item Give a good \textbf{counterexample} to the correctness of this reduction. (A drawing of the counterexample instance is an excellent way to express it.) \item Give the instance of NBP produced by the reduction from your counterexample. (Again, a drawing works well.) \item Give and \textbf{very briefly} explain the incorrect solution to the original instance produced by the reduction (paired with an arbitrary solution to the underlying problem). \item Give and \textbf{very briefly} explain the correct solution to the original instance. \end{enumerate} \section{Milking Your Territory} \label{sec-4} Suppose the leaders of a town have decided that they should hire some ice cream vendors to ride bicycles around town, selling their goods to the children of the community. Your task is to help the leaders decide how many vendors to hire. To help us solve this problem, we have the following definitions: \begin{itemize} \item The town consists of a set of homes and a set of sidewalks, on which the vendors will ride. \item Each sidewalk connects a pair of homes. \item Two homes $h_1$ and $h_2$ are in the same market if there is a way to get from $h_1$ to $h_2$ riding only on sidewalks whose lengths are less than 100m each. (Bicycle vendors don't like to ride very far before they take a break.) \item Each market will be served by exactly one vendor. \end{itemize} Now, answer the following questions: \begin{enumerate} \item The number of vendors can be found most effciently by a modification of which of the following algorithms? Fill in the boxes next to \textbf{ALL} correct answers. (Several could be the foundation for a solution; select only those that solve the problem the fastest and with the least unnecessary functionality.) \begin{center} \begin{tabular}{l} $\fillinMCAll{HeapSort}$\\ $\fillinMCAll{Dijkstra's}$\\ $\fillinMCAll{Kruskal's Minimum Spanning Tree algorithm}$\\ $\fillinMCAll{Prim's Minimum Spanning Tree algorithm}$\\ $\fillinMCAll{BFS}$\\ $\fillinMCAll{DFS}$\\ \end{tabular} \end{center} \item \textbf{Briefly} describe using pseudocode (or simple C++/Java- or Racket-style code) two changes you would make to the algorithm: \begin{itemize} \item change 1: \vfill \item change 2: \vfill \end{itemize} \item Suppose each house is connected to at most 5 other homes by sidewalks. What is the running time of your algorithm in terms of the number of houses $H$? $\fillinblank{DFS/BFS runs in O(m+n) time. m is at most 5n/2. So, O(H).}$ \end{enumerate} \subsection{Quiz Solution} \label{sec-4-1} \begin{enumerate} \item DFS and BFS \item Here are the changes conceptually: \begin{enumerate} \item An (unweighted) edge exists between two houses exactly when there is an edge (sidewalk) between them in the original graph of weight less than 100 (distance less than 100m). \item Initialize the value $L$ to 1. Then, repeat until all nodes are labelled in the following way: \begin{enumerate} \item Pick an arbitrary unlabeled vertex. \item Run DFS/BFS from that vertex, labeling all reachable nodes with $L$. \item Increment $L$. \end{enumerate} \end{enumerate} \item $O(h)$ (assuming a good implementation) \end{enumerate} \subsection{Assignment} \label{sec-4-2} On the assignment, you'll solve a related but \textbf{different} problem. The algorithm above determined the appropriate \emph{number} of vendors. With small modifications, it can also label each home with an identifier that indicates the market to which it belongs. \textbf{Assume for this problem} that such a labelling already exists. Furthermore, \textbf{assume} that in the town from the original problem, there is \textbf{at least one path along sidewalks from each house to each other house} in the town, although some of the sidewalks on the path may be longer than 100m. After hiring the appropriate number of vendors (i.e., one for each market), each of whom lives in some house in the town, the leaders have to decide which vendor will sell in which market. The goal is to minimize the total commuting distance of the vendors, where the commuting distance for a vendor to a market is defined to be: the length of the shortest route from the vendor's home to some home in a market. The town leaders want to know which vendor should serve each market. (Note that some vendors' home-to-market routes may include sidewalks longer than the 100m limit, but we assume that vendors are OK with that on their commute. They'll walk their bikes if needed.) We call this the Vendor Assignment Problem (VAP). The following two problems will be instrumental in designing an algorithm to solve VAP. You should assume that efficient solutions to each exist (and they do!). \begin{description} \item[{All Pairs Shortest Path (APSP):}] takes as input a weighted graph $G=(V,E)$ and returns a $|V| \times |V|$ matrix whose entries are 1) $dist(u,v)$, the shortest distance from vertex $u$ to vertex $v$, and 2) $pred(u,v)$, the second to last vertex on the shortest path from $u$ to $v$. \item[{Minimum Cost Bipartite Matching (MCBM):}] takes as input a bipartite graph $G=(V\cup W, E)$ with costs $c_e, \forall e\in E$, and returns a perfect matching of least total cost if such a matching exists. Note that sets $V$ and $W$ are disjoint, costs are non-negative, and $|V| = |W| = n$. \end{description} Now solve the following problems: \begin{enumerate} \item Briefly explain why any scenario in which all vendors live in different markets might be considered a "trivial instance". \item Make a sketch that you believe illustrates a \textbf{small but not trivial} instance of the problem, and augment the sketch with an optimal solution. \item Give symbolic names to the quantities that matter in VAP, and use those names to describe \textbf{both} the \textbf{general form of an instance} (including any constraints on what makes it valid) of the problem, and the \textbf{general form of a solution} (including what makes a solution valid and good). If you're looking for a format, consider the various problems (including APSP and MCBM) that we've represented using symbolic names in this quiz/assignment (plus your textbook reading and our work in class, of course!). \item Now use clear pseudocode (or \textbf{very very clear} C++, Java, or Racket) to give an algorithm to solve VAP given an instance of the original ice cream vendor problem that has been augmented with labels for each house indicating its market. You \textbf{must} make use of the APSP and MCBM algorithms in your solution, And they should make your solution fairly compact and simple. (You can think of this as reducing VAP to a combination of APSP and MCBM.) \end{enumerate} For further reading on APSP and MCBM, see \url{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/22-apsp.pdf}, and \url{http://theory.stanford.edu/~tim/w16/l/l5.pdf}. % Emacs 25.2.1 (Org mode 8.2.10) \end{document}