Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Consider a set of functions:

  • head(l) returns first bit from list l, e.g.

    head([0,1,0]) = 0, 
    head([1]) = 1
    
  • tail(l) returns a list by removing first element from l, e.g.

    tail([0,1,0]) = [1,0],
    tail([1]) = []
    
  • a:l appends bit a to beginning of list l, e.g.

    1:[0,1,0] = [1,0,1,0].
    
  • 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
    

Can anyone explain what the function g2() returns?

I am able to find out g1() returns a list in binary for example

g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]
share|improve this question
1  
Welcome! I am not sure this question suits this site; you are asking to figure out what a program computes without offering much of your own thought. What does g1 compute in general. –  Raphael Nov 27 '12 at 11:46
    
btw, what programming language is this? At first it looked like Python, but the endif statements and missing colons after the if statements clearly indicate it's not. –  Daniel Eberts Nov 27 '12 at 12:57
    
You are wrong : g1(n) = [ n mod 2 ] –  Anton Nov 27 '12 at 13:50
1  
@DanielEberts this could be valid LUA code. –  Jan Dvorak Nov 27 '12 at 14:11

1 Answer 1

Hints:

  • g1(0) = [0] so you can see that f1 for [0] returns [1] and for [1] returns [0]. From here g1 must be clear.

  • f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)

  • after you know that g2(0) = 0 and the above hints it is easier to calculate g2

I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.

share|improve this answer
    
Hi All, Thanks for your inputs. I am able to find what g2() returns. g2(n)= 0 if n is even and 1 if n is odd. –  akshay Nov 28 '12 at 10:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.