\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 2007 \\
	\rm
	Homework 11a\\
	Due Thursday, April 12
\end{center}

\begin{itemize}
	\item \emph{Reminder:}  The second exam will be given out on Thursday, April 12 in class.  You may choose any 24 hour block between Thursday, April 12 and Tuesday, 	April 17 to take the exam.  The exam will be due back no later than Tuesday, April 	17 in class.  As with the last exam, you may use your lecture notes, homework 	solutions, and solution sets that I have provided.  No other resources (e.g. books, 
	electronic resources, oracles) are permitted.

	\item \emph{No rubles (``extensions'') may be used on this assignment.}  The solution set for this assignment will be given out in class on Thursday.
	
		\item \emph{You have a choice of two problems on this assignment.  Problem 1 is the recommended choice.  However, if you want a bigger challenge, you may do Problem 2 instead.  If you do Problem 2, you need not write up your solution.  Instead, you can set up a time to show it to me on my whiteboard.}
	\end{itemize}

\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 \Points{20} \Name{A Strange NP-complete Problem! (Alternate for Problem 1)}
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.  \emph{Note:  This problem is more difficult than Problem 1.  As such, you can show me your solution in person rather than writing it up.  Please show me your solution before classtime on Thursday or at least get in touch by that time to set up a time to meet.}

\end{enumerate}

\end{document}