In questions $1$ and $2,$ we will create program that calculates the factorial of natural number $n.$ We want $x=$fac$(n)$

to be the postcondition of the program, and $n0$ to be the precondition of this program.

Create a loop invariant $p$ by replacing $n$ by variable $y$ in the postcondition. $($Consider: what is the range of $y?)$

Create the corresponding loop condition $B$ and bound expression $t.$ Show your work.

Create a full proof outline under the total correctness for this program. Don't forget to initialize variable $x$ and $y$

before the loop starts, find reasonable values for them. Use the fact that fac$(n)=$fac$(n-1)**n$ while

creating the loop body.

For each of the following statements, decide whether it is true or false. Justify your answer.

a$.$ A good loop invariant $p$ should be stronger than the expected postcondition of the loop.

b$.$ A good loop invariant $p$ should be true before, after and within each iteration of the loop.

c$.$ There is no algorithm to find a loop invariant, but there are algorithms to find bound expressions.

d$.$ If we know that $),$ then $($if $B$ then $e_1$ else $\{$:$e_{2}fi)|e_1.$

e$.($if $B$ then $T$ else $\{$:$B_{2}fi)|(Bvv{B}_2).$

Finish the following syntax substitution, where $i,j,k$ are all named constants. Optimize your result into a chain

if $-$ else $-$ fi expression.

$(b[b[i]])[\frac{k}{b}[j]]$

Find an optimized precondition $p$ which contains no conditional expressions and create a full proof outline for

the following minimal proof outline. You may assume that $\{p\}b[i]$:$=x$;$b[j]$:$=y\{b[i]b[j]\}p\{p\}b[i]$:$=b[j]$;$b[j]$:$=b[k]\{b[i]>b[k]\}($:$S,$:$)S-=[x$:$=1||x$:$=-1]$;$y$:$=y+x($:$W,\{x=0,y=1,n=2\}$:$)W-=x+1||y$:$=y**2xdo[x$:$=$

$x+1||y$:$=y**2]od\mathrm{.}0i$

$so$ you don't need $to$ worry about the array$-$index$-$out$-of-$bounds error.

$\{p\}b[i]$:$=b[j]$;$b[j]$:$=b[k]\{b[i]>b[k]\}$

Draw $an$ evaluation graph for the configuration $($:$S,$:$)$ where $S-=[x$:$=1||x$:$=-1]$;$y$:$=y+x.$

Draw $an$ evaluation graph for the configuration $($:$W,\{x=0,y=1,n=2\}$:$)$ where $W-=$ while $xdo[x$:$=$

$x+1||y$:$=y**2]od\mathrm{.}0iso$ you don't need

$to$ worry about the array$-$index$-$out$-of-$bounds error.

$\{p\}b[i]$:$=x$;$b[j]$:$=y\{b[i]b[j]\}$

Find $an$ optimized precondition $p$ which contains $no$ conditional expressions and create a full proof outline for

the following minimal proof outline. You may assume that $0i$

$so$ you don't need $to$ worry about the array$-$index$-$out$-of-$bounds error.

$\{p\}b[i]$:$=b[j]$;$b[j]$:$=b[k]\{b[i]>b[k]\}$

Draw $an$ evaluation graph for the configuration $($:$S,$:$)$ where $S-=[x$:$=1||x$:$=-1]$;$y$:$=y+x.$

Draw $an$ evaluation graph for the configuration $($:$W,\{x=0,y=1,n=2\}$:$)$ where $W-=$ while $xdo[x$:$=$

$x+1||y$:$=y**2]od.$