\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,epsfig,graphics}
\setlength{\textwidth}{7in}
\setlength{\topmargin}{-0.575in}
\setlength{\textheight}{9.25in}
\setlength{\oddsidemargin}{-.25in}
\setlength{\evensidemargin}{-.25in}
\reversemarginpar
\setlength{\marginparsep}{-15mm}
\newcommand{\rmv}[1]{}
\newcommand{\bemph}[1]{{\bfseries\itshape#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\imply}{\to}
\newcommand{\bic}{\leftrightarrow}
% Here the user must define certain strings for this homework assignment
%
\def\CourseCode{COMP 6902} % e.g. B38
\def\AssignmentNo{3} % e.g. 1
\def\DateHandedOut{Spring, 2018} % e.g. September 18, 2002
\def\DateDue{July 11, 2018} % e.g. October 1, 2002
\def\TimeDue{11:55pm} % e.g. 11 am
\begin{document}
\noindent
\rmv{Computer Science }
\CourseCode \hfill \DateHandedOut\\
\begin{center}
Homework Assignment \#\AssignmentNo\\
Due: \DateDue, by \TimeDue\\
\medskip
%%%%%% M A K E S U R E T O W R I T E Y O U R N A M E H E R E!!! %%%%%%%%%%%%%%%
\textbf{YOUR NAME HERE} \\
\end{center}
\hrule\smallskip
\begin{enumerate}
\item \textbf{Random SAT} \marginpar{[25]}\\
Recall that in the Random SAT framework formulas are generated as follows. Given the number of variables $n$, a number of clauses $m$, and a number of literals per clause $k$, repeatedly select $k$ out of $n$ literals uniformly at random, and for each selected literal, choose whether it is negated or not with probability 1/2. Repeat this process until there are $m$ distinct clauses (provided $m$ is small enough).
For each of the following subquestions, give both the number for the numeric part of the subquestion, and a formula for the general part.
\begin{enumerate}
\item Suppose there are $n=5$ variables $x_1, x_2, x_3, x_4, x_5$, and you select one clause with $k=5$ literals in it. How many assignments to these variables would satisfy this clause? Now give a formula for a number of assignments satisfying an arbitrary clause with $n=k$ literals.
{\em Solution:
}
\item Now suppose that $n=8$, $k=5$. How many assignments to all $n=8$ variables satisfy one clause with $k=5$ literals? Give a formula for a number of assignments satisfying an arbitrary clause with $n>k$ literals.
{\em Solution:
}
\item Now suppose that $n=8$, $k=5$ and $m=3$. What is the average (that is, expected) number of assignments satisfying a randomly generated formula with these parameters? Give a formula for arbitrary $n, k, m$, where $n>k$ and $m \leq n$ for some constant $c \geq 0$
{\em Solution:
}
\item Now, consider the following randomized algorithm: on a given formula $\phi$ generated as above with parameters $n,k,m$, pick a random assignment and check if it satisfies $\phi$. If so, accept, otherwise fail. What is the probability that this algorithm will succeed, on average, for a formula $\phi$ generated with $n=8, k=5$ and $m=3$? Give a bound on $m$ such that the probability of this algorithm succeeding on formulas generated with parameters $n, k, m$ is at least 1/2.
{\em Solution:
}
\item How large should $m$ be for $n=8, k=5$ to guarantee that the resulting formula is always unsatisfiable? Give a general formula for $m$ as a function of arbitrary $n$ and $k$.
{\em Solution:
}
\end{enumerate}
\item \textbf{Search-to-decision reduction} \marginpar{[25]}\\
The optimization search problem MinTSP is defined as follows.
Given a complete undirected graph $G$ and a cost function $c\colon E \to \mathbb{R}_{\geq 0}$ on its edges (in binary), find a tour (that is, a Hamiltonian cycle in $G$) such that its cost (sum of the costs of all edges in the cycle) is minimal.
\begin{enumerate}
\item Describe how to find the \emph{cost} of an optimal tour in $G$ with cost function $c$ by using as a black box the decision problem
TSP=$\{\langle G, c,B\rangle \mid \exists$ a tour in $G$ of cost at most $B \}$.
Your program should run in time polynomial in the length of the input, counting each call to $TSP$ as one unit of time.
{\em Solution:
}
\item Now describe how to find an optimal tour, again by using TSP as a black box. Use your answer from the previous subquestion.
{\em Solution:
}
\end{enumerate}
\end{enumerate}
\end{document}
\end{enumerate}
\end{enumerate}
\end{document}