Final Exam

$1$: procedure FUN$($n: integer$)$

$2$:

s:$=0$

$3$:

for i:$=1$ to n do

$4$:

for j:$=1$ to $5$n do

$5$:

S:$=8+1$

$6$:

end for

$7$:

end for

$8$:

for k:$=1$ to $|$n$/6]$ do

$9$:

S$=8+1$

$10$:

end for

$11$:

return s

$12$: end procedure

$1.($a$)$ Determine whether or not $($p $->+)^(9->$ r$)$ is logically equivalent to $($PV a $->$ T$.$

$($b$)$ Express the negation of this statement so that all negation symbols immediately precede predi$-$

Vy@$()->3$a$($P$($c$)^-$ R$($ac$))$

$2.$ Show that the following propositions imply that there is a person that likes bowling and darts $($explain each step of your argument$)$:

$$ There is a person that likes playing video games.

$$ If a person likes to nap, then they like to write.

$$ It is not the case that there is a person that likes to write.

$$ If a person does not like to nap, then they like bowling.

$$ If a person likes playing video games, then they like darts.

$3.$ Prove the following: Let n be an integer, then n is even if and only if $5$n $+8$ is even.

$4.($a$)$ Compute a$4$ if an $=4+|645]$ when n $>0$ and ao $=4.$

$3$

$($b$).$ Evaluate

$(-1)*-1.4$n$.$

$5.$ Determine whether or not the following function is a bijection: f: R $->$ R where f$($x$)=3+6.$

$6.$ Give an algorithm $($write the pseudocode$)$ that takes in a list of n integers and returns the location of the first integer that is less than $5$ in the list. If no such integers exists, the algorithm should return $0.$

$7.$ Give a big$-$O estimate on the size of the output s based on the size of the input n for the following algorithm $($be sure to justify all inequalities for full credit$)$:

$8.($a$)$ Convert $522$ to base $6.$

$($b$)$ Convert $($E$4$AD$9)16$ to octal.

$9.$ Solve the congruence $31$x $=3$ mod $59$ using the Euclidean algorithm.

$10.$ Use induction to prove that $2$ divides n $+15$n for all n $>=1.$

$1$