Chapter 8 - Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 8: Dynamic Programming (Completed 6/26: 23%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Edit Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.1 [3]\n",
    "\n",
    "Typists often make transposition errors exchanging neighboring characters, such as typing “setve” when you mean “steve.” This requires two substitutions to fix under the conventional definition of edit distance. Incorporate a swap operation into our edit distance function, so that such neighboring transposition errors can be fixed at the cost of one operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The following is nearly verbatim from the text (including errata), except for the addition of option 4, which is the new swap operation.\n",
    "\n",
    "Let $D[i,j]$ be the minimum number of differences between the segment of $P$ ending at position $i$ and the segment of $T$ ending at position $j$. $D[i,j]$ is the *minimum* of the **four** possible ways to extend smaller strings:\n",
    "\n",
    "1. If ($P_i = T_j$), then $D[i-1, j-1]$, else $D[i-1, j-1] + 1$. This means we either match or substitute the $i$th and $j$th characters, depending upon whether the tail characters are the same.\n",
    "2. $D[i − 1, j] + 1$. This means that there is an extra character in the text to account for, so we do not advance the pattern pointer and pay the cost of an insertion.\n",
    "3. $D[i, j − 1] + 1$. This means that there is an extra character in the pattern to remove, so we do not advance the text pointer and pay the cost on a deletion.\n",
    "4. If ($P_{i} = T_{j-1}$ and $P_{i-1} = T_{j}$), then $D[i-1, j-1]$. This means that characters in P at positions $i-1$ and $i$ are the same as those in T at positions $j-1$ and $j$, only swapped. We must have already payed a cost of 1 for the mismatch between $P_{i-1}$ and $T_{j-1}$ so we advance both patterns and do not pay a second time, for a total cost of 1 for a swap operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.2 [4]\n",
    "\n",
    "Suppose you are given three strings of characters: $X$, $Y$, and $Z$, where $|X| = n$, $|Y| = m$, and $|Z| = n + m$. $Z$ is said to be a *shuffle* of $X$ and $Y$ iff $Z$ can be formed by interleaving the characters from $X$ and $Y$ in a way that maintains the left-to-right ordering of the characters from each string.\n",
    "\n",
    "**(a):** Show that \"*cchocohilaptes*\" is a shuffle of \"*chocolate*\" and \"*chips*\", but \"*chocochilatspe*\"\n",
    "is not.  \n",
    "**(b):** Give an efficient dynamic-programming algorithm that determines whether $Z$ is a shuffle of $X$ and $Y$. Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "\"$\\text{cchocohilaptes}$\" can be written as \"$\\text{(c)choco(h)(i)la(p)te(s)}$\" where letters surrounded by parentheses indicate they are from the word \"chips\", and letters without parentheses are from \"chocolate\". The letters in each group are in the same order as in their parent word. Therefore \"cchocohilaptes\" is indeed a shuffle of \"chocolate\" and \"chips\".\n",
    "\n",
    "However, within \"$\\text{chocochilatspe}$\", there is an \"s\" followed by a \"p\". Neither of these letters appear in \"chocolate\", and so they must be from \"chips\". But in \"chips\" their order is \"p\" then \"s\", while in \"chocochilatspe\" it is \"s\" then \"p\". Proper shuffles must maintain the letter orders of the parent strings. Therefore \"chocochilatspe\" cannot be a shuffle of \"chocolate\" and \"chips\".\n",
    "\n",
    "**(b):**\n",
    "\n",
    "We wish to answer the question \"can string $Z$ be expressed as a shuffle of strings $X$ and $Y$?\". This is a boolean question. We would like to express this question in terms of smaller substrings, enabling us to construct a dynamic programming matrix of answers to identical questions on these smaller substrings.\n",
    "\n",
    "Two natural possibilities are to parametrize the matrix with an index $k$ along string $Z$, or with two indices $i$ and $j$, the first along $X$ and the second along $Y$. Note that we must have $i + j = k$, meaning that if the first $i$ characters of $X$ and the first $j$ characters of $Y$ can be shuffled to match the beginning of $Z$, this beginning substring of $Z$ must have $i + j = k$ characters. This suggests using a 2D matrix for indices $i$ and $j$, instead of a 1D array for index $k$.\n",
    "\n",
    "Let $B[i,j]$ indicate whether the first $i$ characters of $X$ and the first $j$ characters of $Y$ can be shuffled to match the first $i + j = k$ characters of $Z$.\n",
    "\n",
    "Two subtle, but important things to note: our definition of $B$ assumes that the beginning of the strings are padded with a space, otherwise $i$ would mean the first $i+1$ characters of $X$. For example, $X[1]$ would refer to the *second* character of $X$ rather than the *first*. Second, this padding with a space is necessary for another reason. If a word as $n$ letters, we need to be able to express including 0 of these letters up to including all of them. Therefore we need $n+1$ different values for our index.\n",
    "\n",
    "$B$ can then be written recursively as:\n",
    "\n",
    "$$ B[i,j] = \\left(B[i-1, j] \\text{ AND } Z[i+j]=X[i]\\right)\\text{ OR } \\left( B[i, j-1] \\text{ AND } Z[i+j]=Y[j] \\right)$$\n",
    "\n",
    "meaning the current character of $Z$, $Z[i+j]$, must match either $X[i]$ or $Y[j]$, and for each, the previous substring of $Z$ up to character $i + j -1$ must be a shuffle with that parent string's index decremented.\n",
    "\n",
    "Basis cases:  \n",
    "$B[0, j] = B[0, j-1] \\text{ AND } Z[j]=Y[j]$  \n",
    "$B[i, 0] = B[i-1, 0] \\text{ AND } Z[i]=X[i]$  \n",
    "$B[0, 0] = \\text{True}$\n",
    "\n",
    "Note that matrix will be of dimension $(|X|+1)\\times(|Y|+1) = (n+1) \\times (m+1$). In the program below, however, $n$ and $m$ are defined as the lengths of strings $X$ and $Y$ *after* the strings have been padded with a space.\n",
    "\n",
    "The algorithm is $O(nm)$ since there are two nested loops of size $O(n)$ and $O(m)$, with constant time operations within the inner loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def is_shuffle(X, Y, Z):\n",
    "    X = ' ' + X\n",
    "    Y = ' ' + Y\n",
    "    Z = ' ' + Z\n",
    "    \n",
    "    n = len(X)\n",
    "    m = len(Y)\n",
    "    \n",
    "    if (n + m - 1) != len(Z):\n",
    "        return False\n",
    "    \n",
    "    Matrix = [[False for x in range(m)] for y in range(n)]\n",
    "    \n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            if (i == 0) and (j == 0):\n",
    "                Matrix[i][j] = True\n",
    "            if (i == 0) and (j != 0):\n",
    "                if Matrix[0][j-1] and (Y[j] == Z[j]):\n",
    "                    Matrix[i][j] = True\n",
    "            if (i != 0) and (j == 0):\n",
    "                if Matrix[i-1][0] and (X[i] == Z[i]):\n",
    "                    Matrix[i][j] = True\n",
    "            if (i != 0) and (j != 0):\n",
    "                if (Matrix[i][j-1] and (Y[j] == Z[i+j])) or (Matrix[i-1][j] and X[i] == Z[i+j]):\n",
    "                    Matrix[i][j] = True\n",
    "\n",
    "    return Matrix[n-1][m-1]\n",
    "\n",
    "X = 'chocolate'\n",
    "Y = 'chips'\n",
    "Z_True = 'cchocohilaptes' # True\n",
    "Z_False = 'chocochilatspe' # False\n",
    "    \n",
    "print(is_shuffle(X, Y, Z_True))\n",
    "print(is_shuffle(X, Y, Z_False))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Greedy Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.5 [4]\n",
    "\n",
    "Let $P_1, P_2, . . . , P_n$ be $n$ programs to be stored on a disk with capacity $D$ megabytes. Program $P_i$ requires $s_i$ megabytes of storage. We cannot store them all because $D < \\sum_{i=1}^{n} s_i$.\n",
    "\n",
    "**(a):** Does a greedy algorithm that selects programs in order of nondecreasing $s_i$ maximize the number of programs held on the disk? Prove or give a counterexample.  \n",
    "**(b):** Does a greedy algorithm that selects programs in order of nonincreasing order $s_i$ use as much of the capacity of the disk as possible? Prove or give a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "The statement is true: a greedy algorithm would maximize the number of programs held on the disk. We'll prove this by contradiction.\n",
    "\n",
    "First, let:  \n",
    "$P = $set of $n$ programs  \n",
    "$P^{(S)} = $ our \"solution\" set, a subset of $P$  \n",
    "$P^{(U)} = $ the set of programs **not** in the solution; the complement of $P^{(S)}$; not empty since \"we cannot store them all\"  \n",
    "$P_{largest}^{(S)} = $ the largest program in the solution  \n",
    "$P_{smallest}^{(U)} = $ the smallest program **not** in the solution  \n",
    "\n",
    "A solution $P^{(S)}$ is *greedy* if $P_i < P_{largest}^{(S)}$ implies $P_i \\in P^{(S)}$, that is, if all the programs smaller than $P_{largest}^{(S)}$ are also in the solution $P^{(S)}$. This is equal to the condition: $P^{(S)}$ is *greedy* if $P_{smallest}^{(U)} \\geq P_{largest}^{(S)}$, that is, if the smallest program **not** in the solution is larger than or equal to the largest program **in** the solution.\n",
    "\n",
    "To prove that the greedy solution contains the largest possible number of programs, we'll assume otherwise and produce a contradiction. Suppose that $P^{(S)}$ contains the largest possible number of programs while having a total size less than $D$, and that it is not greedy. Further, assume that a greedy solution would contain a smaller number of programs, and therefore would not be optimal.\n",
    "\n",
    "\n",
    "Since the solution set $P^{(S)}$ is not the greedy solution, there must be programs **not** in the solution that are smaller than $P_{largest}^{(S)}$. Specifically, we must have $P_{smallest}^{(U)} < P_{largest}^{(S)}$. We now propose the following algorithm for converting the given non-greedy solution into the greedy solution: we keep placing the smallest not-included program $P_{smallest}^{(U)}$ into the solution set if there is room, and if there isn't, we swap it with the largest program currently in the solution $P_{largest}^{(S)}$. Repeat this until the greedy solution is reached. In pseudocode:\n",
    "\n",
    "$\\hspace{2em} \\text{while } P_{smallest}^{(U)} < P_{largest}^{(S)}:$  \n",
    "$\\hspace{4em} \\text{if } \\text{size}(P^{(S)}) + P_{smallest}^{(U)} \\leq D:$  \n",
    "$\\hspace{6em} \\text{add } P_{smallest}^{(U)} \\text{ to } P^{(S)}$  \n",
    "$\\hspace{4em} \\text{else}:$  \n",
    "$\\hspace{6em} \\text{swap } P_{smallest}^{(U)} \\text{ with } P_{largest}^{(S)}$  \n",
    "$\\hspace{2em} \\text{If there is room, extend } P^{(S)} \\text{ with the greedy algorithm}$\n",
    "\n",
    "We wish to show 2 things:\n",
    "\n",
    "**(1)** *that this process can always be done*: as long as the solution isn't greedy, and therefore $P_{smallest}^{(U)} < P_{largest}^{(S)}$, swapping them will only decrease the size of the solution set, and therefore will always be allowed; and\n",
    "\n",
    "**(2)** *that the resulting greedy solution contains the same number of programs or greater than the original solution*: the swap operations maintain the same number of programs in the solution, but adding $P_l^{(U)}$ into the solution adds an additional program; thereore the size of the solution can only increase.\n",
    "\n",
    "Therefore the greedy solution will be at least as good (i. e., contain at least as many programs) as the original non-greedy solution. And if it contains the same number of programs, then it freed up more space on the disk by swapping larger programs for smaller ones.\n",
    "\n",
    "**(b):**\n",
    "\n",
    "No. Suppose we have two programs of size 2 and 3, and that our disk size is $D = 3$. The greedy algorithm will produce a solution set $\\{2|{-1}\\}$, containing one program and leaving 1 unit of free space. However, the solution $\\{3 | 0\\}$ would also contain only one program, but would leave no free space on the disk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.6 [5]\n",
    "\n",
    "Coins in the United States are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of $\\{d_1, . . . , d_k\\}$ units. We seek an algorithm to make change of $n$ units using the minimum number of coins for this country.\n",
    "\n",
    "**(a):** The greedy algorithm repeatedly selects the biggest coin no bigger than the amount to be changed and repeats until it is zero. Show that the greedy algorithm does not always use the minimum number of coins in a country whose denominations are $\\{1, 6, 10\\}$.  \n",
    "**(b):** Give an efficient algorithm that correctly determines the minimum number of coins needed to make change of $n$ units using denominations $\\{d_1, . . . , d_k\\}$. Analyze its running time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**\n",
    "\n",
    "Suppose we want change of 13 cents. The greedy algorithm will produce coins $\\{10, 1, 1, 1\\}$, while a smaller set of coins is $\\{6, 6, 1\\}$. Therefore the greedy algorithm did not produce a minimal set of coins.\n",
    "\n",
    "**(b):**\n",
    "\n",
    "Let $C[n] = $ the smallest number of coins needed to make change of $n$ cents.\n",
    "\n",
    "This can be written recursively as:\n",
    "\n",
    "$$C[n] = \\min_{d \\in D,\\, d \\leq n} C[n-d] + 1$$\n",
    "\n",
    "where $D = \\{d_1, . . . , d_k\\}$ are the denominations of the available coins. For example, change of 57 cents using US coins is \n",
    "$$C[57] = \\min_{d \\in D,\\, D \\leq n} C[d] + 1 = \\min \\left\\{ C[56],\\, C[52],\\, C[47],\\, C[32],\\, C[50] \\right\\} + 1$$\n",
    "\n",
    "Intuitively, 57 cents can be made with one additional coin from any set of coins with value $57 - d$, for any $d \\in D$.\n",
    "\n",
    "We can implement this recursive relation using dynamic progamming, where to find the number of coins needed to make change of $n$ cents, we make a 1D array of length $n+1$ and calculate the value of $C[i]$ for all $i$ up to $n$.\n",
    "\n",
    "It is assumed that a 1-cent coin is included so that coins can produce any amount of cents. Due to this, every value between $1$ and $n$ will be calculated at some point. If this wasn't true, then it may have been more space efficient to implement this with explicit recursion with caching using a dictionary, that way only needed values are computed.\n",
    "\n",
    "The algorithm fills up an array of size $n+1$, and for each cell computes the minimum of $\\leq k$ values, where $k$ is the number of different types of coins, each of which is a constant time look up. Therefore the algorithm is $O(nk)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 25 ms, sys: 795 µs, total: 25.8 ms\n",
      "Wall time: 25.3 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "203"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def subtract_coins(n, C, D):\n",
    "    A = []\n",
    "    for coin in D:\n",
    "        if n - coin >= 0:\n",
    "            A.append(C[n - coin])\n",
    "    return A\n",
    "\n",
    "def changer(n, D):\n",
    "    C = [0]\n",
    "    for i in range(1, n + 1):\n",
    "        C.append(min(subtract_coins(i, C, D)) + 1)\n",
    "    return C[n]\n",
    "\n",
    "D = [1, 5, 10, 25, 50]\n",
    "%time changer(10031, D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**It is possible** to improve the efficiency on repeated function calls by using a **closure**. This allows the cached values to persist beyond a single call. However, the set of coin denominations $D$ must be constant. Therefore the `changer_with_closure(D)` function implemented below takes a set of coin denominations and produces a `changer(n)` function that will \"change\" different coin values with that fixed currency, with cached values persisting.\n",
    "\n",
    "Repeated calls are shown to be much faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 28.2 ms, sys: 1.47 ms, total: 29.7 ms\n",
      "Wall time: 30.3 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "203"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Implementation using a closure\n",
    "def changer_with_closure(D):\n",
    "    C = [0]\n",
    "    \n",
    "    def dynamic_changer(n):   \n",
    "        if len(C) - 1 < n:\n",
    "            for i in range(len(C), n + 1):\n",
    "                C.append(min(subtract_coins(i)) + 1)\n",
    "        return C[n]\n",
    "    \n",
    "    def subtract_coins(n):\n",
    "        A = []\n",
    "        for coin in D:\n",
    "            if n - coin >= 0:\n",
    "                A.append(C[n - coin])\n",
    "        return A\n",
    "    \n",
    "    return dynamic_changer\n",
    "        \n",
    "D = [1, 5, 10, 25, 50]\n",
    "changer = changer_with_closure(D)\n",
    "%time changer(10031)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3 µs, sys: 0 ns, total: 3 µs\n",
      "Wall time: 5.01 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "203"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Repeat SAME computation on 100.31 dollars \n",
    "%time changer(10031)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Change for 0 cents with 0 coins\n",
      "Change for 1 cents with 1 coins\n",
      "Change for 2 cents with 2 coins\n",
      "Change for 3 cents with 3 coins\n",
      "Change for 4 cents with 4 coins\n",
      "Change for 5 cents with 1 coins\n",
      "Change for 6 cents with 2 coins\n",
      "Change for 7 cents with 3 coins\n",
      "Change for 8 cents with 4 coins\n",
      "Change for 9 cents with 5 coins\n",
      "Change for 10 cents with 1 coins\n",
      "Change for 11 cents with 2 coins\n",
      "Change for 12 cents with 3 coins\n",
      "Change for 13 cents with 4 coins\n",
      "Change for 14 cents with 5 coins\n",
      "Change for 15 cents with 2 coins\n",
      "Change for 16 cents with 3 coins\n",
      "Change for 17 cents with 4 coins\n",
      "Change for 18 cents with 5 coins\n",
      "Change for 19 cents with 6 coins\n",
      "Change for 20 cents with 2 coins\n",
      "Change for 21 cents with 3 coins\n",
      "Change for 22 cents with 4 coins\n",
      "Change for 23 cents with 5 coins\n",
      "Change for 24 cents with 6 coins\n",
      "Change for 25 cents with 1 coins\n"
     ]
    }
   ],
   "source": [
    "for i in range(0, 26):\n",
    "    print('Change for %d cents with %d coins' % (i, changer(i)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Number Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.18 [4] Unfinished\n",
    "\n",
    "Consider the problem of storing $n$ books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book $b_i$, where $1 \\leq i \\leq n$, that has a thickness $t_i$ and height $h_i$. The length of each bookshelf at this library is $L$.\n",
    "\n",
    "Suppose all the books have the same height $h$ (i.e. , $h = h_i = h_j$ for all $i$, $j$) and the shelves are all separated by a distance of greater than $h$, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest $i$ such that $b_i$ does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "First note that the fact that you cannot reorder the books is crucial for the correctness of the greedy algorithm. For example, suppose 7 books have thicknesses $\\{20, 20, 20, 50, 20, 20, 50\\}$ and shelves have length $100$. If we had to keep them in order, the greedy algorithm would place them on shelves as $\\text{Shelf 1} = \\{20, 20, 20 | -40\\}$, $\\text{Shelf 2} = \\{50, 20, 20 | -10\\}$, and $\\text{Shelf 3} =  \\{50 | -50\\}$, using 3 shelves with 100 units of free space. If they could be reordered, the optimal packing would be $\\text{Shelf 1} = \\{50, 50 |0\\}$ and $\\text{Shelf 2} = \\{20, 20, 20, 20, 20 |  0\\}$, using 2 shelves and leaving no free space.\n",
    "\n",
    "Second, note that Skiena does not define what he means by the \"optimal shelf placement\". This could mean \"using the smallest number of shelves\" or \"leaving the smallest amount of space free\". However, these two definitions are equivalent; an arrangement of the same books on the same number of shelves will take up the same amount of space, and therefore will leave the same amount of space free. For two arrangements to leave different amounts of space free, they must use different amounts of shelves.\n",
    "\n",
    "We will prove the optimality of the greedy algorithm by contradition. Suppose that a given arrangement $P$ uses $n$ shelves, but the greedy algorithm would use more than $n$ shelves.\n",
    "\n",
    "For simplicity, assume that there is no empty shelf space between books, meaning that on every shelf the books are pushed all the way to the left, and any free space occurs to their right.\n",
    "\n",
    "Without loss of generality, we will speak of the books being placed in their positions in catalog order.\n",
    "\n",
    "Because the current arrangement $P$ is not greedy, there must have occured a time when a book was placed on the next shelf, even though there was still room for it on the current shelf. Therefore in the current arrangement, there must be a book $i$ at the beginning of a shelf that can be moved to the end of the previous shelf. Let us make that move. Doing so will reduce the amount of free space on the earlier shelf and will increase the amount of free space on the later shelf. If the moved book was the only book on its shelf, then we have just freed up a shelf. Any further moves will ignore that shelf. If we repeat this move at many times as possible, we will have produced the greedy arrangement. And because each move could only decrease the amount of shelves moved, and never can increase, we can be sure that the greedy solution contains the same number of shelves or less than the original, \"optimal\" arrangement. But this contradicts our assumption that the greedy solution was not optimal.\n",
    "\n",
    "Therefore, the greedy arrangement is optimal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.24 [5]\n",
    "\n",
    "Given a set of coin denominations, find the minimum number of coins to make a certain amount of change."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Let $D = \\{d_1, ..., d_k\\}$ be the denominations of $k$ different types of coins in a currency, and let $C[n]$ be the minimal number of coins needed to equal $n$ cents. If we knew the value of $C[i]$ for all $i < n$, we could look up the number of coins needed to produce values of $n-d$ for all $d \\in D$. From each of these sets of coins, we would only need to add a single coin of denomination $d$ to equal $n$ cents. Therefore $C[n]$ is equal to the number of coins in the smallest of these sets, plus one. Written out, we have the recursion relation:\n",
    "\n",
    "$$C[n] = \\min_{d \\in D, \\, d \\leq n} C[n-d] + 1$$\n",
    "\n",
    "where the additional condition $d \\leq n$ is needed to ensure that $n-d \\geq 0$; otherwise we would be trying to produce a negative amount of cents, which... doesn't make sense.\n",
    "\n",
    "This recursive relation can be used to implement a \"dynamic\" program that calculates the value of $C[i]$ for all $i$ up to $n$, caching the results. Each computation will require a comparison of up to $k$ different values. Therefore the algorithm will be $O(nk)$.\n",
    "\n",
    "As done above for problem 8.6, this could be implemented using a closure so that the cached computations will persist across function calls. But in the spirit of an \"interview\" problem, I implemented this quickly and focused on correctness, not additional functionality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 cents with 0 coins\n",
      "1 cents with 1 coins\n",
      "2 cents with 2 coins\n",
      "3 cents with 3 coins\n",
      "4 cents with 4 coins\n",
      "5 cents with 1 coins\n",
      "6 cents with 2 coins\n",
      "7 cents with 3 coins\n",
      "8 cents with 4 coins\n",
      "9 cents with 5 coins\n",
      "10 cents with 1 coins\n",
      "11 cents with 2 coins\n",
      "12 cents with 3 coins\n",
      "13 cents with 4 coins\n",
      "14 cents with 5 coins\n",
      "15 cents with 2 coins\n",
      "16 cents with 3 coins\n",
      "17 cents with 4 coins\n",
      "18 cents with 5 coins\n",
      "19 cents with 6 coins\n",
      "20 cents with 2 coins\n",
      "21 cents with 3 coins\n",
      "22 cents with 4 coins\n",
      "23 cents with 5 coins\n",
      "24 cents with 6 coins\n",
      "25 cents with 1 coins\n"
     ]
    }
   ],
   "source": [
    "def changer(n, D):\n",
    "    C = []\n",
    "    C.append(0)\n",
    "    for i in range(1, n + 1):\n",
    "        C.append(min(smaller_coins(i, C, D)) + 1)\n",
    "    return C[n]\n",
    "\n",
    "def smaller_coins(i, C, D):\n",
    "    A = []\n",
    "    for d in D:\n",
    "        value = i - d\n",
    "        if value >= 0:\n",
    "            A.append(C[value])\n",
    "    return A\n",
    "\n",
    "D = [1, 5, 10, 25]\n",
    "for i in range(26):\n",
    "    print('%d cents with %d coins' % (i, changer(i, D)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.25 [5]\n",
    "\n",
    "You are given an array of $n$ numbers, each of which may be positive, negative, or zero. Give an efficient algorithm to identify the index positions $i$ and $j$ that maximize the sum of the ith through jth numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Let $A = \\{a_1, ..., a_n\\}$ be the array of numbers.\n",
    "\n",
    "A brute force method to find the largest contiguous sum would try all possible combinations of $i$ and $j$, calculating the sum each time. This would be $O(n^3)$.\n",
    "\n",
    "If we pre-computed the partial sums $S[i] = \\sum_{x=0}^{i} a_x$ and define $S[-1] = 0$, then the sum of the numbers between $i$ and $j$ would be $S[j] - S[i-1]$. This is a constant time operation, reducing our complexity to $O(n^2)$.\n",
    "\n",
    "We probably can't hope for an $O(n \\log n)$ algorithm, since we aren't allowed to sort the array.\n",
    "\n",
    "This problem has an inherent left-rightness, and so maybe a dynamic programming solution might work. Since there are 2 indices, we will try to find a solution that constructs either a 1D or 2D matrix.\n",
    "\n",
    "Suppose we isolate a left portion of the set $A$ between positions $0$ and some $j < n$. Furthermore, suppose we knew the maximum possible sum of a contiguous set of numbers *ending on position $j$*. We can denote this as $C[j]$. And now we want to know what is the largest possible sum of contiguous numbers *ending on position $j+1$*, $C[j+1]$. Well, $A[j+1]$ must be included in the sum. Is it possible to produce a sum larger than $A[j+1]$ by including previous numbers? If we do, the maximum possible contribution of this set of \"previous numbers\" is exactly $C[j]$. Therefore these numbers should be included only if $C[j] > 0$.\n",
    "\n",
    "Writing out this recursion relation, we have:\n",
    "$$ C[j] = A[j] + \\max\\left(0, C[j-1]\\right)$$\n",
    "\n",
    "This is a constant time operation. Therefore computing $C[j]$ for all $j$ from $0$ to $n-1$ will be $O(n)$. Afterwards, we can do a single linear scan to find the maximum value in $C$, which will be the largest possible contiguous sum. Then we can do one more scan backwards from the location of the maximum to find the matching index $i$ that produces that sum.\n",
    "\n",
    "To increase efficiency, the first of those two final linear scans can be avoided by tracking the largest value seen so far during the computation of the array $C$. This costs a small, constant amount of space, and saves us a search over all $n$ items in the array. \n",
    "\n",
    "The second final linear scan to locate the matching index $i$ can also be avoided if, during the computation of $C$, we record in a second array $I$ the locations of the corresponding $i$ indices. This will double the amount of linear space used, but save us a linear amount of time, depending on how many values are in the maximal contiguous set, which could be just $1$ or could be all $n$.\n",
    "\n",
    "These two improvements reduce the amount of linear scans over the array from 3 to 1.\n",
    "\n",
    "This algorithm will be $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Largest sum is 11 between i = 0 and j = 5\n"
     ]
    }
   ],
   "source": [
    "def largest_contiguous_sequence(A):\n",
    "    n = len(A)\n",
    "    I = [0]\n",
    "    C = [A[0]]\n",
    "    max_j = 0\n",
    "    \n",
    "    for j in range(1, n):\n",
    "        i = j\n",
    "        value = A[j]\n",
    "        if C[-1] > 0:\n",
    "            value += C[-1]\n",
    "            i = I[-1]\n",
    "        I.append(i)\n",
    "        C.append(value)\n",
    "        if value > C[max_j]:\n",
    "            max_j = j\n",
    "            \n",
    "    print('Largest sum is %d between i = %d and j = %d' % (C[max_j], I[max_j], max_j))\n",
    "\n",
    "largest_contiguous_sequence([10, -1, -1, -1, -1, 5, -1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}