255 views

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]$, . . . .
[ ] denotes the empty list, and $[b]$ is the list consisting of one bit $b$. The function $length(l)$ returns the length (number of bits) in the list $l$. For a nonempty list $l$, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list obtained by removing the first element from $l$. The operator $++$ denotes list concatenation.
For example:

• $head([0,1,0]) = 0, tail([0,1,0]) = [1,0]$,
• $head([1]) = 1, tail([1]) =$ [ ], and
• $[0,1,0]++[1] = [0,1,0,1]$.

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

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

$mystery1$ 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)
endif
endif

$mystery2$ 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
1. Suppose $s=t=110100100$. What are the first two bits of $mystery2(s,t)$?

edited | 255 views
+1
I think its ans should be - 000000000

Here mystery1 returns xor of two binary string if both has same length.
0
wouldn't mystery2 always return 0 if s == t and len(s) >= 1, because it will return mystery1(x,x) which is 00......len(s) times because mystery1 calculates the list xor, for mystery2, x =  mystery2(s,tail(t))

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$.
by Loyal (9.6k points)
selected by
0
+2
They asked only for the first two bits that's why
0

@Kushagra Chatterjee In output of mystery2 function, I think, it should be $2^{length(t)}-1$ because I am getting these many mystery1 calls for particular mystery2(s,t) by taking some sample inputs like s=01,t=101 or s=010,t=101...please check..

0

Written mys inplace of mystery

0

@Kushagra Chatterjee here , string $01$ are of $2^{3}=8$ times but XOR operation is done $2^{3}-1=7$ times. right ?

I am saying it because you have written "Taking XOR of s,  $2^{length(t)}$ times does not change.." in next line. Please correct me if I am wrong.

0

@ankitgupta.1729

yes ur logic correct.

But check last picture of @Kushagra

I think it has small mistake

It calls mystery2(110,110) at first

and it returns (mystery1(10),10) at very first call (Even before calling mystery1() for the first time)

Isnot it??

+1 vote
1