wu :: forums « wu :: forums - Non trivial BST Insertion » Welcome, Guest. Please Login or Register. Sep 18th, 2024, 7:47am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, william wu, Icarus, Eigenray, Grimbal, SMQ)    Non trivial BST Insertion « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Non trivial BST Insertion  (Read 1526 times)
howard roark
Full Member

Posts: 241
 Non trivial BST Insertion   « on: Feb 15th, 2009, 9:25pm » Quote Modify

Assume you are building a  BST (Binary Search tree) of n nodes using purely by insertions, that all keys are distinct, and that all key orderings for the insertions were equally likely.

Write an efficient algorithm which takes as input the root of a tree, and which returns the probability
that that particular tree would have been built under these assumptions.

Hint 1: If the tree has 3 nodes, root node and children on both sides of root node, probability of that tree is 1/3

PS:I thought this is a better place for this question than cs forums. Please tell me if I should move this to cs forums
 « Last Edit: Feb 16th, 2009, 5:55pm by howard roark » IP Logged
mistaken_id
Junior Member

Posts: 132
 Re: Non trivial BST Insertion   « Reply #1 on: Feb 16th, 2009, 9:55pm » Quote Modify

I doubt if the algorithm even needs n as input..
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #2 on: Feb 17th, 2009, 2:59am » Quote Modify

My first guess is to
1) count the nodes in each subtree
2) multiply for each node (#left+#right)!/left!/#right!  (where #left is the number of node in the left subtree, and analogous for #right)
3) divide the whole by #root!
That would be O(n) runtime if it checks out.
 « Last Edit: Feb 17th, 2009, 3:00am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member

Posts: 241
 Re: Non trivial BST Insertion   « Reply #3 on: Feb 17th, 2009, 12:23pm » Quote Modify

Cool! so the algo doesnt need n as the input.

However, run time does depend on n and it is O(n)....
 IP Logged
howard roark
Full Member

Posts: 241
 Re: Non trivial BST Insertion   « Reply #4 on: Feb 17th, 2009, 12:33pm » Quote Modify

what does #root mean?

#left+#right +1 ??
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #5 on: Feb 17th, 2009, 12:33pm » Quote Modify

You can calculate n by going through the tree (and in fact you have to, #root=n). And to be sure you account for the whole tree you need to visit every node, so you can't do better than O(n).
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #6 on: Feb 17th, 2009, 12:35pm » Quote Modify

on Feb 17th, 2009, 12:33pm, howard roark wrote:
 what does #root mean?   #left+#right +1 ??
For the root node, yes. I strictly use it for the top of the tree here though.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member

Posts: 241
 Re: Non trivial BST Insertion   « Reply #7 on: Feb 17th, 2009, 1:00pm » Quote Modify

I somehow feel that your algo assumes number of trees with n nodes is n!, which I think is wrong.

Number of trees with n nodes is Catalan-number (n).

I know I am wrong, Just tell me where I am wrong......
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #8 on: Feb 17th, 2009, 1:35pm » Quote Modify

on Feb 17th, 2009, 1:00pm, howard roark wrote:
 I somehow feel that your algo assumes number of trees with n nodes is n!, which I think is wrong.
Ah yes.
What the algorithm returns is the probability of a random sequence of input resulting in that particular tree. And there are n! such random input sequences.
But this does seem to be exactly what was asked for.

For instance take all inputs of 3 elements
1,2,3 ->  (1,(2,(3)))
1,3,2 ->  (1,((2),3))
2,1,3 ->  ((1),2,(3))
2,3,1 ->  ((1),2,(3))
3,1,2 ->  ((1,(2)), 3)
3,2,1 ->  (((1),2), 3)

The middle two result in the same tree, so we have probability 2/6=1/3 of getting that tree, exactly the number you gave.
 « Last Edit: Feb 17th, 2009, 1:36pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #9 on: Feb 17th, 2009, 3:02pm » Quote Modify

on Feb 17th, 2009, 1:00pm, howard roark wrote:
The possible input sequences are constraint only by the fact that the ancestor of a node has to come earlier in the sequence. So the positions of nodes in different subtrees are independent, as long as they come after their common ancestor. So if we ignore the order the elements of each subtree occurs in for a moment, we're just mixing two groups, which can be done in (n+m)!/(n!m!) ways. And then next we determine the order of those subgroups recursively.
 « Last Edit: Feb 17th, 2009, 3:03pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member

Posts: 241
 Re: Non trivial BST Insertion   « Reply #10 on: Mar 1st, 2009, 10:11pm » Quote Modify

Is the running time of the algorithm O(n).......I think it will be more than that, because as we move up we have to find factorials of larger numbers which are as big as n  in the root
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #11 on: Mar 2nd, 2009, 1:06am » Quote Modify

on Mar 1st, 2009, 10:11pm, howard roark wrote:
 Is the running time of the algorithm O(n).......I think it will be more than that, because as we move up we have to find factorials of larger numbers which are as big as n  in the root
You can make a table of all factorials you need with O(n) multiplications. Although that's a small comfort when the size of the result grows beyond the machineword. There might be ways to improve it though.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Non trivial BST Insertion   « Reply #12 on: Mar 2nd, 2009, 5:50am » Quote Modify

We can also write it as P(T) = 1/|T| * P(L)*P(R), which looks pretty nice (looks better in my head than on the page though).

Let F(n) be the maximum value of P(T) over all trees of size n.  Then n!*F(n) is the number of heaps of size n.
 « Last Edit: Mar 2nd, 2009, 8:05am by Eigenray » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Non trivial BST Insertion   « Reply #13 on: Mar 2nd, 2009, 6:51am » Quote Modify

on Mar 2nd, 2009, 5:50am, Eigenray wrote:
 We can also write it as P(T) = 1/|T| * P(L)*P(R), which looks pretty nice.
Indeed it does. And the interpretation that goes with it is so much simpler as well. In any subtree every node has an equal chance of being the root.
Or to put it another way, you can create the tree by putting all elements in a row, and then recursively pick one from the row uniformly randomly to function as root, and splitting the row in two at its position. Then repeat for both subtrees.

I liked the old version of the formula better [/edit]
 « Last Edit: Mar 2nd, 2009, 6:54am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
howard roark
Full Member

Posts: 241
 Re: Non trivial BST Insertion   « Reply #14 on: Mar 2nd, 2009, 8:12pm » Quote Modify

on Mar 2nd, 2009, 5:50am, Eigenray wrote:
 Let F(n) be the maximum value of P(T) over all trees of size n.  Then n!*F(n) is the number of heaps of size n.

How is the above result possible?
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Non trivial BST Insertion   bstmp256.gif « Reply #15 on: Mar 2nd, 2009, 10:23pm » Quote Modify

F(n) = maxk<n  C(n-1,k) F(k) F(n-1-k).

Compared to the other formula it's not surprising.  Attached are the plots of { C(n-1,k) F(k) F(n-1-k) :  0  k < n }, for n =1,...,256.  Note the two maxima that look like they are moving back and forth.  The index moving to the left is actually standing still at (one less than) a power of 2; the other one grows until it reaches the next (one less than a) power of 2.
 « Last Edit: Mar 2nd, 2009, 10:25pm by Eigenray » IP Logged

 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »