Chapter_12_Binary_Search_Trees/exercises_12.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.4 Randomly built binary search trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.4-1\n",
    "\n",
    "> Prove equation (12.3).\n",
    "\n",
    "> $\\displaystyle \\sum_{i=0}^{n-1} \\binom{i+3}{3} = \\binom{n+3}{4}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\sum_{i=0}^{n-1} \\binom{i+3}{3}\n",
    "&=& \\displaystyle \\sum_{i=0}^{n-1} \\frac{(i+3)(i+2)(i+1)}{6} \\\\\n",
    "&=& \\displaystyle \\frac{1}{6} \\sum_{i=0}^{n-1} i^3 + 6i^2 + 11i + 6 \\\\\n",
    "&=& \\displaystyle \\frac{1}{6} \\left ( \\frac{(n-1)^2 n^2}{4} + \\frac{6(n-1)n(2n-1)}{6} + \\frac{11n(n-1)}{2} + 6n \\right ) \\\\\n",
    "&=& \\displaystyle \\frac{n(n+1)(n+2)(n+3)}{24} \\\\\n",
    "&=& \\displaystyle \\binom{n+3}{4}\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.4-2\n",
    "\n",
    "> Describe a binary search tree on n nodes such that the average depth of a node in the tree is $\\Theta(\\lg n)$ but the height of the tree is $\\omega(\\lg n)$. Give an asymptotic upper bound on the height of an $n$-node binary search tree in which the average depth of a node is $\\Theta(\\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Theta(\\sqrt{n \\lg n})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.4-3\n",
    "\n",
    "> Show that the notion of a randomly chosen binary search tree on $n$ keys, where each binary search tree of $n$ keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For $n=3$, there are 5 binary search trees. However, if we build the trees will a random permutation, the first tree will built twice.\n",
    "\n",
    "![](img/12.4-3_1.png)\n",
    "![](img/12.4-3_2.png)\n",
    "![](img/12.4-3_3.png)\n",
    "![](img/12.4-3_4.png)\n",
    "![](img/12.4-3_5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.4-4\n",
    "\n",
    "> Show that the function $f(x) = 2^x$ is convex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle f(x) + f(y) - 2f \\left ( \\frac{x + y}{2} \\right )\n",
    "&=& \\displaystyle 2^x + 2^y - 2 \\cdot 2^{(x + y)/2} \\\\\n",
    "&=& \\displaystyle (2^{x/2})^2 + (2^{y/2})^2 - 2 \\cdot 2^{x/2} \\cdot 2^{y/2} \\\\\n",
    "&=& \\displaystyle (2^{x/2} - 2^{y/2})^2 \\ge 0\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "Therefore $f(x) = 2^x$ is convex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.4-5 $\\star$\n",
    "\n",
    "> Consider RANDOMIZED-QUICKSORT operating on a sequence of $n$ distinct input numbers. Prove that for any constant $k > 0$, all but $O(1/n^k)$ of the $n!$ input permutations yield an $O(n\\lg n)$ running time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}