Question

Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.

Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with $k = 2^n$ nodes.

Here are my questions:

1) What is the worst-case tree for weighted quick union?

2) How I compute the average depth of a node in this worst-case tree with $2^n$ nodes?

I tried to show through induction that the number of nodes at each level for the worst-case tree in weighted quick-union are binomial coefficients (the first level has $\frac{1!}{0!(1-0)!} = 1$ node). From there I tried to think about how, generally, there are at most $\frac{n!}{r!(n-r)!}$ nodes at the next level. However, I'm unable to think of reasons as to how this makes sense.

Any help with this question is appreciated.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top