%Do not change
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}}
\newif\iftemplate
%\templatefalse
\templatetrue
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
% Do not modify
%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\begin{textblock*}{30cm}(-1.7cm,-2.3cm)
\noindent {\large CS 381-Fall 2019} \\
\iftemplate
\noindent {\large Name: } \\
\noindent {\large Purdue ID: } \\
\noindent {\large Date: \today}
\fi
\end{textblock*}
\vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 7} \\
\textbf{Due Date: November 26, 2019 at 11:59PM on Gradescope.} \\
\textbf{Instructor: Jeremiah Blocki} \\
\end{center}
\subsection*{Homework Guideline Reminders}
\begin{itemize}
\item Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures.
\item Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed {\em entirely} in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded.
\end{itemize}
\subsection*{Question 1: 2-SAT}
Recall that a 2-SAT Instance $\Phi$ consists of $n$ variables $x_1,\ldots,x_n$ and $m$ clauses $C_1,\ldots,C_m$ where each clause $C_i = \ell_{i_1} \vee \ell_{i_2}$ is the disjunction of two literals. In this problem you will develop a linear time algorithm to solve 2-SAT by reducing the 2-SAT instance $\Phi$ to the Strongly Connected Components problem. Given $\Phi$ we construct directed graph $G_{\Phi}$ defined as follows: \\
\noindent{\bf Nodes:} For each literal $\ell$ we add a node $v_{\ell}$ ($2n$ nodes total) \\
\noindent{\bf Notation: } Given a node $v_{\ell}$ we use $v_{\overline{\ell}}$ to denote the node corresponding to $\overline{\ell}$. For example if $\ell = \overline{x}$ then $v_{\overline{\ell}} = v_x$. \\
\noindent{\bf Edges:} For each clause $C = \ell \vee \ell '$ we add two directed edges $\left(v_{\overline{\ell}}, v_{\ell'}\right)$ and $\left(v_{\overline{\ell'}}, v_{\ell}\right)$.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Suppose that we have a directed path $P = v_{\ell_1},v_{\ell_2},\ldots,v_{\ell_k}$ in $G_{\Phi}$. Explain why $\overline{P} =v_{\overline{\ell}_k},\ldots, ,v_{\overline{\ell}_2},v_{\overline{\ell}_1}$ is a valid directed path in $G_{\Phi}$.
\item Suppose that for some literal $\ell$ the graph $G_{\Phi}$ contains a directed path from node $v_{\ell}$ to $v_{\overline{\ell}}$ as well as a directed path from node $v_{\overline{\ell}}$ to $v_{\ell}$. Show that the 2-SAT instance $\Phi$ is not satisfiable.
\item Suppose that for every literal $\ell$ the nodes $v_{\ell}$ and $v_{\overline{\ell}}$ are in separate strongly connected components in $G_{\Phi}$. Show that the 2-SAT instance $\Phi$ is satisfiable.
\item Describe an O(n+m) time algorithm which solves the 2-SAT problem. If the 2-SAT formula $\Phi$ is not satisfiable then the algorithm should output ``no-solution" otherwise the algorithm should output a satisfying assignment. You should analyze the running time of your algorithm and give a brief (but clear) explanation of why your algorithm is correct.
\end{enumerate}
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 2: Stacked Shelves}
Jane and Charles are both volunteers at the local public library, and they have been tasked with shelving books to their assigned shelf. Jane and Charles are each given $n$ books, and each book $i$ has a size $b_i$. The shelf has a capacity of $C$, which may not be enough to shelve all $n$ books.
\\ \\
Jane decides that if all of the books are the same size, then she can just put them aside in a box. Otherwise, she wants to shelve a subset of the books such that all $C$ capacity is used. Jane would like an algorithm that returns $YES$ if and only if all of the books are the same size OR there exists a subset of books with total size $C$.
\\ \\
Charles is a neat freak and wants all of the books to be the same size in addition to wanting to shelve a subset of the books such that all $C$ capacity is used. Charles would like an algorithm that returns $YES$ if and only if all of the books are the same size AND there exists a subset of books with total size $C$.
\\ \\
After discussing their strategies together, Jane and Charles believe that one of their proposed problems is in $P$ and the other is $NP$-complete, but they're not sure which one is which. Your mission -- you better choose to accept it -- is to figure out which of Jane's or Charles' problems is $NP$-complete. Provide a polynomial time algorithm for the problem in $P$ and prove that the other problem is $NP$-complete.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 3: TA Hiring Problem}
Prepping for a course is tough work! A few months before the class began, Prof. Blocki was making preparations to teach CS381. He planned to cover $n$ interesting algorithm topics like divide and conquer, greedy, DP, max flow, P vs.\ NP, etc. To assist Prof. Blocki, the Purdue CS department has allowed him to choose at most $k$ TAs (due to budget constraint) from a set of $m$ applicants. Each of the $m$ TAs has a skill set containing a set of topics that the TA specializes, denoted as $S_i$ for TA $i$. Prof. Blocki wanted to make sure that for each of the $n$ topics, there are at least two hired TAs specialized in that topic. As a result, he came up with the \textbf{TA Hiring Problem}: For a given number $k < m$, is it possible to hire at most $k$ of the TAs and have at least two TAs specialized in each of the $n$ topics?
\\ \\
After thinking about it for few seconds, Prof. Blocki realized that hiring TAs will be a real pain because the TA Hiring Problem is NP-complete. Help Prof. Blocki prove that the TA Hiring Problem is NP-complete.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\subsection*{Question 4: Nonconformists' Network}
Fakebook is a social network represented by an undirected graph with $n$ nodes and $m$ edges, where each node is a person and each edge represents a friendship. On Fakebook, everybody recently gave their opinion on the question $Q$: ``Is P = NP?". There are only three options to the question: ``Yes", ``No", and ``Maybe". However, nobody on Fakebook actually cares about the question, they just care whether their opinion stands out compared to their friends. In other words, everybody on Fakebook wants to choose an answer to $Q$ that does not match the answers of any of their immediate friends. We say that a graph $G$ is stable to $Q$ if it is possible that everybody in $G$ can answer $Q$ in a manner that nobody's answer matches with any of their immediate friends.
\\ \\
You are given an oracle that tells you whether or not a given graph $G$ is stable. Use the oracle to design an efficient algorithm to find a set of answers for the $n$ people that makes the entire network of Fakebook stable.
\iftemplate
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\else
% omit
\fi
\end{document}