\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.7 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\usepackage{amsmath,amssymb,enumerate,epsfig}
\usepackage{algorithm}
\usepackage{ifthen}
\usepackage[noend]{algorithmic}
\usepackage{wasysym}
\usepackage{hyperref}
\usepackage[dvipsnames]{xcolor}
%%%% Some of this is not used for the assignment, it was just in the .tex template I used.
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{proposition}{Proposition}
\newtheorem{prob}{Problem}
\newtheorem{corollary}{Corollary}
\newtheorem{question}{Question}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{remarka}{Remark}
\newtheorem{observation}{Observation}
\def\P{\mathop{\rm P}\nolimits}
\def\NP{\mathop{\rm NP}\nolimits}
\def\DTIME{\mathop{\rm DTIME}\nolimits}
\def\BPTIME{\mathop{\rm BPTIME}\nolimits}
\def\ZPTIME{\mathop{\rm ZPTIME}\nolimits}
\def\polylog{\mathop{\rm polylog}\nolimits}
\newenvironment{remark}{\begin{remarka}\rm}{\end{remarka}}
\newenvironment{proof}{{\bf Proof.}}{\hfill\rule{2mm}{2mm}}
\newenvironment{pproof}[1]{\noindent{\textbf{Proof of #1.}}}{\hfill\rule{2mm}{2mm}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calP}{{\cal P}}
\newcommand{\opt}{\mbox{\sc opt}}
\newcommand{\OPT}{\mbox{\sc OPT}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[5]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CMPUT 304: Algorithms II
\hfill Fall 2021} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Assignment #1 (#2): #3 \hfill} }
\vspace{2mm}}
}
\end{center}
\markboth{Assignment #1: #3}{Assignment #1: #3}
\vspace*{4mm}
}
\begin{document}
% Content that appears in the header.
\lecture{5}{Due Dec 9 by 11:55pm}{Submit via eClass}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
You must adhere to the consultation collaboration policy mentioned in the course outline. Remember to list anyone you discussed the
assignment questions with and remember what constitutes an acceptable level of discussion.
You need to solve 5 out of the 6 problems. Each is worth 8 marks, so the total score is 40. If you solve all 6, the TAs get to decide which ones they want to mark.
{\bf Your solutions must be written neatly}. Messy solutions that are difficult to read may lose marks or may even receive a 0 if it takes the TA too much effort to even understand what you have written. If you are not typesetting your solution in LaTeX or even something like Word (remember to export as a .pdf), then take your time writing things neatly!
Short and to-the-point answers are best. Rambling answers may not receive full credit.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 1 – Constructing Solutions if {\bf P} = {\bf NP} [8 marks]}
Recall that in the {\bf Vertex Cover} problem, you are given a graph $G = (V,E)$ and an integer $k$. The goal is to determine if there is some $C \subseteq V$ with $|C| \leq k$ such that each $\{u,v\} \in E$ has at least one of $u$ or $v$ in $C$.
If {\bf P} = {\bf NP}, then this decision problem can be solved in polynomial time. But merely knowing the answer is “yes” for an instance does not give you the actual vertex cover!
Show that if {\bf P} = {\bf NP} then there is an algorithm that does the following. Given a {\bf yes} instance $G,k$ of {\bf Vertex Cover}, the algorithm computes a feasible solution in polynomial time: that is it finds a vertex cover $C \subseteq V$ with $|C| \leq k$ in polynomial time. Argue why your algorithm is correct (assuming {\bf P} = {\bf NP}) and explain why it runs in polynomial time.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 2 – {\bf co-NP-completeness} [8 marks]}
We say a language $L \subseteq \{0,1\}^*$ is {\bf co-NP-complete} if $L \in \text{\bf co-NP}$ and $\forall L’ \in \text{\bf co-NP}$, $L’ \leq_P L$.
Let {\bf 3DNF-Tautology} be the following problem. Read the description carefully!
We are given $n$ variables $x_1, \ldots, x_n$ and $m$ clauses. Each clause is of the form $\ell_1 \wedge \ell_2 \wedge \ell_3$ where each $\ell_i$ is a literal (a variable or its negation) and these three literals depend on different variables.
We say a clause is satisfied by a truth assignment if {\bf all} of its literals are true under this assignment. The goal of {\bf 3DNF-Tautology} is to determine if all variable assignments will satisfy {\bf at least} one clause (a {\bf yes} instance) or if there exists an assignment that fails to satisfy every clause (a {\bf no} instance).
Show that {\bf 3DNF-Tautology} is {\bf co-NP-complete}.
{\bf Strong Hint}: Use the fact that $L \in {\bf NP}$ if and only if $\overline{L} \in \text{\bf co-NP}$. So starting from any $L’ \in \text{\bf co-NP}$, consider using reductions we already know from $\text{\bf NP-completeness}$ in $\overline{L’}$. Show how {\bf 3CNF-SAT} and {\bf 3DNF-Tautology} are related (tip: DeMorgan’s rule).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 3 – Two Quick Approximation Algorithms [8 marks]}
{\bf Part 1} [4 marks]\\
Let $G = (V,E)$ be a graph. Give an algorithm that finds a colouring $\sigma : V \rightarrow \{1,2,3\}$ of the nodes such that the number of edges $\{u,v\} \in E$ with $\sigma(u) \neq \sigma(v)$ is at least $\frac{2}{3} \cdot |E|$.
Your algorithm is allowed to be randomized, so long as the expected number of edges whose endpoints are coloured differently is at least $\frac{2}{3} \cdot |E|$.
{\bf Part 2} [4 marks]\\
In an instance of {\bf NAE-3SAT}, we are given an instance of {\bf 3CNF-SAT} except a clause is said to be satisfied by a truth assignment if there is at least one \texttt{true} literal and at least one \texttt{false} literal in the clause. For example, consider a clause $x \vee y \vee \overline z$. The assignment $x = T, y = T, z = T$ is satisfying since there are both true and false literals. However, the assignment $x = T, y = Y, z = F$ is not satisfying since there are no \texttt{false} literals. Recall this problem was discussed during the seminar on Nov 17.
Give an algorithm that satisfies at least $3m/4$ clauses where $m$ is the total number of clauses. Again, the algorithm is allowed to be randomized so long as the expected number of clauses that are satisfied is at least $3m/4$.
{\bf Bonus} [1 mark]\\
Give a deterministic (i.e. not randomized), polynomial time that is guaranteed to find a truth assignment satisfying at least $3m/4$ clauses of a {\bf NAE-3SAT} instance.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 4 – TSP Path [8 marks]}
Let $T = (V,E)$ be a tree and $s,t \in V$ be two distinct vertices. Show that there is an $s-t$ walk in the tree (a path, but repeating vertices is allowed) such that each vertex in $V$ is visited at least once by the walk and each edge in $E$ is traversed by this walk at most twice.
Use this to give a 2-approximation for the following problem: given a points $V$ with metric distances $d(u,v)$ between points $u,v \in V$ (recall the metric properties from the lecture 18) and two distinct nodes $s,t$, find a cheapest TSP Path solution.
Here, a TSP path solution is an ordering $v_1, v_2, \ldots, v_n$ of $V$ (so $n = |V|$) with $v_1 = s$ and $v_n = t$. That is, the ordering describes an $s-t$ path that visits all points. The cost of the ordering is:
\[ \sum_{i=1}^{n-1} d(v_i, v_{i+1}). \]
Note, the cost {\bf does not} include the cost of the step from $v_n$ to $v_1$. Informally, find the cheapest path from $s$ to $t$ that visits all points.
{\bf Hint}: Adapt the steps from the 2-approximation for metric TSP from the lectures. Use the fact about trees from the first part to help out.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 5 – Maximum (Non-Bipartite) Matching [8 marks]}
Problem 35-4 in the textbook, parts (b) through (f) (you can think about part (a) if you want, but you do not need to submit it).
Ultimately, you just have to give an $O(|E|)$ algorithm for computing a matching $M$ with size at least half that of a maximum matching. If you choose to do this differently than following parts (b) through (f), go ahead.
{\bf Notation}: Part (d) talks about a subgraph induced by a set of nodes. This means the following: let $G = (V,E)$ be a graph. For a set $S \subseteq V$, the subgraph of $G$ induced by $S$ is the graph:
\[ (S, F) \text{ where } F = \{\{u,v\} \in E : u,v \in S\}. \]
That is, the subgraph of $G$ obtained by deleting all nodes in $V-S$ and edges that touch at least one of the deleted nodes, but keeping all edges having both endpoints in $S$.
{\bf Note}: One can actually find a maximum matching in any graph in polynomial time, but it takes a lot more effort than the case with bipartite graphs (i.e. it does not just reduce to flow).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section*{Problem 6 – Parallel Machine Scheduling [8 marks]}
Problem 35-5 in the textbook. For part (c), don’t worry about finding a solution with optimal running time. Just make sure your algorithm runs in polynomial time. But it is a good exercise to think about how fast you could implement it.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\end{document}