\documentclass[12pt]{article}
\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}
\usepackage{amsfonts}
\usepackage{graphicx}
% \usepackage{geometry}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2009 \\
	\rm
	Homework 10a\\
	Due Thursday, April 2
\end{center}

	\textbf{Reminder:}  The second exam will be given out on Thursday, April 9 in class.  It will be due at 5 PM on Tuesday,  April 14 in the CS office.  The exam will primarily cover material on graph algorithms and NP-completeness and related topics, but techniques from the first part of the course may be useful in some of your solutions.  For this exam, you may use your own lectures notes, any notes that you prepare before the exam, and your solutions and our sample solutions for the homework problems.  No other materials are permitted.

\begin{enumerate}

\item \Points{20} \Name{The Partition and Bin Packing Problems!}
\begin{enumerate}
	\item Let $S = \{a_1, \ldots a_n\}$ and let $f:S \rightarrow {\Bbb Z}_{+}$ (that is, $f$ maps elements of $S$ to the positive integers).  A \emph{partition} of $S$ is a pair of sets $A, B$ such that $S = A \cup B$ and
$A \cap B = \emptyset$.  The Partition Problem asks if there exists a partition of $S$ into sets $A, B$ such that 
\[  \sum_{x \in A} f(x) = \sum_{x \in B} f(x)\]
Prove that the Partition Problem is NP-complete using a reduction from a problem that we have seen in class or on a previous homework assignment.  (Notice that while this definition of the problem is seemingly awkward, it permits us to have multiple items with the same value, that is  a ``multiset'' of numbers.)

	\item The Bin Packing Problem is the following:  We are given a collection of objects
	$S= \{a_1, \ldots, a_n\}$, a function $s:S \rightarrow {\Bbb Z}_{+}$ indicating the ``size'' of
	each object, a bin capacity $C$ such that $C$ is greater than or equal to the size of the largest
	object, and a target $t$.  The question is whether or not it is possible to pack all of the objects
	in $S$ into $t$ or fewer bins, each of capacity $C$.  Prove that Bin Packing is NP-complete.
	
\end{enumerate}



\item \Bonus{20} \Name{A Strange NP-complete Problem!}
A bipartite graph is one in which the vertices can be partitioned into two sets $X$ and $Y$ such that every edge has one endpoint in $X$ and one endpoint in $Y$.  Consider the problem in which we are given a bipartite graph $G=(X \cup Y, E)$ and two non-negative integers $x$ and $y$.  Our objective is to determine whether or not there exists a vertex cover for $G$ that uses at most $x$ vertices in $X$ and at most $y$ vertices in $Y$.  Prove that this problem is NP-complete.  
\end{enumerate}

\end{document}