Chapter 1 - Intro to Algorithm Design.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises from The Algorithm Design Manual, by Steven Skiena"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 1: Introduction to Algorithm Design (Completed 32/34: 94%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding Counterexamples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 [3]\n",
    "\n",
    "Show that $a + b$ can be less than $\\min{(a, b)}$.\n",
    "\n",
    "*Solution:*  \n",
    "Let $a = -1$ and $b = -1.$  \n",
    "Then $a + b = (-1) + (-1) = -2.$  \n",
    "But $\\min{(a,b)} = \\min{(-1, -1)} = -1.$  \n",
    "Since $-2 < -1$, we have shown that  $a + b < \\min{(a, b)}.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 [3]\n",
    "\n",
    "Show that $a \\times b$ can be less than $\\min{(a, b)}$.\n",
    "\n",
    "*Solution:*  \n",
    "Let $a = 5$ and $b = -1.$  \n",
    "Then $a \\times b = 5 \\times -1 = -5.$  \n",
    "But $\\min{a,b} = \\min{5,-1} = -1.$  \n",
    "Since $-5 < -1$, we have shown that $a \\times b < \\min{(a,b)}.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 [5]\n",
    "\n",
    "Design / draw a road network with two points $a$ and $b$ such that the fastest route\n",
    "between $a$ and $b$ is not the shortest route.\n",
    "\n",
    "*Solution:*  \n",
    "This can only happen if the time taken to travel a road depends on more than just its length. For example, roads often have speed limits. Therefore suppose there are 2 roads connecting $a$ and $b$, one of which is 1 mile long but has a speed limit of 1 mile per hour, and another that is 2 miles long but has a speed limit of 4 miles per hour. The second road is twice as long but will take half the time to traverse."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 [5]\n",
    "\n",
    "Design / draw a road network with two points $a$ and $b$ such that the shortest\n",
    "route between $a$ and $b$ is not the route with the fewest turns.\n",
    "\n",
    "*Solution:*  \n",
    "Suppose $a = (0,0)$ and $b = (10,0)$.  \n",
    "Let Route 1 go up to (0,100), right to (10,100), and back down to (0,10).\n",
    "So Route 1 has length 210 and has 3 turns (assuming you were originally facing right).\n",
    "Let Route 2 go up to (0,1), right to (1,1), down to (1, -1), right to (2,-1), up to (2,0), and right to (10,0).\n",
    "So Route 2 has length 14 and has 6 turns.\n",
    "Therefore Route 2 is shorter, but has more turns than Route 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 [4]\n",
    "\n",
    "The *knapsack problem* is as follows: given a set of integers $S = \\{s_1, s_2, . . . , s_n\\}$,\n",
    "and a target number $T$, find a subset of $S$ which adds up exactly to $T$. For example,\n",
    "there exists a subset within $S = \\{1, 2, 5, 9, 10\\}$ that adds up to $T = 22$ but not\n",
    "$T = 23$.\n",
    "\n",
    "Find counterexamples to each of the following algorithms for the knapsack problem.\n",
    "That is, giving an $S$ and $T$ such that the subset selected using the algorithm does\n",
    "not leave the knapsack completely full, even though such a solution exists.\n",
    "\n",
    "1. Put the elements of $S$ in the knapsack in left to right order if they fit, i.e. the\n",
    "first-fit algorithm.\n",
    "\n",
    "2.  Put the elements of $S$ in the knapsack from smallest to largest, i.e. the best-fit\n",
    "algorithm.\n",
    "\n",
    "3.  Put the elements of $S$ in the knapsack from largest to smallest.\n",
    "\n",
    "*Solution:*  \n",
    "**(1)**:  \n",
    "Let $S = \\{1, 2, 5, 9, 10\\}$ and $T = 22$.  \n",
    "If I understand the algorithm correctly, it will continue adding elements left to right until no more can fit. In this case it will put the elements $\\{1, 2, 5, 9\\}$ into the bag for a total of 17, while the set $\\{1, 2, 9, 10\\}$ would have correctly given $T = 22$. Therefore the algorithm is incorrect.\n",
    "\n",
    "**(2)**:  \n",
    "Same as the previous part, let $S = \\{1, 2, 5, 9, 10\\}$ and $T = 22$.  \n",
    "And just like the previous part, the algorithm will place the elements $\\{1, 2, 5, 9\\}$ into the bag for a total of 17, while the set $\\{1, 2, 9, 10\\}$ would have correctly given $T = 22$. Therefore the algorithm is incorrect.\n",
    "\n",
    "**(3)**:  \n",
    "Same as the previous part, let $S = \\{1, 2, 5, 9, 10\\}$ and $T = 22$.  \n",
    "In this case the algorithm will place the subset $\\{10, 9\\}$ into the bag for a total of 19, even though the set $\\{1, 2, 9, 10\\}$ would have correctly given $T = 22$. Therefore the algorithm is incorrect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 [5]\n",
    "\n",
    "The *set cover problem* is as follows: given a set of subsets $S = S_1, ..., S_m$ of the\n",
    "universal set $U = \\{1, ..., n\\}$, find the smallest subset of subsets $T \\subset S$ such that\n",
    "$\\cup_{t_{i}\\in T}t_i = U$. For example, there are the following subsets, $S_1 = \\{1, 3, 5\\}$, $S_2 =\n",
    "\\{2, 4\\}$, $S_3 = \\{1, 4\\}$, and $S_4 = \\{2, 5\\}$ The set cover would then be $S_1$ and $S_2$.\n",
    "\n",
    "\n",
    "Find a counterexample for the following algorithm:\n",
    "\n",
    "\n",
    "$\\hspace{2em} \\text{Select the largest subset for the cover,}$  \n",
    "$\\hspace{2em} \\text{and then delete all its elements from the universal set.}$  \n",
    "$\\hspace{2em} \\text{Repeat by adding the subset containing the largest number of uncovered elements until all are covered.}$\n",
    "\n",
    "*Solution:*  \n",
    "Let $U = \\{1, \\ldots , 10\\}$.  \n",
    "Let $S_1 = \\{1, \\ldots 8\\}$, $S_2 = \\{9\\}$, $S_3 = \\{10\\}$, $S_4 = \\{4, \\ldots 10\\}$, and $S_5 = \\{1, 2, 3\\}$.  \n",
    "$S_1$ is the largest set, so the algorithm will first pick $S_1$, and then delete those elements from $U$, leaving $U = \\{1, 2\\}$. Neither $S_4$ nor $S_5$ contain elements in $U$, so they will be ignored and $S_2$ and $S_3$ will successively be picked, resulting in the covering $T = \\{S_1, S_2, S_3\\}$ with 3 subsets.  \n",
    "However, $T = \\{S_4, S_5\\}$ would also cover $U$, but with 2 subsets.  \n",
    "Therefore the algorithm failed to select the correct output, and so is incorrect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Proofs of Correctness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.7 [3]\n",
    "\n",
    "Prove the correctness of the following recursive algorithm to multiply two\n",
    "natural numbers, for all integer constants $c \\geq 2$.\n",
    "\n",
    "$\\hspace{2em} function \\text{ multiply}(y, \\, z)$  \n",
    "$\\hspace{2em} comment \\text{ Return the product } yz.$  \n",
    "$\\hspace{4em} if \\>  z = 0 \\>  then  \\text{ return}\\,(0) \\> else$  \n",
    "$\\hspace{4em} \\text{return } (\\, \\text{multiply}(cy, \\lfloor z/c\\rfloor) + y \\cdot (z\\bmod c)\\,)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "*Solution:*  \n",
    "First, let's clarify that the natural numbers are $\\mathbb{N} = \\{0, 1, \\ldots\\}$, where we include 0 just to make sure we are covering all our bases.\n",
    "\n",
    "Now onto the problem. Two important things to note are that 1) we are asked to show the correctness of a recursive algorithm, and so almost surely we will use mathematical induction; and 2) we have 3 variables: $y$, $z$, and $c$. Must we increment all of them in our induction proof? I guess it depends on whether we need their induction hypotheses to show algebraic equality. Note that in the recursive function call, the $y$ argument is multiplied by $c$, and so is larger. Therefore the induction hypothesis won't help for $y$. The $z$ argument gets smaller, so here an induction hypothesis would be helpful. What about $c$? Well $c$ is never changed within the algorithm, and it doesn't look like it would be fruitful to try to express $c$ as a sum or product in order to leverage an induction hypothesis.\n",
    "\n",
    "So if our induction proof is to parallel the algorithm's recursion, we'll only try to increment $z$.\n",
    "\n",
    "*Base case:* $z=0$.  \n",
    "If $z=0$, the algorithm returns $0$. And since $y\\cdot 0 = 0$ for any $y$, it is correct.  \n",
    "\n",
    "*Base case:* $z=1$.  \n",
    "If $z=1$, the algorithm returns $\\text{(multiply}\\,(cy, \\lfloor 1/c\\rfloor) + y \\cdot (1\\bmod c))$.  \n",
    "Since $1<c$, we have $\\lfloor 1/c\\rfloor = 0$ and $1\\bmod c = 1$.  \n",
    "Therefore our expression becomes $\\text{(multiply}\\,(cy, 0) + y \\cdot 1) = 0 + y = y$.  \n",
    "And so the algorithm produces the correct result.\n",
    "\n",
    "*General case:*  \n",
    "Suppose the algorithm correctly produces the correct answer for $z \\leq p-1$, where $p > 1$.  \n",
    "Suppose $z = p$.  \n",
    "\n",
    "We then have:  \n",
    "$\\hspace{1em} \\text{multiply}\\,(y, \\, p)$  \n",
    "$\\hspace{2em} \\stackrel{(1)}{=} \\text{multiply}(cy, \\lfloor p/c\\rfloor) + y \\cdot (p\\bmod c)$  \n",
    "$\\hspace{2em} \\stackrel{(2)}{=} cy \\cdot \\lfloor p/c\\rfloor + y \\cdot (p\\bmod c)$  \n",
    "$\\hspace{2em} \\stackrel{(3)}{=} y \\cdot \\left[c \\lfloor p/c\\rfloor + p\\bmod c\\right]$  \n",
    "$\\hspace{2em} \\stackrel{(4)}{=} y p$\n",
    "\n",
    "where:  \n",
    "$(1):$ Since $z \\neq 0$.  \n",
    "$(2):$ Because $c \\geq 2$ we know that $\\lfloor p/c\\rfloor < p$, and therefore our induction hypothesis implies that $\\text{multiply}(cy, \\, \\lfloor p/c\\rfloor) = cy \\cdot \\lfloor p/c\\rfloor$.  \n",
    "$(3):$  Factoring out y.  \n",
    "$(4):$ $p$ can be uniquely expressed as $p = nc + m$ for some natural numbers $n, m$, where $m < c$; specifically, $n = \\lfloor p/c\\rfloor$ and $ m = p\\bmod c$.  \n",
    "\n",
    "Therefore, we have shown that $\\text{multiply}\\,(y, \\, p) = y p$, and our proof is complete."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.8 [3]\n",
    "\n",
    "Prove the correctness of the following algorithm for evaluating the polynomial $P(x) = a_nx^n + a_{n-1}x^{n-1} + \\ldots + a_1x + a_0$.\n",
    "\n",
    "$\\hspace{2em} A = \\{a_n, \\ldots, a_0\\}$  \n",
    "$\\hspace{2em} function \\> \\text{horner}(\\,A,\\,x)$   \n",
    "$\\hspace{4em} p = a_n$  \n",
    "$\\hspace{4em} \\text{for } i \\text{ from } n - 1 \\text{ to } 0$  \n",
    "$\\hspace{6em} p = p * x + a_i$  \n",
    "$\\hspace{4em} \\text{return } p$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*  \n",
    "\n",
    "*Base case:*  \n",
    "Suppose $P(x) = a_0$ is a polynomial of degree $n = 0$ and $A = \\{a_0\\}$. The `for` loop then doesn't do anything since in this case $n - 1 < 0$. The algorithm just returns $p = a_0$, which is correct.\n",
    "\n",
    "*General case*:  \n",
    "Suppose that the algorithm returns the correct result for polynomials up to degree $n - 1 \\geq 0$. Let $P(x) = a_nx^n + a_{n-1}x^{n-1} + \\ldots + a_1x + a_0$ be a polynomial of degree $n$, and $A = \\{a_n, \\ldots, a_0\\}$ is the vector of coefficients.\n",
    "\n",
    "\n",
    "The algorithm as stated is not recursive, but the trick is that it can be rewritten in a recursive way. We separate out the last iteration of the `for` loop to produce:\n",
    "\n",
    "$\\hspace{2em} function \\> \\text{horner}(\\,A,\\,x)$   \n",
    "$\\hspace{4em} p = a_n$  \n",
    "$\\hspace{4em} \\text{for } i \\text{ from } n - 1 \\text{ to } 1$  \n",
    "$\\hspace{6em} p = p * x + a_i$  \n",
    "$\\hspace{4em} p = p * x + a_0$  \n",
    "$\\hspace{4em} \\text{return } p$  \n",
    "\n",
    "Now observe that the first 3 lines of the function are identical to the original algorithm, except that we are leaving out the last coefficient. Therefore, if we let $B = \\{a_n, \\ldots, a_1\\}$ then this can be written as:\n",
    "\n",
    "$\\hspace{2em} function \\> \\text{horner}(\\,A,\\,x)$   \n",
    "$\\hspace{4em} p = \\text{horner}(\\,B,\\,x)$  \n",
    "$\\hspace{4em} p = p * x + a_0$  \n",
    "$\\hspace{4em} \\text{return } p$  \n",
    "\n",
    "Or even more succinctly as:\n",
    "\n",
    "$\\hspace{2em} function \\> \\text{horner}(\\,A,\\,x)$   \n",
    "$\\hspace{4em} \\text{return } \\text{horner}(\\,B,\\,x) * x + a_0$  \n",
    "\n",
    "(This rewrite works because of our assumption that $n > 0$; otherwise we would need to check this. In other words, to truly rewrite the algorithm using recursion we would need to check for basis cases.) By our induction hypothesis, $\\text{horner}(\\,B,\\,x)$ produces the correct result since $B$ represents a polynomial of degree $n-1$. Specifically, $\\text{horner}(\\,B,\\,x)$ correctly evaluates the polynomial $P_{-1}(x) = a_nx^{n-1} + a_{n-1}x^{n-2} + \\ldots + a_1$. \n",
    "\n",
    "And now we can directly check algebraically:\n",
    "\n",
    "$\\hspace{1em} \\text{horner}(\\,A,\\,x)$  \n",
    "$\\hspace{2em} = \\text{horner}(\\,B,\\,x) * x + a_0$  \n",
    "$\\hspace{2em} = \\left[a_nx^{n-1} + a_{n-1}x^{n-2} + \\ldots + a_1\\right] * x + a_0$  \n",
    "$\\hspace{2em} = a_nx^{n} + a_{n-1}x^{n-1} + \\ldots + a_1x + a_0$  \n",
    "$\\hspace{2em} = P(x)$  \n",
    "\n",
    "Therefore $\\text{horner}(\\,A,\\,x) = P(x)$, where by induction, $P$ can be a polynomial of any degree $n \\geq 0.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.9 [3]\n",
    "\n",
    "Prove the correctness of the following sorting algorithm.\n",
    "\n",
    "$\\hspace{2em} function \\text{ bubblesort } (\\,A : \\text{list}[1\\ldots n])$  \n",
    "$\\hspace{4em} \\text{var int } i,\\, j$  \n",
    "$\\hspace{4em} \\text{for } i \\text{ from } n \\text{ to } 1$  \n",
    "$\\hspace{6em} \\text{for } j \\text{ from } 1 \\text{ to }  i - 1$  \n",
    "$\\hspace{8em} \\text{if } (\\,A[j] > A[j + 1])$  \n",
    "$\\hspace{10em} \\text{swap the values of } A[j] \\text{ and } A[j + 1]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "First let's look at an example. Each line below shows the state of the list **after** the `i`th iteration. **Bold** numbers are those rightward of the `i`th position (inclusive).\n",
    "\n",
    "$\\hspace{2em} i = \\_\\_:$ (2, 4, 3, 5, 8, 10, 1, 9, 7, 6)  \n",
    "$\\hspace{2em} i =  10:$ (2, 3, 4, 5, 8, 1, 9, 7, 6, **10**)  \n",
    "$\\hspace{2em} i = \\_9:$ (2, 3, 4, 5, 1, 8, 7, 6, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_8:$ (2, 3, 4, 1, 5, 7, 6, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_7:$ (2, 3, 1, 4, 5, 6, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_6:$ (2, 1, 3, 4, 5, **6**, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_5:$ (1, 2, 3, 4, **5**, **6**, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_4:$ (1, 2, 3, **4**, **5**, **6**, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_3:$ (1, 2, **3**, **4**, **5**, **6**, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_2:$ (1, **2**, **3**, **4**, **5**, **6**, **7**, **8**, **9**, **10**)  \n",
    "$\\hspace{2em} i = \\_1:$ (**1**, **2**, **3**, **4**, **5**, **6**, **7**, **8**, **9**, **10**)  \n",
    "\n",
    "The key thing to notice is that the **bold** numbers, those to the right of the `i`th position, are in sorted order. Therefore when the `i` $=1$ iteration finishes, the list is guaranteed to be sorted.\n",
    "\n",
    "To start off, let's prove this fact: *after the *`i`*th iteration the element in the *`i`*th position is larger than or equal to all the elements to its left.* The `i`th iteration operates on the subset of elements from $j=1$ to $j = i-1$. As `j` is incremented, at some point $A[j]$ will refer to the subset's largest element. At that point, $A[j]$ will be greater than $A[j+1]$, and so these will be swapped. Then when `j` is incremented, $A[j]$ is now still equal to that largest value. In this manner the largest element will be propogated to the end of the subset. If the largest element is not unique, then these elements will be propogated right until they meet an equal element. In this case, they won't be swapped, but since they are equal, the value of $A[j]$ still won't change when `j` is incremented and so will still point to the largest value in the subset. And so the end result is the same, the last element of the subset (including position `i`) is now the (possibly not unique) largest element of the subset.\n",
    "\n",
    "Another fact is: *after the `i`th iteration, the element in position `i` won't move.* The next iteration only considers elements $1$ though $i-2$ because `i` will be incremented, and so on.\n",
    "\n",
    "A consequence of the 2 results above is: *after the `i`th iteration, the element in position `i` is smaller than or equal to all the elements to its right.* To prove this, let's suppose otherwise. Suppose that after the `i`th iteration, $A[i] > A[i+k]$ for some $k>0$. But after the (earlier) `i+k` iteration, $A[i+k]$ was larger than all elements to its left, and the element hasn't changed since. Furthermore, $A[i]$ must have been among those elements to the left of position `i+k`, for if it was to the right, an iteration would have already occurred referring to that position, freezing it in that spot, even though it is now located in positon `i`. Therefore, $A[i+k] > A[i]$, which constradicts our assumption, and the result is proved.\n",
    "\n",
    "Putting the above 3 results together, after the `i`th iteration, the element in position `i` is larger than or equal to all the elements to its left, is small than or equal to all the elements to its right, and won't move on later iterations. *So it is permanently in its correct sorted position.* Therefore after all $n$ iterations of `i`, every element is in its correct sorted position, and the list is sorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Induction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.10 [3]\n",
    "\n",
    "Prove that $\\sum_{i=1}^{n}i = n(n+1) \\,/\\, 2$ for $n \\geq 0$, by induction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "*Solution:*  \n",
    "\n",
    "*Base case:* $n=0$.  \n",
    "LHS: $\\sum_{i=1}^{n=0}i = 0$  \n",
    "RHS: $0(0+1)\\,/\\,2 = 0$  \n",
    "They are equal.\n",
    "\n",
    "\n",
    "*Base case:* $n=1$.  \n",
    "LHS: $\\sum_{i=1}^{n=1}i = 1$  \n",
    "RHS: $1(1+1)\\,/\\,2 = 2\\,/\\,2 = 1$  \n",
    "They are equal.\n",
    "\n",
    "*General case.*  \n",
    "$\\hspace{1em} \\sum_{i=1}^{n}i$  \n",
    "$\\hspace{2em} = n + \\sum_{i=1}^{n-1}i$  \n",
    "$\\hspace{2em} = n + \\frac{(n-1)(n-1+1)}{2}$  \n",
    "$\\hspace{2em} = n + \\frac{n(n-1)}{2}$  \n",
    "$\\hspace{2em} = \\frac{1}{2} \\cdot \\left[2n + n(n-1)\\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{2} \\cdot \\left[2n + n^2-n\\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{2} \\cdot \\left[n^2+n\\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{2} \\cdot \\left[n(n+1)\\right]$  \n",
    "$\\hspace{2em} = \\frac{n(n+1)}{2}$  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.11 [3]\n",
    "\n",
    "Prove that $\\sum_{i=1}^{n}i^2 = n(n+1)(2n+1) \\,/\\, 6$ for $n \\geq 0$, by induction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 0$.  \n",
    "Both sides trivially reduce to 0.\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $\\sum_{i=1}^{n=1}i^2 = 1^2 = 1$  \n",
    "RHS: $1(1+1)(2+1)\\,/\\,6 = 2(3)\\,/\\,6 = 6 \\,/\\,6 = 1$  \n",
    "They are equal.\n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\sum_{i=1}^{n}i^2$  \n",
    "$\\hspace{2em} = n^2 + \\sum_{i=1}^{n-1}i^2$  \n",
    "$\\hspace{2em} = n^2 + \\frac{(n-1)(n)(2(n-1)+1)}{6}$  \n",
    "$\\hspace{2em} = n^2 + \\frac{n(n-1)(2n-1)}{6}$  \n",
    "$\\hspace{2em} = \\frac{1}{6} \\cdot \\left[ 6n^2 + \\left(n^2-n\\right)\\left(2n-1\\right) \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{6} \\cdot \\left[ 6n^2 + 2n^3 -n^2 -2n^2 + n \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{6} \\cdot \\left[ 2n^3 + 3n^2 + n \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{6} \\cdot \\left[ n\\left(2n^2 + 3n + 1\\right) \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{6} \\cdot \\left[ n\\left(2n+1\\right)\\left(n+1\\right) \\right]$  \n",
    "$\\hspace{2em} = \\frac{n\\left(2n+1\\right)\\left(n+1\\right)}{6}$  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.12 [3]\n",
    "\n",
    "Prove that $\\sum_{i=1}^{n}i^3 = n^2(n+1)^2 \\,/\\, 4$ for $n \\geq 0$, by induction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 0$.  \n",
    "Both sides trivially reduce to 0.\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $\\sum_{i=1}^{n=1}i^3 = 1^3 = 1$  \n",
    "RHS: $1^2(1+1)^2 \\,/\\, 4 = 2^2\\,/\\,4 = 4\\,/\\,4 = 1$  \n",
    "They are equal.\n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\sum_{i=1}^{n}i^3$  \n",
    "$\\hspace{2em} = n^3 + \\sum_{i=1}^{n-1}i^3$  \n",
    "$\\hspace{2em} = n^3 + \\frac{(n-1)^2n^2}{4}$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[4n^3 + n^2(n-1)^2 \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[4n^3 + n^2\\left(n^2 - 2n + 1\\right) \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[4n^3 + n^4 - 2n^3 + n^2 \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[n^4 + 2n^3 + n^2 \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[ n^2\\left(n^2 + 2n + 1\\right) \\right]$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[ n^2(n+1)(n+1) \\right]$  \n",
    "$\\hspace{2em} = \\frac{n^2(n+1)^2}{4}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.13 [3]\n",
    "\n",
    "Prove that $$\\sum_{i=1}^{n}i(i+1)(i+2) = n(n+1)(n+2)(n+3) \\,/\\, 4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 0$.  \n",
    "Both sides trivially reduce to 0.\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $\\sum_{i=1}^{1}i(i+1)(i+2) = 1(1+1)(1+2) = 2(3) = 6$  \n",
    "RHS: $1(1+1)(1+2)(1+3) \\,/\\,4 = 2(3)(4)\\,/\\,4 = 6$  \n",
    "They are equal.\n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\sum_{i=1}^{n}i(i+1)(i+2)$  \n",
    "$\\hspace{2em} = n(n+1)(n+2) + \\sum_{i=1}^{n-1}i(i+1)(i+2)$  \n",
    "$\\hspace{2em} = n(n+1)(n+2) + \\frac{(n-1)(n)(n+1)(n+2)}{4}$  \n",
    "$\\hspace{2em} = \\frac{1}{4} \\cdot \\left[4n(n+1)(n+2) + (n-1)(n)(n+1)(n+2)\\right]$  \n",
    "$\\hspace{2em} = \\frac{n(n+1)(n+2)}{4} \\cdot \\left[4 + (n-1)\\right]$  \n",
    "$\\hspace{2em} = \\frac{n(n+1)(n+2)(n+3)}{4}$  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.14 [5]\n",
    "\n",
    "Prove by induction on $n \\geq 1$ that for every $a \\neq 1$,\n",
    "$$\\sum_{i=0}^na^i = \\frac{a^{n+1} - 1}{a-1}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $\\sum_{i=0}^{1}a^i = a^0 + a^1 = a + 1$  \n",
    "RHS: $\\frac{a^{1+1} - 1}{a-1} = \\frac{a^2 - 1}{a-1} = \\frac{(a - 1)(a + 1)}{a-1} = a + 1$  \n",
    "They are equal.\n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\sum_{i=0}^na^i$  \n",
    "$\\hspace{2em} = a^n + \\sum_{i=0}^{n-1}a^i$  \n",
    "$\\hspace{2em} = a^n + \\frac{a^n - 1}{a-1}$  \n",
    "$\\hspace{2em} = \\frac{a^n(a-1)}{a-1} + \\frac{a^n - 1}{a-1}$  \n",
    "$\\hspace{2em} = \\frac{a^{n+1}-a^n}{a-1} + \\frac{a^n - 1}{a-1}$  \n",
    "$\\hspace{2em} = \\frac{a^{n+1} - 1}{a-1}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.15 [3]\n",
    "\n",
    "Prove by induction that for $n \\geq 1$,\n",
    "$$\\sum_{i=0}^n\\frac{1}{i(i+1)} = \\frac{n}{n+1}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $\\sum_{i=0}^{1}\\frac{1}{1(1+1)} = \\frac{1}{2}$  \n",
    "RHS: $\\frac{1}{1+1} = \\frac{1}{2}$  \n",
    "They are equal.\n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\sum_{i=0}^n\\frac{1}{i(i+1)}$  \n",
    "$\\hspace{2em} = \\frac{1}{n(n+1)} + \\sum_{i=0}^{n-1}\\frac{1}{i(i+1)}$  \n",
    "$\\hspace{2em} = \\frac{1}{n(n+1)} + \\frac{n-1}{n}$  \n",
    "$\\hspace{2em} = \\frac{1}{n(n+1)} + \\frac{(n-1)(n+1)}{n(n+1)}$  \n",
    "$\\hspace{2em} = \\frac{1 + (n-1)(n+1)}{n(n+1)}$  \n",
    "$\\hspace{2em} = \\frac{1 + n^2 - 1}{n(n+1)}$  \n",
    "$\\hspace{2em} = \\frac{n^2}{n(n+1)}$  \n",
    "$\\hspace{2em} = \\frac{n}{n+1}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.16 [3]\n",
    "\n",
    "Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n \\geq 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "$n^3 + 2n = 1^3 + 2(1) = 1 + 2 = 3$  \n",
    "3 is divisible by 3.\n",
    "\n",
    "*General case:*  \n",
    "Let $f(n) = n^3 + 2n$, and suppose that for all positive integers $m<n$, $f(m)$ is divisible by 3. We wish to show $f(n)$ is also divisible by 3. We will do so by expressing $f(n)$ as $f(n) = f(n-1) + A$. Since $f(n-1)$ is divisible by 3 by our inductive hypothesis, if we can show that $A$ is also divisible by 3, then $f(n)$ must be also.\n",
    "\n",
    "$\\hspace{1em} A = f(n) - f(n-1)$  \n",
    "$\\hspace{2em} = \\left(n^3 + 2n\\right) - \\left[ (n-1)^3 + 2(n-1) \\right]$  \n",
    "$\\hspace{2em} = n^3 + 2n - \\left[ (n-1)\\left(n^2 - 2n + 1\\right)  \\right] - 2n + 2$  \n",
    "$\\hspace{2em} = n^3 + 2 - \\left[ n^3 - 2n^2 + n - n^2 + 2n - 1  \\right]$  \n",
    "$\\hspace{2em} = n^3 + 2 - n^3 + 2n^2 - n + n^2 - 2n + 1$  \n",
    "$\\hspace{2em} = 3 + 3n^2 - 3n$  \n",
    "$\\hspace{2em} = 3\\left(n^2 - n + 1\\right)$  \n",
    "\n",
    "Since $n$ is an integer, $n^2 - n + 1$ will also be an integer. And by multiplying by 3 we produce an integer that must be divisible by 3. By writing $A = 3\\left(n(n - 1) + 1\\right)$ and noting that $n\\geq1$, we see that $A\\geq3$. Therefore $A$ is a positive integer divisible by 3. \n",
    "\n",
    "Since both $A$ and $f(n-1)$ are both positive integers divisible by 3, their sum $f(n)$ must be as well.\n",
    "\n",
    "Note that this proof sort of generalized, or modified, the method of proof used in the previous 6 questions. In each of them we expressed the general case as\n",
    "\n",
    "$$General\\_case(n) = nth\\_term + General\\_case(n-1)$$\n",
    "\n",
    "and then applied our inductive hypothesis to $General\\_case(n-1)$ to produce something that could be algebraically combined with $nth\\_term$. In this case, there is no sum, so there is no \"$nth\\_term$\". And therefore it wasn't clear how to to express $n^3 + 2n$ in terms of a smaller general case, which is needed in order to use the inductive hypothesis. The solution was to just *solve* for the equivalent of the \"$nth\\_term$\". The reason why this worked is because in the earlier induction problems, the *point* of using the inductive hypothesis was to turn a summation (which is algebraically hard to deal with) into a nice compact expression. In this problem, the function $f$ was algebraically very simple. The inductive hypothesis was used to assure us of some property, in this case divisibility by 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.17 [3]\n",
    "\n",
    "Prove by induction that a tree with $n$ vertices has exactly $n-1$ edges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case: n = 1.*  \n",
    "A tree with $n=1$ vertices (a singel vertex) has no (0) edges, and $n-1 = 1-1 = 0$.\n",
    "\n",
    "*General case:*  \n",
    "Note that a tree can be created iteratively by starting with the root and iteritavely adding branches. But note that each time a branch are added, one edge and one point is added. This is because an edge is never created between two vertices that already exist. (As a consequence, trees have no enclosed areas.) So each addition adds one vertex and one edge, and the total number of *added* vertices is equal to the total number of *added* edges. When you account for the original root vertex, the tree has one more vertex than edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.18 [3]\n",
    "\n",
    "Prove by methematical induction that the sum of the cubes of the first $n$ positive integers is equal to the square of the sum of these integers, i.e.\n",
    "$$ \\sum_{i=1}^{n}i^3 = \\left(\\sum_{i=1}^{n}i\\right)^2 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*Base case:* $n=1$.  \n",
    "RHS: $1^3 = 1$  \n",
    "LHS: $1^2 = 1$  \n",
    "They are equal.  \n",
    "\n",
    "*General case:*  \n",
    "$\\hspace{1em} \\left(\\sum_{i=1}^{n}i\\right)^2$  \n",
    "$\\hspace{2em} = \\left(n + \\sum_{i=1}^{n-1}i\\right)^2$  \n",
    "$\\hspace{2em} = n^2 + 2n\\left(\\sum_{i=1}^{n-1}i\\right) + \\left(\\sum_{i=1}^{n-1}i\\right)^2$  \n",
    "$\\hspace{2em} \\stackrel{(1)}{=} n^2 + 2n\\left(\\frac{n(n-1)}{2}\\right) + \\sum_{i=1}^{n-1}i^3$  \n",
    "$\\hspace{2em} = n^2 + n^2(n-1) + \\sum_{i=1}^{n-1}i^3$  \n",
    "$\\hspace{2em} = n^2 + n^3 - n^2 + \\sum_{i=1}^{n-1}i^3$  \n",
    "$\\hspace{2em} = n^3 + \\sum_{i=1}^{n-1}i^3$  \n",
    "$\\hspace{2em} = \\sum_{i=1}^{n}i^3$  \n",
    "\n",
    "(1): The key step, here we use our inductive hypothesis on the third term, and on the second term we use the equality proved in problem 10: $\\sum_{i=1}^{n}i = n(n+1) \\,/\\, 2$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.19 [3]\n",
    "\n",
    "Do all the books you own total at least one million pages? How many total\n",
    "pages are stored in your school library?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Even if I owned 50 books and each was 1000 pages, that would still only be 50,000 pages, less than 10% of a million.  So I am very confident that all the books I own total less than a million pages.  \n",
    "\n",
    "My school's library (University of Pennsylvania) easily has over a million books, considering they are spread out over multiple libraries and even in an excess repository. Let's assume it contains 20 million books. On average, each may be 500 pages, for a total of 10 billion pages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.20 [3]\n",
    "\n",
    "How many words are there in this textbook?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The book is 730 pages long, plus 16 pages of front matters, for a total of 746, about 750 pages. There appears to be about 40 lines per page, but many pages have much less. So let's assume 30 lines per page and 15 words per line, both of which are generous.\n",
    "\n",
    "$750*40*15 = 450,000 \\text{ words}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.21 [3]\n",
    "\n",
    "How many hours are one million seconds? How many days? Answer these\n",
    "questions by doing all arithmetic in your head."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "1 million seconds is [divide by ~50 seconds/min] 20,000 minutes.  \n",
    "20,000 minutes is [divide by ~50 min/hour] 400 hours.  \n",
    "In both cases, the denominator 60 was estimated as 50. Therefore both are slightly larger than the true answers. Maybe 20%."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.22 [3]\n",
    "\n",
    "Estimate how many cities and towns there are in the United States."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "I know that the US is roughly 3000 miles wide, and maybe half that vertically. Town size will vary greately across the country, varying from maybe 1 square mile to maybe 100 square miles (think Alaska). For the continental US, let's say that the averge town is 20 square miles large.\n",
    "\n",
    "$3000 \\text{ (miles)} *1500\\text{ (miles)}\\,/\\,20\\text{ (sq. miles per town)} = 3000^2/40 = 9,000,000/40 = 225,000 \\text{ towns in the continental US}$\n",
    "\n",
    "Let's say that Hawaii adds a negligible amount of towns. Alaska, on the other hand, is odd, both for its size and its sparsity. I guess that it is 20-30% the size of the continental US, but likely has the lowest town density. Let's say it is 1/4 the size of the continental US, with an average town size of 100 square miles.\n",
    "\n",
    "$3000 \\text{ (miles)} *1500\\text{ (miles)} * (1/4)\\,/\\,100\\text{ (sq. miles per town)} = 3000^2/800 = 9,000,000/800 = 11,250 \\text{ towns in Alaska}$\n",
    "\n",
    "For a total of $225,000 + 11,250 = 236250\\text{ towns in the US.}$\n",
    "\n",
    "As a different estimate, let's say that the average town has 10,000 people in it, and the population of the U.S. is about 360 million.\n",
    "\n",
    "$360,000,000 \\,/\\, 10,000 = 36,000 \\text{ towns in the US.}$\n",
    "\n",
    "The second line of reasoning seems more reasonable, so let's put our final estimate at 80,000 towns.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.23 [3]\n",
    "\n",
    "Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "No idea. Let's say the Mississippi is 5 miles wide and that water flows out at a rate of 1 mile every 20 minutes. We also need the average depth at the outlet, let's say a quarter of a mile.\n",
    "\n",
    "Therefore the cubic rate of flow is:\n",
    "\n",
    "$5 \\text{ (miles wide)} * 0.25 \\text{ (miles deep)} * 1 \\text{ (mile long)} \\,/\\, 20 \\text{ (minutes)}$  \n",
    "$ = 1.25 \\text{ cubic miles every 20 minutes}$  \n",
    "$ = 3.75 \\text{ cubic miles every hour}$  \n",
    "$ = 90 \\text{ cubic miles every day}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.24 [3]\n",
    "\n",
    "Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds (millionths of a second)? Does your RAM memory access a word in more or less than a microsecond? How many instructions can your CPU execute in one year if the machine is left running all the time?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Disk drive access time is normally measured in milliseconds.\n",
    "\n",
    "RAM access times are usually between 50 and 150 nanoseconds (per word).\n",
    "\n",
    "Taken from the Wikipedia page [Instructions per second](http://www.wikiwand.com/en/Instructions_per_second), the most recent Intel processor \"Intel Core i7 5960X\" performs 238,310 MIPS (million instructions per second).\n",
    "\n",
    "$\\frac{238,000 \\text{ million instructions}}{1 \\text{second}} \\cdot \\frac{10^6}{1 \\text{ million}} \\cdot \\frac{60 \\text{ seconds}}{1 \\text{ minute}} \\cdot \\frac{60 \\text{ minutes}}{1 \\text{ hour}} \\cdot \\frac{24 \\text{ hours}}{1 \\text{ day}} \\cdot \\frac{365 \\text{ days}}{1 \\text{ year}} = 7.5 \\times 10^{18} \\frac{\\text{instructions}}{\\text{second}}$\n",
    "\n",
    "which is 7.5 billion billions of instructions!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 1.25 [4]\n",
    "\n",
    "A sorting algorithm takes 1 second to sort 1,000 items on your local machine. How long will it take to sort 10,000 items. . .  \n",
    "$\\hspace{1em}$ a. if you believe that the algorithm takes time proportional to $n^2$, and  \n",
    "$\\hspace{1em}$ b. if you believe that the algorithm takes time roughly proportional to $n \\log{n}$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "*(a):*  \n",
    "$t(n) = a\\cdot n^2$ for some constant $a$.\n",
    "\n",
    "$\\frac{t(10,000)}{t(1,000)} = \\frac{a\\cdot (10^4)^2}{a\\cdot (10^3)^2} = \\frac{10^8}{10^6} = 100$  \n",
    "\n",
    "So $t(10,000) = 100 \\text{ seconds}$.\n",
    "\n",
    "*(b):*  \n",
    "$t(n) = a\\cdot n\\log{n}$ for some constant $a$.\n",
    "\n",
    "$\\frac{t(10,000)}{t(1,000)} = \\frac{a\\cdot (10^4)\\log{(10^4)}}{a\\cdot (10^3)\\log{(10^3)}} = 10 \\cdot\\frac{\\log{(10^4)}}{\\log{(10^3)}} \\stackrel{*}{=} 10 \\cdot \\frac{4}{3} = 13.\\bar{3}$  \n",
    "\n",
    "(*where we made the assumption that $\\log$ is base 10, rather than base $e$ or base $2$). So $t(10,000) = 13.\\bar{3} \\text{ seconds}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation Projects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.26 [5] Unfinished\n",
    "\n",
    "Implement the two TSP heuristics of Section 1.1 (page 5). Which of them gives better-quality solutions in practice? Can you devise a heuristic that works better than both of them?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.8863495173726745\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "\n",
    "P = [(1,2),(2,3),(3,1)]\n",
    "\n",
    "def distance(a, b):\n",
    "    xdist = a[0] - b[0]\n",
    "    ydist = a[1] - b[1]\n",
    "    return (xdist**2 + ydist**2)**.5\n",
    "    \n",
    "def NearestNeighbor(P):\n",
    "    ## P is an iterable of tuples.\n",
    "    unvisited = set(P) # List of points not yet visited\n",
    "    n = len(unvisited)       ## Number of points\n",
    "    distances = list()\n",
    "    \n",
    "    ## Initialize with a random point\n",
    "    p0, = random.sample(unvisited, 1) ## comma needed for unpacking\n",
    "    pstart = p0 ## Will need to return to this point later\n",
    "    unvisited.remove(p0)\n",
    "    \n",
    "    i = 0\n",
    "    while len(unvisited) > 0:\n",
    "        p1,  = random.sample(unvisited, 1)\n",
    "        unvisited.remove(p1)\n",
    "        distances.append(distance(p0, p1))\n",
    "        p0 = p1\n",
    "        i = i + 1\n",
    "        \n",
    "    distances.append(distance(pstart, p1))\n",
    "    return sum(distances)\n",
    "        \n",
    "print(NearestNeighbor(P))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.27 [5] Unfinished\n",
    "\n",
    "Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.6 (page 23). Write a program to find good ticket sets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.28 [5]\n",
    "\n",
    "Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.\n",
    "\n",
    "*Solution:*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a simple solution. If you are dividing $x$ by $y$, then repeatedly subtract y from x until you reach 0 or a negative number. The number of subtractions is your answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 10 µs, sys: 0 ns, total: 10 µs\n",
      "Wall time: 11.9 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def divide1(x, y):\n",
    "    result = 0\n",
    "    while (x - y) >= 0:\n",
    "        x -= y\n",
    "        result += 1\n",
    "    return result\n",
    "\n",
    "%time divide1(101, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The problem is that when $x\\,/\\,y$ is large, a large number of subtractions must take place. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 899 ms, sys: 7.21 ms, total: 906 ms\n",
      "Wall time: 915 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5000000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time divide1(10**7, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way to speed this up is to subtract $2y$ (y + y) each time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 454 ms, sys: 4.07 ms, total: 458 ms\n",
      "Wall time: 460 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5000000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def divide2(x, y):\n",
    "    result = 0\n",
    "    y2 = y + y\n",
    "    while (x - y2) >= 0:\n",
    "        x -= y2\n",
    "        result += 2\n",
    "        \n",
    "    while (x - y) >= 0:\n",
    "        x -= y\n",
    "        result += 1\n",
    "        \n",
    "    return result\n",
    "\n",
    "%time divide2(10**7, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, $x$ can still become large enough such that this too is slow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4.76 s, sys: 73.8 ms, total: 4.83 s\n",
      "Wall time: 4.98 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50000000"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time divide2(10**8, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Doubling $y$ only saves us about half the time. The natural extention then is to continually double $y$ and subtract it from $x$ until the result would be $0$ or below. At this point, half $y$ repeatedly until you can subtract it again. Of course, we aren't allowed to divide by 2, so the sequence of y's used must be stored in a list. A second list, \"factor\", records how much each enlarged \"y\" is worth in terms of the original y."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def divide3(x, y):\n",
    "    y = [y]\n",
    "    result = 0\n",
    "    factor = [1]\n",
    "    while True:\n",
    "        if (x - y[-1]) >= 0:\n",
    "            x -= y[-1]\n",
    "            result += factor[-1]\n",
    "            \n",
    "        ## Try doubling y.\n",
    "        if (x - y[-1] - y[-1]) >= 0:\n",
    "            y.append(y[-1] + y[-1])\n",
    "            factor.append(factor[-1] + factor[-1])\n",
    "            \n",
    "        ## If y can't be doubled, check and see\n",
    "        ## if it can just stay the same.\n",
    "        elif (x - y[-1]) >= 0:\n",
    "            continue\n",
    "        ## If not, divide y by 2\n",
    "        ## by returning to the previous y.\n",
    "        ## If y is len 1, break.\n",
    "        else:\n",
    "            if len(y) == 1:\n",
    "                break\n",
    "            else:\n",
    "                y.pop()\n",
    "                factor.pop()\n",
    "                \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 113 µs, sys: 1 µs, total: 114 µs\n",
      "Wall time: 123 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50000000"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time divide3(10**8, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 12.2 ms, sys: 1.32 ms, total: 13.5 ms\n",
      "Wall time: 14 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time divide3(10**1000, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "This scales much much better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.29 [5]\n",
    "\n",
    "There are 25 horses. At most, 5 horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "It is assumed that to compare horses they must be in the same race, rather than just comparing their times from different races. We need to assure that the fastest horse has raced with the second fastest, and that the second fastest has raced with the third fastest.\n",
    "\n",
    "A simplistic way of viewing the problem is that for every race we run, we can eliminate the bottom two horses. We need to eliminate a total of 22 horses, indicating we need to run 11 races. This can serve as an upper bound.\n",
    "\n",
    "To address the problem more systematically, suppose we initially run all 25 horses in 5 races. The bottom 2 horses from each race can be eliminated, leaving us with 15 horses. These can all be run together in another 3 races. Eliminating the bottom 2 horses from each race, we are reduced to 9 horses. We can pick 5 of these 9, race them, and eliminate the bottom 2, leaving 7 horses. We can do this again, leaving 5. One final race will determine the top 3.\n",
    "\n",
    "This procedure also takes 11 races.\n",
    "\n",
    "There is a huge inefficiency in this procedure however, which is that outcomes from previous races are never used later on.\n",
    "\n",
    "Perhaps we can do better.\n",
    "\n",
    "Here is a drawing of a better racing scheme that only takes 9 races; there are 3 rounds, and only circled horses continue to the next.\n",
    "\n",
    "![Hallock Fig 1-1](Figures/Hallock_Fig_1-1.jpg)\n",
    "\n",
    "After running all 25 horses in 5 races, eliminate the 10 horses that came in 4th or 5th place, and then run the 5 3rd place horses against each other. Consider the winner from that race. We already know of 2 horses that are faster, namely, the horses that beat it in the first round. Therefore at best, this horse is overall the 3rd fastest; the 4 horses it beat in round 2 cannot be in the overall top 3, and so all 4 can be eliminated. This leaves 11 horses.\n",
    "\n",
    "Now race the 5 horses that each came in 2nd place in round 1, and consider the 2nd place horse in that race. How many horses do we know of that are faster? The horse that beat it in round 1, the horse that beat it in round 2, and the horse that beat that horse in round 1 are all faster. Therefore this horse is at best overall 4th fastest. So we can eliminate all but the winner of this race, leaving us with 7 horses.\n",
    "\n",
    "Now race the 5 horses that came in 1st place in round 1. We eliminate the bottom 2, leaving us with a total of 5 horses. These 5 can then be raced together, identifiying the 3 overall best horses.\n",
    "\n",
    "This procedure took 3 rounds of 5, 3, and 1 races for a total of 9 races."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.30 [3]\n",
    "\n",
    "How many piano tuners are there in the entire world?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Let's say that 1 in a hundred thousand people within a typical large Western city is a piano tuner. NYC has 8 million people, so there are 80 piano tuners. There may be more. Outside of a major city, would this number be more or less? More because people are more spread out, so you need tuners to cover every body. Less because smaller towns won't have as active a musical scene, especially a professional one.\n",
    "\n",
    "So let's say 1 in 100,000 for the West, 1 in 500,000 for all of Asia, and 1 in 1,000,000 for the rest of the world. The whole world is 7 billion people. Let's say 1 billion is the West, 4 billion is Asia, 2 billion is the rest.\n",
    "\n",
    "That comes out to 10,000 in the West, 5,000 in Asia, and 1,000 in the rest of the world, for a total of 16,000 piano tuners."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.31 [3]\n",
    "\n",
    "How many gas stations are there in the United States?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The population of the US is roughly 360 million. Let's say there is 1 gas station for every 100-1000 people. That puts the number of gas stations between 360,000 and 3,600,000. Let's say 500,000."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.32 [3]\n",
    "\n",
    "How much does the ice in a hockey rink weigh?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Water weights roughly 1 g per mL, which is a cubic centimeter. Let's say that an ice hockey rink is a 100 meters long and 40 wide, which comes to 4000 square meters, or 40,000,000 square centimeters. Let's also assume that the rink is 5 centimeters deep, amounting to a total of 200,000,000 cubic centimeters, and therefore 200,000,000 grams, or 200,000 kilograms. One issue though is that ice has a greater volume than water. So let's take 20 percent off, for a result of 160,000 kilograms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.33 [3]\n",
    "\n",
    "How many miles of road are there in the United States?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The US is roughly 3,000 miles wide and 1,500 tall. If there were horizontal roads stretching from coast to coast, spaced vertically 1 mile apart, they would total $3*1.5*1,000*1,000 = 4.5*1,000,000 = 4,500,000 \\text{ miles}$. A similar striping of vertical roads would be the same, for a total of 9 million miles. There are many places where this road density of 2 road miles (1 vertical, 1 horizontal) per square mile will be way off. Cities will have a much higher road density, and rural areas will have a much lower road density. I would guess that most of the US is rural, with much lower road densities. Also, Alaska is huge, but very sparse. Let's revise or estimate down to 20%: 1,800,000 miles of road in the U.S."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.34 [3]\n",
    "\n",
    "On average, how many times would you have to flip open the Manhattan phone\n",
    "book at random in order to find a specific name?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "*Solution:*\n",
    "\n",
    "Let's say there are 2 million people who live in Manhattan, and that a phonebook page has 100 names on it (including both sides).\n",
    "\n",
    "$2,000,000 \\text{ (people)} \\div \\frac{100 \\text{ (people)}}{1\\text{ (page)}} = 20,000 \\text{ pages}$\n",
    "\n",
    "How many times must I randomly open a 20,000 page book before landing on a particular page. A crude answer is 10,000 times.\n",
    "\n",
    "Or, what is the expected value of the number of times $n$ I must randomly sample a number from 1 through 20,000 with replacement before I draw a particular number $x$. The probability of drawing a particular number $x$ on the first draw is $1 \\,/\\, 20,000 = 0.00005$. The probability of drawing $x$ on the second draw is $(19,999 \\,/\\, 20,000)*(1 \\,/\\, 20,000) = .0000499$, where we account for NOT drawing $x$ on the first draw, and then drawing it on the second. So the probability of drawing $x$ within the first 2 draws is the sum of these two.\n",
    "\n",
    "Therefore, with $p = 1\\,/\\,20,000$, the probability that the given number is drawn in the first $n$ draws is\n",
    "$$P = \\sum_{m=1}^n(1-p)^{m-1} \\cdot p$$\n",
    "$$= p \\cdot \\sum_{m=1}^n(1-p)^{m-1} $$\n",
    "$$= p \\cdot \\sum_{m=0}^{n-1}(1-p)^{m}$$\n",
    "$$\\stackrel{(*)}{=} p \\cdot \\frac{(1-p)^{n} - 1}{1 - p - 1}$$\n",
    "$$= 1 - (1-p)^{n}$$\n",
    "\n",
    "($*$) where we use the expression for a partial geometric sum proved in problem 1.14. We set this equal to 0.5 (at which point it becomes more likely to have landed on the page than not): $0.5 = 1 - (1-p)^n$, rewriten as $0.5 = (1 - p)^n = 0.99995^n$, so $n = \\log_{0.99995} 0.5 = 13,862.6$, which rounds up to 13,863 times.\n",
    "\n",
    "You must open the Manhattan phonebook 13,863 times before it is likely that you have found a specfic name. The crude estimate of 10,000 was actually not too far off."
   ]
  }
 ],
 "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
}