%---------change this for every latex homework
\def\yourid{mst3k}
\def\collabs{list collaborators's computing IDs}
\def\sources{Cormen, et al, Introduction to Algorithms. \emph{(add others here)}}
% -----------------------------------------------------
\def\duedate{Tuesday, May 3, 2022 at 11:30 pm }
\def\duelocation{via Gradescope}
\def\htype{Adv}
\def\hunit{D}
\def\hnumber{}
\def\course{{cs4102 - algorithms - spring 2022}}%------
%-------------------------------------
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,amssymb, graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.25in,right=1.25in,centering,letterpaper]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.1,0.6,0.4}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{myheadings}
\markboth{\yourid}{\yourid}
\usepackage{clrscode}
\usepackage{tabularx}
\newcolumntype{Y}{>{\centering\arraybackslash}X}
\usepackage{framed}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\handout}{
\renewcommand{\thepage}{Unit \hunit: \htype~Homework \hnumber~-~\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}\hunit\hnumber{\Large\MakeLowercase{\htype}}(\yourid)}}
}
\end{center}
\vspace*{1mm}
\hrule
\vspace*{1mm}
{\footnotesize \textbf{Collaboration Policy:} You are encouraged to collaborate with up to 3 other students, but all work submitted must be your own {\em independently} written solution. List the computing ids of all of your collaborators in the \texttt{collabs} command at the top of the tex file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite by naming the book etc.\ or listing a website's URL. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for a complete description of the collaboration policy.
\vspace*{1mm}
\hrule
\vspace*{2mm}
\noindent
\textbf{Collaborators}: \collabs\\
\textbf{Sources}: \sources}
\vspace*{2mm}
\hrule
\vskip 2em
}
\newcommand{\solution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution:} #1\color{black}}
%\newcommand{\solution}[1]{}
\newcommand{\altsolution}[1]{}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newcommand{\Z}{\mathbb{Z}} % This might be useful for Integers!
\begin{document}
\thispagestyle{empty}
\handout
%----Begin your modifications here
\begin{problem} IKEA Grill \end{problem}
IKEA is growing in popularity across the US, however their stores are only found in a handful of larger metropolitan areas. While their main product is furniture, they have become known for their signature meatballs. To increase profits and make their delicious food more accessible, they have decided to open local IKEA Grill restaurants in towns across the country. Restaurant storefronts are expensive to rent and maintain, so they are happy with customers needing to drive at most to the next town over to get their IKEA meatball fix. Specifically, their goal is that every town in America either has an IKEA Grill, or its neighboring town has an IKEA Grill.
Given a graph representing the towns (as vertices) and roads between them (edges connecting neighboring towns), the \emph{IKEA Grill} problem is to decide whether $k$ IKEA Grill locations can be placed in order to ensure that each town or its neighbor has an IKEA Grill location. Show that \emph{IKEA Grill} is NP-Complete.
Note: You are not being asked to explicitly solve the \emph{IKEA Grill} problem; you are only required to show that it is NP-Complete.
\solution{ Your solution here! }
\begin{problem} Backpacking, Revisited \end{problem}
After your first successful backpacking adventure (Unit C's Advanced, Problem 1), you have decided to return to
Shenandoah National Park. Similar to before, you and your friend have completed your packing list, and you need
to bring $n$ items in total, with the weights of the items given by $W = (w_1, \ldots, w_n)$. Your goal
this time is to divide the items between the two of you such that the difference in weight is as small as possible.
There is no longer a restriction on the total number of items that each of you should carry.
Here, we will define a decisional version of this \textsc{Backpacking} problem:
\begin{framed}
\noindent
\textsc{Backpacking}: Given a sequence of non-negative weights $W = (w_1, \ldots, w_n)$ and a target weight difference
$t$, can you divide the items among you and your friend such that the weight difference between backpacks is at most $t$?
\end{framed}
\begin{enumerate}
\item Show that the \textsc{Backpacking} problem defined above is $\mathsf{NP}$-complete (namely, you should
show that $\textsc{Backpacking} \in \mathsf{NP}$ and that \textsc{Backpacking} is $\mathsf{NP}$-hard). For this
problem, you may use the fact that the \textsc{SubsetSum} problem is $\mathsf{NP}$-complete:
\begin{minipage}[t]{\linewidth}
\begin{framed}
\textsc{SubsetSum}: Given a sequence of non-negative integers $a_1, \ldots, a_n$
and a target value $t$, does there exist
a subset $S \subseteq \{ 1, \ldots, n \}$ such that $\sum_{i \in S} a_i = t$?
\end{framed}
\end{minipage}
\solution{ Your solution here! }
\item Your solution to Unit C Advanced's Problem 1 can be adapted to solve this version of the \textsc{Backpacking} problem
in time that is {\em polynomial} in $n$ and $M$, where $M = \max(w_1, \ldots, w_n)$ is the maximum weight of all of the items. Why did this
not prove $\textsf{P} = \textsf{NP}$? ({\em Conversely, if you did prove that $\textsf{P} = \textsf{NP}$, there's a nice
check waiting for you at the \href{https://www.claymath.org/millennium-problems/p-vs-np-problem}{Clay Mathematics Institute}.})
\solution{ Your solution here! }
\end{enumerate}
\begin{problem} Gradescope Submission \end{problem}
Submit a version of this \verb|.tex| file to Gradescope with your solutions added, along with the compiled PDF. You should only submit your \verb|.pdf| and \verb|.tex| files.
\end{document}