CECS $329,$ Writing As

March $7$th$,2024,$ Dr$.$

Directions

Make sure name is on all pages. Order pages $($front and back$)$ so that solutions are presented in their original numerical order. Please no staples or folding of corners. Using a paper clip is OK is you wish. Show all necessary work and substantiate all claims. Note: plagiarizing the work of another student or using a solution found on the internet will result in a final course grade of $"$F$".$ Note: this writing assignment is worth $0-40$ course points and so only one half the total assignment points earned will be recorded in the corresponding grade item.

Problems

Find an NP$-$complete decision problem $L$ that is used as a simplified model for a practical problem within an applied area of computer science that interests you. The areas are limited to $A\frac{\text{I}}{m}ane$ learning, security, networking$/$distributed$-$computing, computer graphics, software egineering, data mining, and computer architecture. The problem should be presented within a book or technical article written about your area of interest and may not appear in any of this semester's $329$ course artifacts, including lectures, and LO$/$exam problems. Then do each of the following. Note: adequately solving parts c$-$e counts for passing LO$2.$ Students who have already passed LO$2$ via an in$-$class assessment will receive a $25$ course$-$points bonus for doing so$,$ in addition to the points earned for this problem.

$($a$)$ Provide a reference for where you found $L$ and explain how it relates to your applied CS area of interest. $(5$ points and whose completion is necessary to avail the remaining Problem$-1$ points$).$

$($b$)$ List the different parameters that comprise an instance of $L$ and provide an $($non$-$trivial but sufficiently small$)$ example of a positive instance of $L$ along with its solution. $(5$ pts$)$

$($c$)$ For a given instance of $L,$ describe a certificate in relation to this instance. $(5$ pts$)$

$($d$)$ Provide a semi$-$formal verifier algorithm that takes as input i$)$ an instance of $L$ and ii$)$ a certificate for the problem instance as defined in part $c,$ and decides if the certificate is valid for $L.(10$ pts$)$

$($e$)$ Describe the running time of your verifier from part d using appropriate size parameters and explain why it is a polynomial with respect to the size paramters. $(5$ pts$)$

Given $3$SAT instance

$C=\{\begin{array}{ccc}{x}_1,& x_3\frac{,}{b}ar& (x_4)\\ x_1,& x_2\frac{,}{b}ar& (x_3)\\ x_1,& x_3,& x_5\\ \frac{?}{\text{b}\text{a}\text{r}}& (x_1),x_2,& x_3\\ \frac{?}{\text{b}\text{a}\text{r}}& (x_1),x_2\frac{,}{b}ar& (x_4)\\ ?\end{array}$

$(\frac{?}{\text{b}\text{a}\text{r}}(x_1)\frac{,}{b}ar(x_2),x_4),(\frac{?}{\text{b}\text{a}\text{r}}(x_1)\frac{,}{b}ar(x_2)\frac{,}{b}ar(x_5)),(\frac{?}{\text{b}\text{a}\text{r}}(x_1),x_3,x_5),(\frac{?}{\text{b}\text{a}\text{r}}(x_1)\frac{,}{b}ar(x_3),x_4),(x_2,x_4\frac{,}{b}ar(x_5))$

$\{$:$(\frac{?}{\text{b}\text{a}\text{r}}(x_2)\frac{,}{b}ar(x_3),x_5),(\frac{?}{\text{b}\text{a}\text{r}}(x_2),x_3\frac{,}{b}ar(x_4))(x_2,x_3\frac{,}{b}ar(x_4)),(x_1,x_2,x_4),(\frac{?}{\text{b}\text{a}\text{r}}(x_1)\frac{,}{b}ar(x_3)\frac{,}{b}ar(x_4))\}$

$1$

$($a$)$ For the mapping reduction $f$ from $3$SAT to Clique presented in lecture, if $f(C)=(G,k)$ what is the value of $k$ the order of $G,$ and a good upper bound for the size of $G?$ Explain and show work. $(5$ pts$)$

$($b$)$ Provide a set $C$ of vertices of $G$ that corresponds with a maximum clique for $G.$ Please indicate which clause group is associated with each vertex in $C.$ Justify your answer $(10$ pts$)$

$($c$)$ For the mapping reduction $f$ from $3$SAT to DHP$,$ if $f(C)=(G,a,b),$ does $G$ have a directed Hamilton path from $a$ to $b?$ If not, explain why, if yes, then provide the direction $($left or right$)$ that the path takes in each diamond subgraph of $G$ and, for each $($island$)$ clause vertex $c,$ indicate which diamond one should use in order to visit $c.$ Justify your answer. $(10$ pts$)$

$3.$ Provide the instructions of a URM program $P$ that, on input $x>0$ returns ${|}_{{?}_{?}}lo{g}_2{x}_{{?}_{?}}|.$ For each register used by your program, write one or more sentences that describe its role in computing the desired value. Use the online URM simulator to verify that your program works for a variety of inputs $($especially for the first few powers of $2).(25$ pts$).$