\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}
