% Created 2018-01-27 Sat 09:04 \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{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}}} \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 2017W2: Assignment 2} \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.) 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. Submit by the deadline \textbf{Monday 5 Feb at 10PM}. 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{Wall-E Loman} \label{sec-1} \begin{quote} \emph{\ldots{} the air doesn't smell so foul here. If in doubt \ldots{} always follow your nose.} --- Gandalf \end{quote} The \emph{Traveling Salesperson Optimization Problem} (TSP) can be defined as follows: you are given a set $\{ C_1, C_2, \ldots, C_n \}$ of cities. For every two cities $C_i$, $C_j$, there is a cost $c_{i,j}$ for traveling from city $C_i$ to city $C_j$ (equal to the cost of travelling from $C_j$ to $C_i$). Your job is to find the lowest cost path that starts at $C_1$, travels through every other city, and returns to $C_1$. You are not allowed to go through a city more than once (except for $C_1$ which appears both at the start and at the end of your trip). \begin{enumerate} \item Briefly but clearly justify why the number of valid solutions to an instance of TSP with $n$ cities is $(n-1)!$. \textbf{Note:} a "brief justification" is not a proof but should contain the key ideas that would enable a correct proof. \item Imagine that you have a brute force algorithm that builds up a partial path step-by-step as a candidate solution to TSP. Each time it has visited all other nodes, it returns to $C_1$ and measures the cost of the solution. Complete the following small instance of TSP by labelling each edge with a \emph{distinct} cost so that it can act as a counterexample to the correctness of the following heuristic for the algorithm: "always add as the next city in the partial path the cheapest not-yet-visited city to reach". Briefly describe how the algorithm could run and produce an incorrect solution. (E.g., "the algorithm starts at $C_1$ then the heuristic guides it to select $C_2$ then $C_3$ then $C_4$ as the "next closest" city at each step, but this produces a total of XXX, whereas the following solution produces a lower total \ldots{}".) Instance: \includegraphics[width=0.2\textwidth]{figures/2017W2-four-city-graph.png} \item The correctness of the following heuristic relies on a (very sensible) assumption about the costs of travelling from one city to the next. What is the assumption, and why is it necessary? Heuristic: "discard any partial path that is more expensive than the cheapest complete path found so far". \item Here is another heuristic for the algorithm for instances with at least 3 cities: "never include city $C_3$ in a partial path until after city $C_2$ has been included". Sketch the key points in a proof that this heuristic \textbf{is} correct. I.e., the algorithm run with this modification \textbf{will} produce an optimal solution. \end{enumerate} \section{The Antepenultimate Jedi} \label{sec-2} You want to hire for a movie the best stars to draw the most people to the theaters. For each star, you have a positive number indicating their "draw". You can hire as many stars as you like. Certain actors consider themselves "big fish". If you include a big fish with draw $x$, you may not include any other star with draw $k$ such that $\frac{x}{2} < k \leq x$. \begin{enumerate} \item For this question only, \textbf{every actor} considers themselves a "big fish". Give and briefly justify the correctness of an efficient greedy algorithm to solve this problem. (Your algorithm is likely to be simple enough that a clear English explanation is best, but clear and short pseudocode is also acceptable.) \item We now alter the problem for this and subsequent parts. In the new version, the actor with the highest draw overall is automatically a big fish, whether or not they're in your movie. Additionally, any \emph{other} actor with draw $x$ is a big fish if there is no actor at all (whether or not they're in your movie) with draw $y$ such that $x < y < 2x$.\footnote{They're a big fish in a little pond.} So, for example, if the available stars have draw $[8, 10, 22, 3, 2, 30, 4]$ then 30 (as the highest draw actor) is a "big fish". 22 is not (because 30 is between 22 and 44). 10 is a "big fish" (because no other actor has draw between 10 and 20). 8 is not. 4 is a big fish. 3 and 2 are not. Give an instance that includes actors with draw 11 and 13 in which the optimal solution involves hiring both of these actors. \item Give an instance that includes actors with draw 11 and 13 in which no valid solution (whether optimal or not) involves hiring both actors. \item Give and briefly justify the correctness of an efficient, greedy algorithm to solve this problem. (Your algorithm may be simple enough that a clear English explanation is best, but clear and short pseudocode may work better.) \item Below we propose (suboptimal) algorithms to solve this problem. Give a \textbf{single} instance with three actors including one with draw 10 that serves as a counterexample to \textbf{all} the algorithms' optimality. That is, each algorithm will either fail to produce any valid solution or produce a suboptimal solution. Be sure to state: \textbf{the list of draws in your instance}, \textbf{the optimal solution and its total draw} and for each algorithm \textbf{the solution it produces and its total draw}. \begin{enumerate} \item Iterate through the stars in the order given. For each star, hire them if doing so would not invalidate the so-far-hired set of stars. \item Sort the stars in decreasing order of draw. Iterate through the sorted stars. For each star, hire them if doing so would not invalidate the so-far-hired set of stars. \item Sort the stars in decreasing order of draw. Iterate through the sorted stars. Hire the first (biggest) star. Then, for each subsequent star, hire them \textbf{unless} they are a big fish (in which case, skip them). \end{enumerate} \end{enumerate} \section{Blue, Gold, and Green} \label{sec-3} For its Blue-and-Gold fundraising campaign, UBC has found \emph{anchors}---major donors, each with a \emph{limit} (maximum amount they will donate)---and \emph{causes} to which the anchors will donate.\footnote{And which are then named for them, like the Belleville Urban Beautification Project or Wolfman Lunar Research Fund.} Each cause has a \emph{goal}, the maximum money that will go to the cause. \textbf{An anchor donates to at most one cause}, but \textbf{one cause may receive donations from many anchors}, and the total amount of the donations of anchors to a cause cannot exceed that cause's goal. The Blue-and-Gold Problem, or BGP, consists in determining how much money each anchor will give to each cause, subject to the constraints stated above. A BGP instance's solution is the maximum dollar amount that can be raised. (Assume limits are distinct, as are goals.) \begin{enumerate} \item An instance of BGP can be represented clearly and cleanly as a weighted, undirected, bipartite graph (where each edge has a \textbf{single} number as its weight). Draw the instance with limits $10, 100, 30, 40$ for anchors $a_1, a_2, a_3, a_4$, and goals $50, 80, 10$ for causes $c_1, c_2, c_3$. \item Below we propose (suboptimal) algorithms to solve this problem. Give a \textbf{single} instance with three limits $[100, 50, 200]$ and two goals of your choice that serves as a counterexample to \textbf{all} the algorithms' optimality. That is, each algorithm will either fail to produce any valid solution or produce a suboptimal solution. Be sure to state: \textbf{the list of goals for your instance}, \textbf{the optimal solution and the anchor/cause pairings that generate it} and for each algorithm \textbf{the solution it produces and the anchor/cause pairings that generate it}. Notes: (1) We use "limit" and "anchor" interchangeably. (2) All of these algorithms do the "right" thing when matching an anchor to a goal: They let the anchor donate the minimum of their limit and the money remaining before the goal is met and then update the money remaining for that goal. \begin{enumerate} \item Iterate through the anchors in the order given. For each anchor, assign them to the cause with the most money still left before reaching its goal. \item Sort the goals in decreasing order. Iterate through the goals, matching each with the largest anchor who has not already been assigned a goal. \item Sort each of the limits and the goals in decreasing order. Iterate through the anchors, matching each with the first remaining goal. (Remove a goal when its fundraising target has been met.) \end{enumerate} \item \textbf{PROBLEM CUT FROM ASSIGNMENT} \end{enumerate} \section{Oh Oh Oh} \label{sec-4} \begin{enumerate} \item Determine the worst case running time of the \verb~colorize~ algorithm as a function of both $n$ and $m$: \begin{verbatim} // G = (V, E) is an undirected graph, represented as an adjacency list function colorize(V, E) n = |V| m = |E| let Colors be a list of at least n distinct colors for i = 0 to n - 1: V[i].setvisited(False) for i = 0 to n - 1: DFS(V[i], (function(v): v.setcolor(Colors[i]))) \end{verbatim} where DFS is defined as: \begin{verbatim} function DFS(v, visitfunction) if not v.getvisited(): visitfunction(v) v.setvisited(True) for w in neighbours(v): DFS(w, visitfunction) \end{verbatim} \item Briefly justify how your bound applies to a complete graph, including how and why each piece of the code contributes to the bound. \item Describe in English what this algorithm does. Your description should be brief, clear, and precise. \end{enumerate} \section{O'd to a Pair of Runtimes} \label{sec-5} For this problem, we consider a dense, undirected graph and a simple path in that graph of length $k$. (A \emph{dense} graph has $m \in \Theta(n^2)$. A \emph{simple path} of length $k$ is a list of $k+1$ vertices where each subsequent pair of vertices is connected by an edge and no vertex appears more than once in the list.) \textbf{ASSUME $k>0$.} \begin{enumerate} \item Give exact upper- and lower-bounds on $k$ in terms of $n$. (Note that "expressing $y$ in terms of $x$" means you \emph{can but need not} use $x$ in a function you provide to describe $y$.) \item Give an exact upper-bound on $m$ in terms of $n$. \item Briefly justify why it is not possible to give an exact lower-bound on $m$ in terms of $n$ using the information above. \item Give a good $\Theta$-bound on each of the following functions from above. Express your bound in terms of as few as possible of the variables $k$, $n$, and $m$. \begin{enumerate} \item $n \lg(knm)$ \item $(k+m)(n+k)$ \item $k^3 + m \lg m$ \end{enumerate} \end{enumerate} \section{eXtreme True And/Or False} \label{sec-6} Each of the following problems presents a scenario in a graph and a statement about that scenario. For each one, exactly one of the following is correct: \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} \textbf{Briefly} justify the correct answer to each one. \begin{itemize} \item 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. \item 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. \item 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. (Indicate which is which!) \end{itemize} 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 vertex other than the starting/end vertex (which only appears twice). Unless stated otherwise, we assume graphs have no self-loops (edges from a vertex to itself). \begin{enumerate} \item \textbf{Scenario:} An undirected graph with $n \geq 2$ and at least $\frac{n^2}{4}$ edges. \textbf{Statement:} The graph is connected. \item \textbf{Scenario:} A tree (undirected) found by DFS run on a connected, undirected graph with $n \geq 2$. \textbf{Statement:} The degree of every node in the tree is two or less. \item \textbf{Scenario:} A weakly-connected but \textbf{not} strongly-connected, directed graph with $n \geq 2$. \textbf{Statement:} A simple cycle of length $n+1$ exists. \item \textbf{Scenario:} A connected, undirected graph with $n \geq 3$. \textbf{Statement:} The graph includes at least $2^n$ different simple cycles. \end{enumerate} \section{BONUS!} \label{sec-7} This is worth only one course bonus point (for a clearly on-track answer that makes significant progress) or two course bonus points (for a beautiful, complete answer), which is way too little for how much work it is. On the other hand, how fun is it?! (On a correct group submission, each group member earns the number of bonus points noted above.) Give and prove the correctness of an achievable, asymptotic upper-bound (in terms of $n$) on the number of optimal solutions to an interval scheduling problem instance with $n$ intervals. \emph{Hint:} it isn't an answer in online quiz \#4! Note that you'll need to give your bound, give a way to construct an instance of an arbitrary size $n$ that has a number of solutions in your bound, and show that no higher bound is possible. % Emacs 25.2.1 (Org mode 8.2.10) \end{document}