The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
224 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)
else return([op(head(s),head(t))] ++ mystery1(tail(s),tail(t)))
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)$?
asked in Algorithms by Veteran (96.2k points)
edited by | 224 views
+1
I think its ans should be - 000000000

Here mystery1 returns xor of two binary string if both has same length.

1 Answer

+6 votes
Best answer

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$. 
answered by Loyal (9.5k points)
selected by
0
Why isn't the answer 000000000?
+1
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
187,535 comments
71,151 users