% Created 2018-11-19 Mon 17:16
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\usepackage{csquotes}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{algpseudocode}
\usepackage[margin=0.75in]{geometry}
\usepackage{nth}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,shapes.misc,calc,arrows,patterns,decorations.pathreplacing}
\usepackage{ccicons}
\usepackage{calc}
\usepackage{fancyhdr}
\usepackage{fancyvrb}
\usepackage{hyperref}
\usepackage{nopageno}
\usepackage{enumitem}
\usepackage{multicol}
\usepackage{braket}
\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}
\setlength{\columnseprule}{1pt}
\newcommand{\bonusmarksamt}[1]{\textbf{[#1~BONUS~marks]}}
\newcommand{\bonusmarkamt}[0]{\textbf{[1~BONUS~mark]}}
\newcommand{\marksamt}[1]{\textbf{[#1~marks]}}
\newcommand{\markamt}[0]{\textbf{[1~mark]}}
\newcommand{\fillinMC}[1]{\fillinMCmath{\mbox{#1}}}
\newcommand{\fillinMCmath}[1]{\begin{tikzpicture}\draw circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCsoln}[1]{\fillinMCmathsoln{\mbox{#1}}}
\newcommand{\fillinMCmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] circle [radius=0.5em];\end{tikzpicture}\ #1}
\newcommand{\fillinMCAll}[1]{\fillinMCAllmath{\mbox{#1}}}
\newcommand{\fillinMCAllmath}[1]{\begin{tikzpicture}\draw (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinMCAllsoln}[1]{\fillinMCAllmathsoln{\mbox{#1}}}
\newcommand{\fillinMCAllmathsoln}[1]{\begin{tikzpicture}\draw[black, fill=blue] (0,0) rectangle (1em,1em);\end{tikzpicture}\ #1}
\newcommand{\fillinblank}[1]{\fillinblankmath{\mbox{#1}}}
\newcommand{\fillinblankmath}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{\LARGE\phantom{#1}}\endgroup}
\newcommand{\fillinblanksoln}[1]{\fillinblankmathsoln{\mbox{#1}}}
\newcommand{\fillinblankmathsoln}[1]{\begingroup\setlength{\fboxsep}{1em}\setlength{\fboxrule}{2pt}\fbox{{#1}}\endgroup}
\newcommand{\answerbox}[1][3\baselineskip]{%
\noindent\setlength{\fboxrule}{2pt}\framebox[0.7\linewidth]{%
\raisebox{2pt}[0pt][#1]{}%
}\par\medskip%
}
\usepackage{collcell,array}
\newcommand{\shiftdown}[1]{\smash{\raisebox{-.5\normalbaselineskip}{#1}}}
\newcolumntype{C}{>{\collectcell\shiftdown}c<{\endcollectcell}}
\newcommand{\shiftup}[1]{\smash{\raisebox{.5\normalbaselineskip}{#1}}}
\def\sequence#1#2{\dsequence{#1}{1}{#2}}
\def\dsequence#1#2#3{#1_{#2}, \ldots, #1_{#3}}
\newtheorem{fact}{Fact}
\def\imax{$\texttt{S}_{\max}$}
\def\iprevmax{previous\_$\texttt{S}_{\max}$}
\def\deleted{\texttt{covered}}
%\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by/4.0/}{Creative Commons Attribution 4.0 International License. \ccby}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
\makeatletter
\def\@myproof#1[#2]{\trivlist \item [\hskip\labelsep{\bf #1 {#2}: }]}
\def\@begproof#1{\@ifnextchar[{\@myproof{#1}}{\@myproof{#1}[\unskip$\,$]}}
\newenvironment{solution}{\vskip -10pt\leavevmode\@begproof{Solution}}{\endtrivlist}
\def\sopt{S_{\textit{\scriptsize opt}}}
\makeatother
\fancyhead{}\fancyfoot[C]{\tiny This work is licensed under a \href{http://creativecommons.org/licenses/by-nc/4.0/}{Creative Commons Attribution-NonCommercial 4.0 International License. \ccbync}\\ For license purposes, the author is the University of British Columbia.}\pagestyle{fancyplain}
\usepackage{mdframed}
\BeforeBeginEnvironment{minted}{\begin{mdframed}}
\AfterEndEnvironment{minted}{\end{mdframed}}
\date{\today}
\title{CPSC 320 2018W1: Assignment 5}
\hypersetup{
  pdfkeywords={},
  pdfsubject={},
  pdfcreator={Emacs 25.2.2 (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.)

Submit by the deadline \textbf{Thursday November 29, 2018 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! When uploading assignments to gradescope,
marks will be docked if pages are not properly assigned to each question.
\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}

Before  we  begin, a  few  notes  on  pseudocode  throughout CPSC  320:  Your
pseudocode need  not compile in  any language,  but it must  communicate your
algorithm  clearly,  concisely,  correctly, and  without  irrelevant  detail.
Reasonable  use of  plain  English is  fine in  such  pseudocode. You  should
envision your  audience as  a capable  CPSC 320  student unfamiliar  with the
problem you are solving. If you choose  to use actual code, note that you may
\textbf{neither} include what we consider to  be irrelevant detail \textbf{nor} assume that
we understand  the particular language  you chose.  (So, for example,  do not
write  \texttt{\#include <iostream>}  at  the  start of  your  pseudocode, and  avoid
idiosyncratic    features   of    your   language    like   Java's    ternary
(question-mark-colon) operator.)

\medskip

\section{NP true or false}
\label{sec-1}
Let $X$ and $X'$ be problems in NP.
State whether you think each of the following statements is true,
false, or an open question. Give a short explanation of your answer.

\begin{enumerate}
\item The problem $X \cup X'$ is always in NP.

\item If $X \le_p X'$ and $X$ is in P, then $X'$ must be in P.

\item If both $X \le_p X'$ and $X' \le_p X$, then both $X$ and $X'$ must be
NP-complete.
\end{enumerate}

\section{Scheduling classes}
\label{sec-2}
A college wishes to offer evening courses and has $n$ possible courses
that can be offered. There are $k$ students interested in taking a
course and each student is interested in some subset of the $n$
possible courses. To manage costs, the college has a bound $b$ on
the number of courses it is willing to actually offer. Is there a way
to choose $b$ courses out of the $n$ possibilities so that every
student can take a course that interests them?
Formally, an instance of the CS problem consists of
\begin{itemize}
\item a set $C$ of $n$ possible courses, numbered 1 through $n$,
\item subsets $S_1, S_2, \ldots, S_k$ of $\{ 1,2,\ldots, n\}$,
(the courses of interest to each of the students), and
\item a bound $b$ (the maximum number of classes actually offered).
\end{itemize}
The problem is to determine whether there is a subset $B$
of $\{1,2,\ldots,n\}$, where the size of $B$ is $\le b$,
such that $B\cap S_i$ is not empty for all $i$, $1\le i\le k$.

\begin{enumerate}
\item Describe an efficient reduction from the Vertex Cover problem to the 
Class Scheduling (CS) problem.

\item Your reduction maps instances $(G,p)$ of Vertex Cover to instances
$(C, S_1, \ldots, S_k, b)$ of CS. Show that $G$ has a vertex cover
of size at most $p$ if and only if in the mapped instance $(C, S_1,
   \ldots, S_k, b)$, there is a set of courses of size at most $b$
such that every student can take a course that interests them.
(Remember that you need to two parts here, one for "if" and one
for "only if".)

\item Explain why your reduction runs in polynomial time.

\item Explain why CS is \emph{NP}-complete.
\end{enumerate}
\section{Connected dominating set}
\label{sec-3}
In quiz  5 we described the  problem of finding a  \emph{connected dominating set}
   with at most $K$ vertices in a  graph $G = (V, E)$ (a connected dominating
   set is a dominating  set $W$ where the elements of  $W$, together with any
   edge of $G$ that connects two of them, form a connected subgraph of $G$).

In the solutions  we described the following reduction from  the vertex cover
   problem to the connected dominating set problem.

\begin{quote}
  Given  an instance $(G,K)$  of the vertex  cover problem,
  construct a graph  $G'$ by first creating  a copy of $G$. Next,  add a new
  vertex $v^*$, and  add the edges $\{v^*,  v \}$ for each $v  \in V$. Then,
  add one vertex $v_e$  for each edge $e \in E$,  and connecting this vertex
  to the  endpoints of $e$. That  is, if $e =  \{x, y\}$ then add  the edges
  $\{v_e, x \}$  and $\{ v_e, y  \}$. Finally, add two new  vertices $z$ and
  $z'$  and add  the two  edges $\{v^*,z\}$  and $\{v^*,z'\}$.  Map instance
  $(G,K)$ to  instance $(G',K+1)$ of  the connected dominating  set problem.
\end{quote}

\begin{enumerate}
\item Explain why this reduction is correct. That is, prove that the instance of
the vertex cover problem  has a Yes answer is and only  if the instance of
the connected dominating set problem produced  by the reduction also has a
Yes answer.

\item Using the  fact you  proved  in part  (1),  prove that  the maximum  leaf
spanning tree problem is NP-complete.
\end{enumerate}
% Emacs 25.2.2 (Org mode 8.2.10)
\end{document}