Re: [algogeeks] Re: binary nos

2010-06-11 Thread Mayur 
Oh! Forgot to mention that the count of the leaves of the tree, gives the
number of possible sequences (as required to be determined by the question)

On Fri, Jun 11, 2010 at 10:02 PM, Mayur  wrote:

> A more theoretical answer to the question can be the following:
>
> Let's try to construct a tree for all such possible sequences.
> Level 0  => 0  or 1
> Level 1 =>   01  0
> Level 2 =>0   1 0 01
> Level 3 =>  0  1   0  0  1 0  10
> 
>
> Simple observation will tell you that for every 0 in a position, the next
> position can have either 0 or 1, but for a 1 in the position, the next bit
> *has *to be a 0.  -- (1)
>
> Let us call the function N0(p) to be the number of 0s at level (position) p
> in the sequence; N1(p) to be the number of 1s at level p. The total number
> of nodes at level p is then N(p) = N0(p) + N1(p).
>
> It is also clear from statement (1) that
>  N0(p) = N0(p-1) + N1(p-1)--- (2)
>  and
> N1(p) = N0(p-1)-- (3)
>
> i.e. the number of 0s in the next level equal to the number of 0s in the
> previous level plus the number of 1s in the previous level,
> whereas the number of 1s is equal to the number of 0s in the previous
> level.
>
>
> Thus, combining (2) and (3), we have... N(p) = N0(p-1) + N1(p-1) + N0(p-1)
> --- (4)
>
> Now, N0(p-1) + N1(p-1) is really N(p-1) - i.e. the total number of possible
> sequences of length p.
>
> Also, N0(p-1) = N0(p-2)  + N1(p-2)  = N(p-2)  from (2)
>
> Therefore, (4) reduces to
> N(p) = N(p-1) + N(p-2)
>
> The above, you would recognize as the generative recursive form of the
> sequence of fibonacci numbers.
>
> thanks,
> mayur
>
>
>
> On Fri, Jun 11, 2010 at 2:05 PM, Debajyoti Sarma <
> sarma.debajy...@gmail.com> wrote:
>
>> clarification to all
>>
>> n=1
>> 0,1   no of sequence =2
>>
>> n=2
>> 00,01,10   no of sequence =3
>>
>> n=3
>> 000,100,010,001,101 no of sequence =5
>>
>> n=4
>> ,1000,0100,0010,0001,1010,0101,1001 no of sequence
>> =8
>>
>> n=5
>> 0,1,01000,00100,00010,1,10100,10010,10001,01010,01001,00101,10101
>>  no of sequence =13
>>
>> so its coming in fibo no.
>>
>> no of sequence =fibo(n+2)if you exclude 0 from fibo no
>>
>> no of sequence =fibo(n+3)if you include 0 in fibo no
>>
>>
>>
>> On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma <
>> sarma.debajy...@gmail.com> wrote:
>>
>>> @Rohit Saraf
>>>
>>> i understood the question.
>>> Superb solution by u.
>>>
>>>
>>> On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf <
>>> rohit.kumar.sa...@gmail.com> wrote:
>>>
 write an efficient algo to compute no. of sequences of n binary digits
 that do not contain 2 1's in a row. eg 111 is invalid whereas
 1001001 is valid.

 HERE the number of sequences comes to be a fibonacci number , precisely
 fib(n+2).
 So this prob is equivalent to finding fibonacci numbers

 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14


 On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh <
 singh.sund...@gmail.com> wrote:

> @rohit: fibonacci sequence may be the answer to the prob, but I am
> curious why? I haven't come across any such fib sequence property...
>
> On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf <
> rohit.kumar.sa...@gmail.com> wrote:
>
>> @junta : are fibonacci sequence is the answer of the prob, it is not
>> used :D
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf <
>> rohit.kumar.sa...@gmail.com> wrote:
>>
>>> @debajyoti: read the prob before posting
>>>
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>>
>>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>>> sarma.debajy...@gmail.com> wrote:
>>>
 First 20 fibo no as follows with binary form
   0 = 0
   1 = 1
   1 = 1
   2 = 10
   3 = 11
   5 = 101
   8 = 1000
  13 = 1101
  21 = 10101
  34 = 100010
  55 = 110111
  89 = 1011001
 144 = 1001
 233 = 11101001
 377 = 10001
 610 = 1001100010
 987 = 011011
 1597 = 1100001
 2584 = 1

Re: [algogeeks] Re: binary nos

2010-06-11 Thread Mayur 
A more theoretical answer to the question can be the following:

Let's try to construct a tree for all such possible sequences.
Level 0  => 0  or 1
Level 1 =>   01  0
Level 2 =>0   1 0 01
Level 3 =>  0  1   0  0  1 0  10


Simple observation will tell you that for every 0 in a position, the next
position can have either 0 or 1, but for a 1 in the position, the next bit *has
*to be a 0.  -- (1)

Let us call the function N0(p) to be the number of 0s at level (position) p
in the sequence; N1(p) to be the number of 1s at level p. The total number
of nodes at level p is then N(p) = N0(p) + N1(p).

It is also clear from statement (1) that
 N0(p) = N0(p-1) + N1(p-1)--- (2)
 and
N1(p) = N0(p-1)-- (3)

i.e. the number of 0s in the next level equal to the number of 0s in the
previous level plus the number of 1s in the previous level,
whereas the number of 1s is equal to the number of 0s in the previous level.


Thus, combining (2) and (3), we have... N(p) = N0(p-1) + N1(p-1) + N0(p-1)
--- (4)

Now, N0(p-1) + N1(p-1) is really N(p-1) - i.e. the total number of possible
sequences of length p.

Also, N0(p-1) = N0(p-2)  + N1(p-2)  = N(p-2)  from (2)

Therefore, (4) reduces to
N(p) = N(p-1) + N(p-2)

The above, you would recognize as the generative recursive form of the
sequence of fibonacci numbers.

thanks,
mayur


On Fri, Jun 11, 2010 at 2:05 PM, Debajyoti Sarma
wrote:

> clarification to all
>
> n=1
> 0,1   no of sequence =2
>
> n=2
> 00,01,10   no of sequence =3
>
> n=3
> 000,100,010,001,101 no of sequence =5
>
> n=4
> ,1000,0100,0010,0001,1010,0101,1001 no of sequence
> =8
>
> n=5
> 0,1,01000,00100,00010,1,10100,10010,10001,01010,01001,00101,10101
>  no of sequence =13
>
> so its coming in fibo no.
>
> no of sequence =fibo(n+2)if you exclude 0 from fibo no
>
> no of sequence =fibo(n+3)if you include 0 in fibo no
>
>
>
> On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma <
> sarma.debajy...@gmail.com> wrote:
>
>> @Rohit Saraf
>>
>> i understood the question.
>> Superb solution by u.
>>
>>
>> On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf > > wrote:
>>
>>> write an efficient algo to compute no. of sequences of n binary digits
>>> that do not contain 2 1's in a row. eg 111 is invalid whereas
>>> 1001001 is valid.
>>>
>>> HERE the number of sequences comes to be a fibonacci number , precisely
>>> fib(n+2).
>>> So this prob is equivalent to finding fibonacci numbers
>>>
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>>
>>> On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh >> > wrote:
>>>
 @rohit: fibonacci sequence may be the answer to the prob, but I am
 curious why? I haven't come across any such fib sequence property...

 On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf <
 rohit.kumar.sa...@gmail.com> wrote:

> @junta : are fibonacci sequence is the answer of the prob, it is not
> used :D
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf <
> rohit.kumar.sa...@gmail.com> wrote:
>
>> @debajyoti: read the prob before posting
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>> sarma.debajy...@gmail.com> wrote:
>>
>>> First 20 fibo no as follows with binary form
>>>   0 = 0
>>>   1 = 1
>>>   1 = 1
>>>   2 = 10
>>>   3 = 11
>>>   5 = 101
>>>   8 = 1000
>>>  13 = 1101
>>>  21 = 10101
>>>  34 = 100010
>>>  55 = 110111
>>>  89 = 1011001
>>> 144 = 1001
>>> 233 = 11101001
>>> 377 = 10001
>>> 610 = 1001100010
>>> 987 = 011011
>>> 1597 = 1100001
>>> 2584 = 10111000
>>> 4181 = 101010101
>>>
>>> Now please explain how fibo no is coming under consideration.Both
>>> kind of no is mixed here.
>>>
>>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf <
>>> rohit.kumar.sa...@gmail.com> wrote:
>>>
 Fib comes because she wants the number of such sequences

 --
 --
 Rohit Saraf
 Second Year Undergraduate,
>>

Re: [algogeeks] Re: binary nos

2010-06-11 Thread Debajyoti Sarma 
clarification to all

n=1
0,1   no of sequence =2

n=2
00,01,10   no of sequence =3

n=3
000,100,010,001,101 no of sequence =5

n=4
,1000,0100,0010,0001,1010,0101,1001 no of sequence
=8

n=5
0,1,01000,00100,00010,1,10100,10010,10001,01010,01001,00101,10101
 no of sequence =13

so its coming in fibo no.

no of sequence =fibo(n+2)if you exclude 0 from fibo no

no of sequence =fibo(n+3)if you include 0 in fibo no



On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma
wrote:

> @Rohit Saraf
>
> i understood the question.
> Superb solution by u.
>
>
> On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf 
> wrote:
>
>> write an efficient algo to compute no. of sequences of n binary digits
>> that do not contain 2 1's in a row. eg 111 is invalid whereas
>> 1001001 is valid.
>>
>> HERE the number of sequences comes to be a fibonacci number , precisely
>> fib(n+2).
>> So this prob is equivalent to finding fibonacci numbers
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh 
>> wrote:
>>
>>> @rohit: fibonacci sequence may be the answer to the prob, but I am
>>> curious why? I haven't come across any such fib sequence property...
>>>
>>> On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf >> > wrote:
>>>
 @junta : are fibonacci sequence is the answer of the prob, it is not
 used :D

 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14


 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf <
 rohit.kumar.sa...@gmail.com> wrote:

> @debajyoti: read the prob before posting
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
> sarma.debajy...@gmail.com> wrote:
>
>> First 20 fibo no as follows with binary form
>>   0 = 0
>>   1 = 1
>>   1 = 1
>>   2 = 10
>>   3 = 11
>>   5 = 101
>>   8 = 1000
>>  13 = 1101
>>  21 = 10101
>>  34 = 100010
>>  55 = 110111
>>  89 = 1011001
>> 144 = 1001
>> 233 = 11101001
>> 377 = 10001
>> 610 = 1001100010
>> 987 = 011011
>> 1597 = 1100001
>> 2584 = 10111000
>> 4181 = 101010101
>>
>> Now please explain how fibo no is coming under consideration.Both kind
>> of no is mixed here.
>>
>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf <
>> rohit.kumar.sa...@gmail.com> wrote:
>>
>>> Fib comes because she wants the number of such sequences
>>>
>>> --
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>> --
>>>
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this grou

Re: [algogeeks] Re: binary nos

2010-06-11 Thread Debajyoti Sarma 
@Rohit Saraf

i understood the question.
Superb solution by u.

On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf wrote:

> write an efficient algo to compute no. of sequences of n binary digits
> that do not contain 2 1's in a row. eg 111 is invalid whereas
> 1001001 is valid.
>
> HERE the number of sequences comes to be a fibonacci number , precisely
> fib(n+2).
> So this prob is equivalent to finding fibonacci numbers
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh 
> wrote:
>
>> @rohit: fibonacci sequence may be the answer to the prob, but I am curious
>> why? I haven't come across any such fib sequence property...
>>
>> On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf 
>> wrote:
>>
>>> @junta : are fibonacci sequence is the answer of the prob, it is not used
>>> :D
>>>
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>>
>>> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf >> > wrote:
>>>
 @debajyoti: read the prob before posting

 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14


 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
 sarma.debajy...@gmail.com> wrote:

> First 20 fibo no as follows with binary form
>   0 = 0
>   1 = 1
>   1 = 1
>   2 = 10
>   3 = 11
>   5 = 101
>   8 = 1000
>  13 = 1101
>  21 = 10101
>  34 = 100010
>  55 = 110111
>  89 = 1011001
> 144 = 1001
> 233 = 11101001
> 377 = 10001
> 610 = 1001100010
> 987 = 011011
> 1597 = 1100001
> 2584 = 10111000
> 4181 = 101010101
>
> Now please explain how fibo no is coming under consideration.Both kind
> of no is mixed here.
>
> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf <
> rohit.kumar.sa...@gmail.com> wrote:
>
>> Fib comes because she wants the number of such sequences
>>
>> --
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>> --
>>
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>


>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algo

Re: [algogeeks] Re: binary nos

2010-06-10 Thread Rohit Saraf 
write an efficient algo to compute no. of sequences of n binary digits
that do not contain 2 1's in a row. eg 111 is invalid whereas
1001001 is valid.

HERE the number of sequences comes to be a fibonacci number , precisely
fib(n+2).
So this prob is equivalent to finding fibonacci numbers

--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14


On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh wrote:

> @rohit: fibonacci sequence may be the answer to the prob, but I am curious
> why? I haven't come across any such fib sequence property...
>
> On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf 
> wrote:
>
>> @junta : are fibonacci sequence is the answer of the prob, it is not used
>> :D
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf 
>> wrote:
>>
>>> @debajyoti: read the prob before posting
>>>
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>>
>>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>>> sarma.debajy...@gmail.com> wrote:
>>>
 First 20 fibo no as follows with binary form
   0 = 0
   1 = 1
   1 = 1
   2 = 10
   3 = 11
   5 = 101
   8 = 1000
  13 = 1101
  21 = 10101
  34 = 100010
  55 = 110111
  89 = 1011001
 144 = 1001
 233 = 11101001
 377 = 10001
 610 = 1001100010
 987 = 011011
 1597 = 1100001
 2584 = 10111000
 4181 = 101010101

 Now please explain how fibo no is coming under consideration.Both kind
 of no is mixed here.

 On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf <
 rohit.kumar.sa...@gmail.com> wrote:

> Fib comes because she wants the number of such sequences
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
> --
>
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-10 Thread Sundeep Singh 
@rohit: fibonacci sequence may be the answer to the prob, but I am curious
why? I haven't come across any such fib sequence property...

On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf wrote:

> @junta : are fibonacci sequence is the answer of the prob, it is not used
> :D
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf 
> wrote:
>
>> @debajyoti: read the prob before posting
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>> sarma.debajy...@gmail.com> wrote:
>>
>>> First 20 fibo no as follows with binary form
>>>   0 = 0
>>>   1 = 1
>>>   1 = 1
>>>   2 = 10
>>>   3 = 11
>>>   5 = 101
>>>   8 = 1000
>>>  13 = 1101
>>>  21 = 10101
>>>  34 = 100010
>>>  55 = 110111
>>>  89 = 1011001
>>> 144 = 1001
>>> 233 = 11101001
>>> 377 = 10001
>>> 610 = 1001100010
>>> 987 = 011011
>>> 1597 = 1100001
>>> 2584 = 10111000
>>> 4181 = 101010101
>>>
>>> Now please explain how fibo no is coming under consideration.Both kind of
>>> no is mixed here.
>>>
>>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf >> > wrote:
>>>
 Fib comes because she wants the number of such sequences

 --
 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14

 --

 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-10 Thread jaladhi dave 
@Rohit:
Junta is looking forward for explanation about how one resorted  to
Fibonacci for such solution ? Or was it some 'gyaan' like sun rise in east
direction.

Would be real glad if we can know methods to find such fits.



On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf wrote:

> @junta : are fibonacci sequence is the answer of the prob, it is not used
> :D
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf 
> wrote:
>
>> @debajyoti: read the prob before posting
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma <
>> sarma.debajy...@gmail.com> wrote:
>>
>>> First 20 fibo no as follows with binary form
>>>   0 = 0
>>>   1 = 1
>>>   1 = 1
>>>   2 = 10
>>>   3 = 11
>>>   5 = 101
>>>   8 = 1000
>>>  13 = 1101
>>>  21 = 10101
>>>  34 = 100010
>>>  55 = 110111
>>>  89 = 1011001
>>> 144 = 1001
>>> 233 = 11101001
>>> 377 = 10001
>>> 610 = 1001100010
>>> 987 = 011011
>>> 1597 = 1100001
>>> 2584 = 10111000
>>> 4181 = 101010101
>>>
>>> Now please explain how fibo no is coming under consideration.Both kind of
>>> no is mixed here.
>>>
>>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf >> > wrote:
>>>
 Fib comes because she wants the number of such sequences

 --
 --
 Rohit Saraf
 Second Year Undergraduate,
 Dept. of Computer Science and Engineering
 IIT Bombay
 http://www.cse.iitb.ac.in/~rohitfeb14

 --

 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-09 Thread Rohit Saraf 
@junta : are fibonacci sequence is the answer of the prob, it is not used :D
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14


On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf wrote:

> @debajyoti: read the prob before posting
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
> On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma  > wrote:
>
>> First 20 fibo no as follows with binary form
>>   0 = 0
>>   1 = 1
>>   1 = 1
>>   2 = 10
>>   3 = 11
>>   5 = 101
>>   8 = 1000
>>  13 = 1101
>>  21 = 10101
>>  34 = 100010
>>  55 = 110111
>>  89 = 1011001
>> 144 = 1001
>> 233 = 11101001
>> 377 = 10001
>> 610 = 1001100010
>> 987 = 011011
>> 1597 = 1100001
>> 2584 = 10111000
>> 4181 = 101010101
>>
>> Now please explain how fibo no is coming under consideration.Both kind of
>> no is mixed here.
>>
>> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf 
>> wrote:
>>
>>> Fib comes because she wants the number of such sequences
>>>
>>> --
>>> --
>>> Rohit Saraf
>>> Second Year Undergraduate,
>>> Dept. of Computer Science and Engineering
>>> IIT Bombay
>>> http://www.cse.iitb.ac.in/~rohitfeb14
>>>
>>> --
>>>
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-09 Thread Rohit Saraf 
@debajyoti: read the prob before posting
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14


On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma
wrote:

> First 20 fibo no as follows with binary form
>   0 = 0
>   1 = 1
>   1 = 1
>   2 = 10
>   3 = 11
>   5 = 101
>   8 = 1000
>  13 = 1101
>  21 = 10101
>  34 = 100010
>  55 = 110111
>  89 = 1011001
> 144 = 1001
> 233 = 11101001
> 377 = 10001
> 610 = 1001100010
> 987 = 011011
> 1597 = 1100001
> 2584 = 10111000
> 4181 = 101010101
>
> Now please explain how fibo no is coming under consideration.Both kind of
> no is mixed here.
>
> On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf 
> wrote:
>
>> Fib comes because she wants the number of such sequences
>>
>> --
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>> --
>>
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-09 Thread Sundeep Singh 
Whats the logic behind using Fibonacci in determining the number of such
sequences?

-Sundeep.


On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf wrote:

> Fib comes because she wants the number of such sequences
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-09 Thread Debajyoti Sarma 
First 20 fibo no as follows with binary form
  0 = 0
  1 = 1
  1 = 1
  2 = 10
  3 = 11
  5 = 101
  8 = 1000
 13 = 1101
 21 = 10101
 34 = 100010
 55 = 110111
 89 = 1011001
144 = 1001
233 = 11101001
377 = 10001
610 = 1001100010
987 = 011011
1597 = 1100001
2584 = 10111000
4181 = 101010101

Now please explain how fibo no is coming under consideration.Both kind of no
is mixed here.

On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf wrote:

> Fib comes because she wants the number of such sequences
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-09 Thread jaladhi dave 
hmmm ... Atleast I was of the opinion that such nos. were required and hence
was thinking fib is not the thing. Thanks for clarifying.

On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf wrote:

> Fib comes because she wants the number of such sequences
>
> --
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-08 Thread Rohit Saraf 
Fib comes because she wants the number of such sequences

-- 
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-08 Thread Raj N 
@Divya: That was the question i previously asked. If n=3 000,001,010,100,101
are valid. So the solution for this is fib(n+2).
If n=4 no. of sequences will be fib(6) i.e 8

On Tue, Jun 8, 2010 at 9:31 AM, Rohit Saraf wrote:

> getting fibonacci nos is trivial using matrix multiplication in almost
> constant time.
>
> --
> Rohit Saraf
> Second Year Undergraduate,
> Dept. of Computer Science and Engineering
> IIT Bombay
> http://www.cse.iitb.ac.in/~rohitfeb14
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: binary nos

2010-06-07 Thread Rohit Saraf 
getting fibonacci nos is trivial using matrix multiplication in almost
constant time.

--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.