The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
72 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], \dots$
$[]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. 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. \: \: a:l$ denotes a new list formed by adding a at the head of list $l$.
For example:
$head([0,1,0]) \: =\: 0, tail([0,1,0]) = [1,0]$,
$head([1]) \: = \: 1, 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
  1. What is the value of $g2(256)$ and $g2(257)$?
in Algorithms by Veteran (100k points) | 72 views

1 Answer

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)

by Loyal (9.6k points)

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
50,092 questions
55,239 answers
190,755 comments
85,992 users