%\def\solutionMode{TRUE}
\documentclass[11pt]{article}
\usepackage{573}
%
% ======================================================================
\begin{document}
%\thispagestyle{empty}
%\headers{\Course{}}{Homework 0 (due 8/30/07)}{\Semester{}}
\begin{center}
{\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 1, due Monday, September 16, 23:59:59, \Year}
\\[0.25in]
{\Large\bf Version 1.2}
\end{center}%
\begin{center}
\LARGE %
\begin{tabular}{|p{2in}|p{2in}|}
\hline \multicolumn{2}{|l|}{Name:} \\\hline Net ID: &
Alias: \\\hline%
\end{tabular}%
\end{center}%
%----------------------------------------------------------------------
\medskip
\noindent
Neatly print your name(s), NetID(s). Staple this sheet to the top of
your homework. If you are on campus, submit the homework by submitting
it in the homework boxes in the basement of SC.
%----------------------------------------------------------------------
\medskip
\noindent
\textbf{Note:} You will be held accountable for the appropriate
responses for answers (e.g. give models, proofs, analysis, etc). For
\NPComplete{} problems you should prove everything rigorously, i.e.
for showing that it is in \NP{}, give a description of a certificate
and a polynomial time algorithm to verify it, and for showing problems
are \NPHard{}, you must show that your reduction is polynomial time
(by similarly proving something about the algorithm that does the
transformation) and proving both directions of the `if and only if' (a
solution of one is a solution of the other) of the many-one reduction.
\bigskip
\fbox{
\begin{minipage}{0.9\linewidth}
This homework should be easier than hw0. You are {\bf \em{{\Huge
encouraged}}} to discuss problems in this homework with
people, but should submit your homework on your own.
\end{minipage}}
\bigskip%
\centerline{%
\fbox{%
\small%
\begin{minipage}{0.4\linewidth}%
\begin{minipage}{1.3\linewidth}%
Only of myself I know how to tell,\\
my world is as narrow as an ant's.\\
like an ant too my burden I carry,\\
too great and heavy for my frail shoulder.\\
\\
My way too - like the ant's to the treetop -\\
is a way of pain and toil;\\
a gigantic hand, assured and malicious,\\
a mocking hand hinders\\
\\
All my paths are made bleak and tearful\\
by the constant dread of this giant hand.\\
\\
Why do you call to me, wondrous shores?\\
Why do you lie to me, distant lights?\\
\hspace*{2cm} -- Only of Myself, Rachel
\end{minipage}
\end{minipage}
}
}%
% \newpage%
\section*{Required Problems}
% ===================================================================
%
\begin{compactenum}[\color{red} \huge \bf 1.]%
%
\item \HWProblem{20}{Poly time subroutines can lead to exponential
algorithms.}{% \points{20}
Show that an algorithm that makes at most a constant number of
calls to polynomial-time subroutines runs in polynomial time,
but that a polynomial number of calls to polynomial-time
subroutines may result in an exponential-time algorithm.
}{}{}{}{}
\item \HWProblem{50}%
{Beware of algorithms carrying oracles.}%
{%
Consider the following optimization problems, and for each one
of them do the following:
\begin{compactenum}[\qquad (I)]
\item \points{2} State the natural decision problem
corresponding to this optimization problem.
\item \points{3} Prove that this decision problem is
\NPComplete by showing a reduction from one of the
\NPComplete problems seen in class. If you already seen
this problem in class state ``seen in class'' and move on
with your life.
\item \points{5} Assume that you are given an algorithm
that can solve the decision problem in polynomial
time. Show how to solve the original optimization problem
using this algorithm in polynomial time.
\end{compactenum}
Prove that the following problems are \NPComplete{}.
\begin{compactenum}[\quad(A)]
\item \points{10} \OptProblem{SET COVER}{%
Collection $\mathcal{C}$ of
subsets of a finite set $S$.}%
{Compute the minimum $k$, and the sets $S_1, \ldots, S_k$
in $\mathcal{C}$, such that $S \subseteq \cup_{i=1}^{k} S_i$.}
\item \points{10}%
\OptProblem{MIN BIN PACKING}%
{Finite set $U$ of items, a size $s(u) \in \ZZ^+$ for each
$u \in U$, an integer bin capacity $B$}%
{Compute the minimum $k$, and a partition of $U$ into
disjoint sets $U_1, \ldots, U_k$, such that the sum of
the sizes of the items inside each $U_i$ is $B$ or
less.}
\item \points{10} \OptProblem{HITTING SET}%
{A \emphi{ground set} $U = \brc{1, \ldots, n}$, and a set
$\Family = \brc{U_1, \ldots, U_m}$ of subsets of $U$.
}%
{Find the smallest set $S' \subseteq U$, such that $S'$
hits all the sets of $\Family$. Specifically, $S'
\subseteq U$ is a \emphi{hitting set} if for all $U_i
\in \Family$, we have that $S'$ contains at least one
element of $U_i$.}
\item \points{10}%
\OptProblem{Max Degree Spanning Tree}%
{Graph $\Graph=(\Vertices,\Edges)$.}%
{Compute the spanning tree $\Tree$ in $\Graph$ where the
maximum degree of a vertex in $\Tree$ is minimized.}
\item \points{10}%
\OptProblem{Partition into independent sets.}%
{Graph $\Graph=(\Vertices,\Edges)$.}%
{Compute the minimum $k$, and the partition of $\Vertices$
into $k$ sets $\Vertices_1, \ldots, \Vertices_k$, such
that for every edge $uv$ of $\Graph$, there exists two
distinct indices $i$ and $j$, such that $u \in
\Vertices_i$, and $v \in \Vertices_j$.}
\end{compactenum}
}{}{}{}{}
\item \HWProblem{30}%
{Dominating set.}%
{%
Consider the following problem (which is \NPComplete):
\OptProblem{Dominating set}%
{Graph $\Graph=(\Vertices,\Edges)$ and an integer $k$.}%
{Is there a subset $X \subseteq \Vertices$ of size $k$,
such that each vertex of $\Vertices \setminus X$ is
adjacent to some vertex of $X$.}
Consider the variant where $\Vertices = \brc{1,\ldots, n}$, and
$ij \in \Edges$, implies that $\cardin{i - j} \leq 8$. We refer
to this variant as the \ProblemC{$8$Dominating set} problem.
Either prove that \ProblemC{$8$Dominating set} is \NPComplete,
or alternatively, provide a polynomial time algorithm for
solving it. }{}{}{}
\end{compactenum}
\end{document}
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------
%----------------------------------------------------------------------