in Algorithms edited by
494 views
1 vote
1 vote

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$. 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. \: \: a:l$ denotes a new list formed by adding a at the head of list $l$.
For example:
$\text{head}([0,1,0]) \: =\: 0, \text{tail}([0,1,0]) = [1,0]$,
$\text{head}([1]) \: = \: 1, \text{tail}([1]) = [ \: ],$ and
$1:[0,1,0] \: = \: [1,0,1,0]$.

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

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

$f1$ takes as input a list and returns another list.

f1(s)
if (s == []) then return([1])
else if (head(s) == 0) then return(1:tail(s))
else if (head(s) == 1) then return(0:f1(tail(s)))
endif

$f2$ takes as input a bit and a list and returns a bit.

f2(b,s)
if (s == [ ]) then return(b)
else if (head(s) == 0) then return(f2(xor(b,1),tail(s)))
else if (head(s) == 1) then return(xor(b,1))
endif

$g1$ takes as input a nonnegative number and returns a list.

g1(n)
if (n == 0) then return([0])
else return f1(g1(n-1))
endif

$g2$ takes as input a nonnegative number and returns a bit.

g2(n)
if (n == 0) then return(0)
else return f2(g2(n-1),g1(n))
endif

What is the value of $g2(256)$ and $g2(257)$?

in Algorithms edited by
494 views

1 Answer

0 votes
0 votes

                     f2 (b, s) = b XOR 0 = b.

Now we start calculating the values returned by the function g1 for different non negative numbers.

g1 (0) = [0]

g1 (1) = f1(g1(0)) = f1([0]) = [1]

g1 (2) = f1( g1(1)) = f1([1]) = [01]

g1 (3) = f1 (g1 (2)) = f1([01]) = [11].

g1 (4) = [001]

g1(5) = [101].

Now if we observe different values for  g1 then we get

g1 (odd number) = Binary representation of the odd number taken as argument.

g1 (even number) = Reverse of the binary representation of the even number taken as argument.

Now we calculate the values returned by the function g2 for different non negative numbers taken as arguments.

g2(0) = 0

g2(1) = f2 (g2(0),g1(1)) = f2(0,1) =1

g2(2) = f2(1,[01]) = 1

g2 (3) = f2(1,[11]) = 0

g2(4) = f2(0,[001]) = 1

g2(5) = f2(1,[101]) = 0

g2(6) = f2 (0,[011]) = 0

g2(7) = f2 (0,[111]) = 1

g2(8) = f2 (1,[0001]) = 1

[ NOTE : To generate the values of g2  I have used the concepts for generating the values of f2 and g1 discussed before.]

By observing different values of g2 we get

g2 ($2^k$) = 1.

Hence g2(256) = g2($2^8$) = 1(Answer)

and g2(257) =f2(g2 (256),f1 (257)) =  f2(1,[100000001]) = 0 (Answer)

Related questions