\documentclass[12pt]{article}

%\usepackage{algo}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{tikz,fullpage,url,amssymb,amsmath,epsfig,color,xspace,alltt,mathtools}
\usetikzlibrary{shapes,chains,positioning,arrows.meta}
\usepackage[pdftitle={CS 341 Assignment 5},%
pdfsubject={University of Waterloo, CS 341, Winter 2026},%
pdfauthor={MP}]{hyperref}
\usepackage{cleveref}
\usepackage{enumerate}
\usepackage{sepfootnotes}
\usepackage{tcolorbox}
\newlength{\nodeLength}
\newcommand{\Node}{A}
\newcommand{\setnode}[1]{
  \settowidth{\nodeLength}{#1}
  \renewcommand{\Node}[1]{
    \Tcircle[name=#1]{\makebox[\nodeLength]{##1}}
  }
}
\setnode{99}
\usepackage{stmaryrd}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\renewcommand{\thesubsection}{Question \arabic{subsection}}
\newtheorem{claim}{Claim}
\Crefname{claim}{Claim}{Claims}
\usepackage{complexity}

\usepackage{algorithmic}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

\newcommand{\pts}[1]{%
  \ifnum\pdfstrcmp{#1}{1}=0
    \textbf{#1~mark}%
  \else
    \textbf{#1~marks}%
  \fi
}
\newcommand{\pt}{{\textbf{1 mark}}}
\newcommand{\opt}{\mathsf{OPT}}


\usepackage{tikz}
\usepackage{wrapfig}

\tikzstyle{vertex}=[circle, draw, inner sep=1pt, minimum size=15pt]

\usetikzlibrary{arrows.meta}
\tikzset{>={Latex[width=2mm,length=2mm]}}

\tikzset{
  dot/.style={circle, draw, fill=black, inner sep=0pt, minimum width=4pt},
}
\usepackage{graphicx}
\graphicspath{ {images/} }


\begin{document}

\begin{center}
{\Large\bf University of Waterloo}\\
\vspace{3mm}
{\Large\bf CS 341 Winter 2026}\\
\vspace{2mm}
{\Large\bf Written Assignment 5}\\
%\vspace{3mm}
\textbf{Elena Grigorescu, Mark Petrick, Luke Schaeffer \\Copyright $\copyright$ 2026 Distribution (except by the authors) is prohibited. \\ ~\\
Due Date: Thursday, April 2 at 11:59pm to Crowdmark \\
All work submitted must be the student's own.}
\end{center}
\begin{itemize}
\item Make sure to read the Assignments section on the course webpage for instructions on submission and question expectations (``Instructions for Assignments"):  \\ \url{https://student.cs.uwaterloo.ca/~cs341/#Assignments}
\end{itemize}

\definecolor{care}{rgb}{0,0,0}
\def\question#1{\item[\bf #1.]}
\def\part#1{\item[\bf #1)]}
\newcommand{\pc}[1]{\mbox{\textbf{#1}}} % pseudocode


\subsection{Candy Distribution [9 Marks]}

We are distributing $n$ pieces of candy to $n$ children, without sharing. Unlike in lecture, there are no allergies to worry about, but the children do have preferences. The preferences are in the form of an $n \times n$ matrix $P \in \mathbb Z^{n \times n}$ where the $i$th column contains the $i$th child's ranking (in the form of integers $1, \ldots, n$) for each type of candy. Find a matching of children to candy such that every child gets some candy in their first $k$ preferences, for $k$ as small as possible. More precisely, find a bijection $\sigma \colon [n] \to [n]$ from children to candy such that $\max_i P_{\sigma(i), i}$ is minimized. 

Design an algorithm to find an optimal (as described above) matching. Show that if your algorithm outputs a matching using the top $k$ preferences of each child, then it finishes in $O(k n^2)$ time. 

%%%%%%%%%%%% Q1
\subsection{P and NP-C [15 Marks]} 

\begin{enumerate}
    \item Let $\textsc{BIP-AND-VC}=\{\langle G, k\rangle$ be the set of all bipartite graphs $G$ that also have a vertex cover of size $k$.
Show that $\textsc{BIP-AND-VC}$ is solvable in polynomial time.

\item  Let $\textsc{BIP-XOR-VC}=\{\langle G, k\rangle$ be the set of all  graphs $G$ that fall  into exactly one of the cases: $G$ is bipartite; 2) $G$ a vertex cover of size $k$. \}


Show that $\textsc{VertexCover}\leq_P \textsc{BIP-XOR-VC}.$ In fact, finish the proof to show that the problem is NP-Complete.

\end{enumerate}



\subsection{XOXO-puzzle [10 Marks]} 

 An XOXO-puzzle is on an $n\times m$ grid, where each square of the grid may be empty, or occupied by a cross piece, or occupied by a circle piece (see figure for reference). 
Given an initial configuration of circles and crosses on the $n\times m$ grid, the goal of the puzzle is to remove some pieces (can be circle or cross pieces or both), so that the remaining pieces satisfy \emph{both} the constraints defined below: 
\begin{enumerate}
    \item Every row contains at least one piece. 
    \item No column contains pieces of both types, i.e., every column either contains only circle pieces or only cross pieces or neither. 
\end{enumerate}

 Some CS341 students quickly realize that there are initial configurations for which solving this puzzle is impossible, and worse, even \emph{deciding} whether this puzzle is solvable is actually \NP-hard. 
\begin{center}
\includegraphics[scale=0.5]{hw5-puzzle-picture.png}    
\end{center}

Given an initial configuration of circles and crosses show an efficient reduction from 3-{\sf SAT}. Make sure to prove that the puzzle has a solution if and only if 3-SAT has a solution. 

\subsection{Special-SAT [6 Marks]}

Given a CNF formula $\phi$ on $n$ variables, it is a \emph{Special-SAT formula} if it has a \emph{special}  satisfying assignment, namely one in which each clause has at least one satisfied variable and one unsatisfied variable. For example, $
\varphi = (x_1 \lor x_2 \lor x_3) \;\wedge\; (\neg x_1 \lor x_2 \lor x_4)$ is a Special-3SAT formula with special assignment (1, 1, 0, 1),
but $(x  \lor y)\;\wedge\;(x \lor \neg y)$ 
is not, because every satisfying assignment is not special.
The Search-Special-SAT problem asks to find a special assignment for a given formula, if one exists. You have access to a  magical oracle that can solve the decision version of Special-SAT in a single unit of time. 

How do you use this magical oracle in order to solve Search-Special-SAT, by 
making only few queries to the oracle? Clearly state  the number of queries your algorithm makes.

\end{document}