CMI2020-B: 4

Question

Consider the procedure $\text{MYSTERY}$ described in pseudocode below. The procedure takes two non-negative integers as arguments. For a real number $x$ the notation $[x]$ denotes the largest integer which is not larger than $x$.

$\text{MYSTERY (p,q)}$

1. $\textbf{if}\;p==0$
2.         $\textbf{then return} \;0$
3. $r \leftarrow \llcorner p/2\lrcorner$
4. $s\leftarrow q+q$
5. $t \leftarrow \text{MYSTERY (r,s)}$
6. $\textbf{if}\; p\; is\; even$
7.          $\textbf{then return}\; t$
8.          $\textbf{else return}\; t+q$

1. What does $MYSTERY(100,150)$ return?
2. How many times is the statement on line $8$ executed in a call to $MYSTERY(100,150)$?
3. In general, what does $MYSTERY(m,n)$ return for $m,n\underline> 0?$ Justify your answer with a proof.

Answer 1