Chapter_15_Dynamic_Programming/exercises_15.5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.5 Optimal binary search trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.5-1\n",
    "\n",
    "> Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST$(root)$ which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.10, your procedure should print out the structure corresponding to the optimal binary search tree shown in Figure 15.9(b)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "CONSTRUCT-OPTIMAL-BST(root, i, j, last=0)\n",
    " 1 if i L j\n",
    " 2     return\n",
    " 3 if last == 0\n",
    " 4     print root[i, j] + \"is the root\"\n",
    " 5 elseif j < last:\n",
    " 6     print root[i, j] + \"is the left child of\" + last\n",
    " 7 else\n",
    " 8     print root[i, j] + \"is the right child of\" + last\n",
    " 9 CONSTRUCT-OPTIMAL-BST(root, i, root[i, j] - 1, root[i, j])\n",
    "10 CONSTRUCT-OPTIMAL-BST(root, root[i, j] + 1, j, root[i, j])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.5-2\n",
    "\n",
    "> Determine the cost and structure of an optimal binary search tree for a set of $n = 7$ keys with the following probabilities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$k_4$ is the root\n",
    "$k_2$ is the left child of $k_4$\n",
    "$k_1$ is the left child of $k_2$\n",
    "$d_0$ is the right child of $k_1$\n",
    "$d_1$ is the right child of $k_1$\n",
    "$k_3$ is the right child of $k_2$\n",
    "$d_2$ is the left child of $k_3$\n",
    "$d_3$ is the right child of $k_3$\n",
    "$k_5$ is the right child of $k_4$\n",
    "$d_4$ is the left child of $k_5$\n",
    "$d_5$ is the right child of $k_5$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.5-3\n",
    "\n",
    "> Suppose that instead of maintaining the table $w[i, j]$, we computed the value of $w(i, j)$ directly from equation (15.12) in line 9 of OPTIMAL-BST and used this computed value in line 11. How would this change affect the asymptotic running time of OPTIMAL-BST?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(n^3)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.5-4 $\\star$\n",
    "\n",
    "> Knuth [212] has shown that there are always roots of optimal subtrees such that $root[i, j - 1] \\le root[i, j] \\le root[i + 1, j]$ for all $1 \\le i < j \\le n$. Use this fact to modify the OPTIMAL-BST procedure to run in $O(n^2)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    " 10 for r = root[i, j-1] to root[i + 1, j]\n",
    "```"
   ]
  }
 ],
 "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
}