\documentclass[11pt]{article}
\usepackage{fullpage}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
       \hbox to 6.25in { {\bf CSE 202: Algorithms}
         \hfill #2}
       \vspace{4mm}
       \hbox to 6.25in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.25in { {#3 \hfill #4} }
      }
   }
   \end{center}
}

\newcommand{\homework}[2]{\handout{#1}{Winter 2019}{Instructor:
Daniele Micciancio}{#2}{Problem Set #1}}

\begin{document}
\homework{4}{Due: March 6, 2019}

\section*{Problem 1: Balanced Simple Path}
Recall the Balanced-Path problem from the midterm exam:
Let $G$ be an $n$-node directed graph whose edges $e \in E$
are labelled either $-1$ or $+1$. A path $e_1,\ldots,e_k$
in $G$ is \emph{balanced} if it contains the same number of $+1$ and $-1$.
Given $G$ and two nodes $s,t$, the problem is
to decide whether there is a balanced path from $s$ to $t$.
(For simplicity, in the midterm, you were also provided the length of the desired
path $k$. It is easy to adapt the solution from the midterm to work without
knowledge of $k$.)
Crucially, the problem in the midterm, did \emph{not} require the path to be simple.
(A path is \emph{simple} if it never visits the same node twice.)

Now consider the following variant:
the Balanced-Simple-Path problem is defined just like the Balanced-Path problem,
but the question is to determine if there is a simple path from $s$ to $t$ which is
balanced.
Show that the Balanced-Simple-Path problem in NP-complete.
(You may reduce from any of the NP-complete problems presented in chapter 8 of the textbook.)

\section*{Problem 2 (KT 8.7): 4-Dimensional Matching}
Since the $3$-Dimensional Matching Problem is NP-complete, it is natural to expect that the corresponding
$4$-Dimensional Matching Problem is at least as hard. Let us define 4-Dimensional Matching as follows.
Given sets $W,X,Y$ and $Z$, each of size $n$, and a collection $C$ of ordered 4-tuples of the form
$(w_i,x_j,y_k,z_l)$, do there exist $n$ 4-tuples from $C$ so that to two have an element in common?
Prove that 4-Dimensional Matching is NP-complete.

\section*{Problem 3: Domino Tiling}

You are given a subset of the $n \times n$ grid of squares, 
described as an $n \times n$ boolean matrix.
(True meaning the square is in the subset, False meaning
it is not.)
The question is whether it is possible to cover precisely
this subset with $1 \times 2$ rectangular dominoes, subject to the following
constraints:    
Each domino must be placed either horizontally or vertically, covering two
adjacent squares of the grid.   
Both squares must be in the subset.  
No two dominoes can cover the same square.  
Each square in the subset must be covered by some domino.
Give an efficient algorithm for deciding whether it is possible, given as
input the boolean matrix describing the subset of the grid.

\section*{Problem 4 (KT 10.9): MaxCut for trees}

Give a polynomial time algorithm for the following problem.
We are given a binary tree $T=(V,E)$ with an even number of nodes, and a nonnegative weight on each edge.
We wish to find a partition of the nodes $V$ into two sets of equal size so that the weight of the cut
between the two sets
(i.e., the total weight of the edges with one end in each set)
is as large as possible.
(Note that the restriction that the graph is a tree is crucial here.
The MaxCut problem is NP-hard in general graphs.)

\end{document}