exp(x) inequality

Quick one.

Use induction to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$.

$n$ is a natural number $\ge 0$.

[Solution]

Number of AVL trees [Solution]

The problem was to compute the number of AVL tree of $n$ nodes.

Solution

---

The solution is very similar to that of the corresponding problem for red-black trees.

Using dynamic programming, try to compute $T[n, h]$ the number of AVL trees on $n$ nodes with height $h$.

Now write a recursive formula based on the AVL tree properties, and you have an algorithm.

I will leave the details to you.