edited by
1,068 views
7 votes
7 votes

A finite sequence of bits is represented as a list with values from the set $\{0,1\}$. For example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $\text{length}(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $\text{head}(l)$ returns the first element of $l$, and $\text{tail}(l)$ returns the list obtained by removing the first element from $l$. The operator $++$ denotes list concatenation.
For example:

  • $\text{head}([0,1,0]) = 0, \text{tail}([0,1,0]) = [1,0]$,
  • $\text{head}([1]) = 1, \text{tail}([1]) =  [ \: ]$, and
  • $[0,1,0]++[1] = [0,1,0,1]$.

Consider the following functions:
$\text{op}$ takes as input two bits and returns a bit.

op(a,b)
if (a = b) return(0)
else return(1)
endif

$\text{mystery}1$ takes as input two lists and returns a list.

mystery1(s,t)
if (length(s) != length(t)) then return(t)
else if (length(s) = 0) then return(s)
else return([op(head(s),head(t))] ++ mystery1(tail(s),tail(t)))
endif
endif

$\text{mystery}2$ takes as input two lists and outputs a list.

mystery2(s,t)
if (length(t) = 0) then return(s)
else return( mystery1(mystery2(s,tail(t)),mystery2(s,tail(t))))
endif

Suppose $s=t=110100100$. What are the first two bits of $\text{mystery2(s,t)}$?

edited by

1 Answer

Best answer
10 votes
10 votes

Here, the $op$ function takes two bits as input and outputs their $\text{XOR} (\oplus).$

Let $x_1$ and $x_2$ be the two input bits in the function $op$.

Then, the output is $x_3$ s.t. $\boxed{x_3 = x_1 \hspace{0.1cm} \oplus \hspace{0.1cm} x_2 }\quad \rightarrow \text{(output of op function)}$

Now, the mystery $1$ function takes two lists $s$ and $t$ as input and outputs another list $u$  (say) such that

$\boxed{u = s \oplus  t} \quad \rightarrow \text{(output of mystery 1 function)}$

and the output of mystery $2$ function is 

$$u =\underset{2 ^{\text{length}(t)} \text{times}}{\underbrace{ s \oplus s \oplus s \oplus s \ldots \oplus s}} $$

  1. Taking $\text{XOR}$ of $s,$ $2^{\text{length}(t) }$ times does not change the $\text{length}(s)$. So, our answer will be $\text{length}(s) .$
  2. In this problem the first two bits of length $s$ are $11$, so taking the $\text{XOR}$ of $1,$ even number of times gives the output $0$. So, our answer is $00$. 
selected by

Related questions