Computer Club MNNIT
Would you like to react to this message? Create an account in a few clicks or log in to continue.

count total trees

5 posters

Go down

count total trees Empty count total trees

Post  Admin Sat Aug 30, 2008 11:00 am

Write a program to count the total no. of binary trees possible with n nodes.
Try to optimise the solution.

Admin
Admin

Posts : 39
Join date : 2008-08-03

https://computerclub09mnnit.forumotion.net

Back to top Go down

count total trees Empty Re: count total trees

Post  shivang Sat Aug 30, 2008 1:12 pm

the total number of different binary trees that can be formed with n nodes can be given by CATALAN NUMBER
if b(n) denotes the no of different trees of n nodes than

b(n) = (2n)! / ( (n)!(n+1)! )
shivang
shivang

Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174

Back to top Go down

count total trees Empty Re: count total trees

Post  ankurgutpa Sun Aug 31, 2008 11:18 am

elaboration please? cheers
ankurgutpa
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 36
Location : Tandon 72

Back to top Go down

count total trees Empty @papa

Post  prani Sun Sep 07, 2008 11:24 am

try googling
Catalan Numbers:
the number of binary search trees possibble with n nodes is same as
--number of path in an nxn matrix above the leading diagonal from start to end
--the number of ways n people in a circlecan shake hands so that no hands cross
etc..
CLRS me dekho..

prani

Posts : 15
Join date : 2008-08-12

Back to top Go down

count total trees Empty Re: count total trees

Post  Akash Kumar Wed Sep 10, 2008 8:55 am

Hi there,

Good to see this forum active. great work final years. It s good to see you guys actively participating in this forum and better still is to see that you guys are interested in the mathematical appeal of algorithms.

BTW here is another catalan number problem...You have a stack. It has a stream of numbers 1,2,3........N as input in that order. At any stage the stack spits out an element which is then printed on the screen. Your task is NOT to find the number of N-lettered strings printable using the stack ,I answered that (as if it were needed)..

No, You have to tell why the catalan recurrence fits in this case. Its simple, but still I feel, you should attempt it.

Akash Kumar

Posts : 4
Join date : 2008-09-10

Back to top Go down

count total trees Empty @Akash Sir

Post  prani Thu Sep 11, 2008 5:27 am

Question not clear...

prani

Posts : 15
Join date : 2008-08-12

Back to top Go down

count total trees Empty Clarifying the Question

Post  Akash Kumar Fri Sep 12, 2008 8:27 am

Hello,

Yaar question hai -

You have a stack which to which we feed a stream of integers 1,2,3 .... N as input. At any time during the stream eating process the stack can choose to hold the stream off for a while and have the element (or elements) on its top popped. the element popped from the stack gets printed. It is given that your stack will consume every element and have it popped when it likes. Thus the stack will print a string of N-letters in some order. Clearly some strings are printable using the stack and some are unprintable.

This is a Catalan Number Problem and we know that the number of possible printable strings when you have N-letters equals a Catalan Number. I hope you guys know the Catalan Number recurrence. I want you to show how you can arrive at that recurrence in this problem. Sure, you can throw in an analogy with some other Catalan Number problem - but spare it. I would like you to establish this recurrence for this particular case.

Hope this makes the problem more clear (or did it confuse the matters more Smile - if so tell me - I would then let you know whatever the hell i meant to say)

Akash Kumar

Posts : 4
Join date : 2008-09-10

Back to top Go down

count total trees Empty @Akash Sir..

Post  prani Fri Sep 12, 2008 12:01 pm

For the n numbers in the stack..
Let Cn be the total number of strings
Now if we pop i elements from the string,The problem brakes down to two sub problem of length
Ci,Cn-i.
So ,Cn=Summations of(Ci*Cn-i) i from 1 to n
which is the popular Catalan number recurrence

prani

Posts : 15
Join date : 2008-08-12

Back to top Go down

count total trees Empty Re: count total trees

Post  Akash Kumar Sat Sep 13, 2008 11:53 am

Yeah you are right...

But there is a scope for clarifying your answer better still... You see, the letter which gets printed at the end is a special character in the sense that you need to have an empty stack before this element makes its grand entry into the stack...

Thus, you obtain the recurrence saying Number of printable sequences = sum of Ci*Cn-i-1 where i goes from 1 to N....

It is actually this point I wanted to stress...Thats where the problem has a subtle jump. If you say that pushing and then popping i numbers first contributes Ci and then pushing remaining n-i elements and popping them contributes Cn-i - well thats were most of us make a mistake....

Think this way - I can have i elements pushed and all popped and then a set of j elements all pushed and popped followed by which remaining n-(j+i) are pushed and all popped - this will not support the Catalan recurrence!

Thats because you did not define the recurrence right.. To define it the right way, you need to make a comment about the last element the stack prints..

Give it a little more thought if you like...This problem requires nothing but a careful definition of recurrence and thats why I asked it....Just be careful when you define a recurrence..

Hope u understand it
-Akash

Akash Kumar

Posts : 4
Join date : 2008-09-10

Back to top Go down

count total trees Empty Re: count total trees

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum