Chapter_15_Dynamic_Programming/exercises_15.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15.2 Matrix-chain multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-1\n",
    "\n",
    "> Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is $\\left \\langle 5, 10, 3, 12, 5, 50, 6 \\right \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Table $m$:\n",
    "\n",
    "|  | 1 | 2 | 3 | 4 | 5 | 6 |\n",
    "| :---: | :---: | :---: | :---: | :---: | :---: | :---: |\n",
    "| 1 | 0 | 150 | 330 | 405 | 1655 | 2010 |\n",
    "| 2 |  | 0 | 360 | 330 | 2430 | 1950 |\n",
    "| 3 |  |  | 0 | 180 | 930 | 1770 |\n",
    "| 4 |  |  |  | 0 | 3000 | 1860 |\n",
    "| 5 |  |  |  |  | 0 | 1500 |\n",
    "| 6 |  |  |  |  |  | 0 |\n",
    "\n",
    "Table $s$:\n",
    "\n",
    "|  | 1 | 2 | 3 | 4 | 5 | 6 |\n",
    "| :---: | :---: | :---: | :---: | :---: | :---: | :---: |\n",
    "| 1 |  | 1 | 2 | 2 | 4 | 2 |\n",
    "| 2 |  |  | 2 | 2 | 2 | 2 |\n",
    "| 3 |  |  |  | 3 | 4 | 4 |\n",
    "| 4 |  |  |  |  | 4 | 4 |\n",
    "| 5 |  |  |  |  |  | 5 |\n",
    "| 6 |  |  |  |  |  |  |\n",
    "\n",
    "Optimal parenthesization:\n",
    "\n",
    "$$\n",
    "(A_1 \\times A_2) \\times ((A_3 \\times A_4) \\times (A_5 \\times A_6))\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-2\n",
    "\n",
    "> Give a recursive algorithm MATRIX-CHAIN-MULTIPLY$(A, s, i, j)$ that actually performs the optimal matrix-chain multiplication, given the sequence of matrices $\\langle A_1, A_2, \\dots ,A_{n_i} \\rangle$, the $s$ table computed by MATRIX-CHAIN-ORDER, and the indices $i$ and $j$. \\(The initial call would be MATRIX-CHAIN-MULTIPLY$(A, s, 1, n)$.\\)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "MATRIX-CHAIN-MULTIPLY(A, s, i, j)\n",
    "1 if i == j\n",
    "2     return A[i]\n",
    "3 if i + 1 == j\n",
    "4     return A[i] * A[j]\n",
    "5 b = MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j])\n",
    "6 c = MATRIX-CHAIN-MULTIPLY(A, s, s[i, j] + 1, j)\n",
    "7 return b * c\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-3\n",
    "\n",
    "> Use the substitution method to show that the solution to the recurrence \\(15.6\\) is $\\Omega(2^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $P(n) \\ge c2^n$,\n",
    "\n",
    "\n",
    "$$\n",
    "\\begin{array}{rlll}\n",
    "P(n) &\\ge& \\displaystyle \\sum_{k=1}^{n-1} c2^k \\cdot c2^{n-k} \\\\\n",
    "&=& \\displaystyle \\sum_{k=1}^{n-1} c^2 2^n \\\\\n",
    "&=& \\displaystyle c^2 (n - 1) 2^n \\\\\n",
    "&\\ge& \\displaystyle c^2 2^n & (n > 1) \\\\\n",
    "&\\ge& \\displaystyle c 2^n & (0 < c \\le 1)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-4\n",
    "\n",
    "> Describe the subproblem graph for matrix-chain multiplication with an input chain of length $n$. How many vertices does it have? How many edges does it have, and which edges are they?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vertice: $O(n^2)$, edges: $O(n^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-5\n",
    "\n",
    "> Let $R(i, j)$ be the number of times that table entry $m[i, j]$ is referenced while computing other table entries in a call of MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is  \n",
    "> $\\displaystyle \\sum_{i=1}^n \\sum_{j=i}^n R(i, j) = \\frac{n^3 - n}{3}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\sum_{i=1}^n \\sum_{j=i}^n R(i, j) = \\sum_{l=2}^n 2 (n - l + 1) (l - 1) = \\frac{n^3 - n}{3}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2-6\n",
    "\n",
    "> Show that a full parenthesization of an $n$-element expression has exactly $n-1$ pairs  \n",
    "> of parentheses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$n - 1$ multiplications."
   ]
  }
 ],
 "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
}