Chapter 4 - Sorting and Searching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 4: Sorting and Searching (Completed 12/46: 26%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applications of Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 [3]\n",
    "\n",
    "The Grinch is given the job of partitioning $2n$ players into two teams of $n$ players each. Each player has a numerical rating that measures how good he/she is at the game. He seeks to divide the players as *unfairly* as possible, so as to create the biggest possible talent imbalance between team A and team B. Show how the Grinch can do the job in $O(n \\log n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Have the players stand in a line and sort them. This presumably can be done in $O(n\\log n)$ time although I imagine doing quicksort, mergesort or heapsort on a line of 100 people would be quite difficult; distribution sort might work if we know the ratings are close to uniformly distributed. Then put the first $n \\, / \\, 2$ players on one team and the other $n\\, / \\, 2$ players on the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 [3]\n",
    "\n",
    "For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, $S = \\{6, 13, 19, 3, 8\\}$, $19 − 3$ maximizes the difference, while $8 − 6$ minimizes the difference.\n",
    "\n",
    "(a) Let $S$ be an unsorted array of $n$ integers. Give an algorithm that finds the pair $x, y \\in S$ that maximizes $|x−y|$. Your algorithm must run in $O(n)$ worst-case time.\n",
    "\n",
    "(b) Let $S$ be a sorted array of $n$ integers. Give an algorithm that finds the pair $x, y \\in S$ that maximizes $|x − y|$. Your algorithm must run in $O(1)$ worst-case time.\n",
    "\n",
    "(c) Let $S$ be an unsorted array of $n$ integers. Give an algorithm that finds the pair $x, y \\in S$ that minimizes $|x − y|$, for $x = y$. Your algorithm must run in $O(n \\log n)$ worst-case time.\n",
    "\n",
    "(d) Let $S$ be a sorted array of $n$ integers. Give an algorithm that finds the pair $x, y \\in S$ that minimizes $|x − y|$, for $x = y$. Your algorithm must run in $O(n)$ worst-case time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):** The pair of values that will maximize $|x - y|$ will be the largest and smallest values in $S$. To find them, perform a linear search for each. Or, combine them both into one linear search by tracking both the minimum and maximum values seen so far."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 259,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min = 3\n",
      "max = 19\n",
      "difference = 16\n"
     ]
    }
   ],
   "source": [
    "unsorted = [6, 13, 19, 3, 8]\n",
    "sorted_S = [3, 6, 8, 13, 19]\n",
    "\n",
    "def max_diff_unsorted(S):\n",
    "    min = S[0]\n",
    "    max = S[0]\n",
    "    for i, _ in enumerate(S):\n",
    "        if S[i] > max:\n",
    "            max = S[i]\n",
    "        if S[i] < min:\n",
    "            min = S[i]\n",
    "    print(\"min = %s\" % min)\n",
    "    print(\"max = %s\" % max)\n",
    "    print(\"difference = %s\" % (max-min))\n",
    "\n",
    "max_diff_unsorted(unsorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b):** Once again, the pair of values that will maximize $|x - y|$ will be the largest and smallest values in $S$. Since S is sorted, these will be the first and last values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 260,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min = 3\n",
      "max = 19\n",
      "difference = 16\n"
     ]
    }
   ],
   "source": [
    "def max_diff_sorted(S):\n",
    "    min = S[0]\n",
    "    max = S[-1]\n",
    "    \n",
    "    print(\"min = %s\" % min)\n",
    "    print(\"max = %s\" % max)\n",
    "    print(\"difference = %s\" % (max-min))\n",
    "    \n",
    "max_diff_sorted(sorted_S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(c):** The pair of values that minimize $|x-y|$ can be any $x$ and $y$ in $S$, not simply the largest or smallest. However, they will be adjacent if $S$ is sorted, since if there was an intermediate point, the distance to that point must be smaller: $S[i+2] - S[i] $ $= \\left[ S[i+2] - S[i+1] \\right] + \\left[ S[i+1] - S[i] \\right] $ $\\geq \\left[ S[i+1] - S[i] \\right]$ since $S[i+2] - S[i+1] \\geq 0$. We can sort $S$ in $O(n \\log n)$ time, and then scan through the sorted set calculating $|x-y|$ for each adjacent pair, finding the minimum. Since $n \\log n > n$, the sum of these two components will be $O(n \\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 261,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum difference is between 6 and 8, which is 2.\n"
     ]
    }
   ],
   "source": [
    "def min_diff_unsorted(S):\n",
    "    S = sorted(S)\n",
    "    j = 0\n",
    "    k = 1\n",
    "    diff = S[1] - S[0]\n",
    "    \n",
    "    for i in range(len(S) - 1):\n",
    "        if (S[i+1] - S[i]) < diff:\n",
    "            j = i\n",
    "            k = i + 1\n",
    "            diff = S[k] - S[j]\n",
    "    \n",
    "    print(\"Minimum difference is between %s and %s, which is %s.\" % (S[j], S[k], diff))\n",
    "\n",
    "min_diff_unsorted(unsorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(d):** Since $S$ is already sorted, by the same reasoning of part **(c)** we know know that the pair that minimizes $|x-y|$ will be adjacent. Therefore we can reuse most of the previous solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 262,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum difference is between 6 and 8, which is 2.\n"
     ]
    }
   ],
   "source": [
    "def min_diff_sorted(S):\n",
    "    S = sorted(S)\n",
    "    j = 0\n",
    "    k = 1\n",
    "    diff = S[1] - S[0]\n",
    "    \n",
    "    for i in range(len(S) - 1):\n",
    "        if (S[i+1] - S[i]) < diff:\n",
    "            j = i\n",
    "            k = i + 1\n",
    "            diff = S[k] - S[j]\n",
    "    \n",
    "    print(\"Minimum difference is between %s and %s, which is %s.\" % (S[j], S[k], diff))\n",
    "\n",
    "min_diff_unsorted(sorted_S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6 [3]\n",
    "\n",
    "Given two sets $S_1$ and $S_2$ (each of size $n$), and a number $x$, describe an $O(n \\log n)$ algorithm for finding whether there exists a pair of elements, one from $S_1$ and one from $S_2$, that add up to $x$. (For partial credit, give a $\\Theta(n^2)$ algorithm for this problem.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Solution:$\n",
    "\n",
    "A $\\Theta(n^2)$ algorithm would be to construct the matrix $M[i,j] = S_1[i] + S_2[j]$ of pair-wise sums for all possible pairs, where element $(i,j)$ is the sum of element $i$ from $S_1$ and element $j$ from $S_2$. After constructing the matrix, search it looking for $x$. Both the construction and search are $\\Theta(n^2)$.\n",
    "\n",
    "For an $O(n \\log n)$ algorithm, first sort both $S_1$ and $S_2$ in $O(n \\log n)$ time. We can now take advantage of the sortedness property to construct a linear-time algorithm for finding a pair of values that sum to $x$ if such a pair exists.\n",
    "\n",
    "We maintain two pointers, $i=1$ that will increment along $S_1$, and $j=n$ that will decrement along $S_2$. For each $(i,j)$ we calculate $S_1[i] + S_2[j]$ and test if it is less than, equal to, or greater than $x$. If it's equal, then we found such a pair and we are done. If the sum is too large, we can decrement $j$. Since the sets are sorted, we know that $S[j-1] \\leq S[j]$. Therefore decrementing $j$ can only maintain or decrease the sum. Similarly, incrementing $i$ can only maintain or increase the sum, which we do if the sum is too small.\n",
    "\n",
    "This procedure will be $O(n)$. Specifically, the pointers $i$ and $j$ must each traverse at most $n$ different numbers, and each iteration of the inner loop moves one of these pointers one number ahead. If no pair has been found, each pointer traversed $n$ numbers, and each time at most 3 different comparisons were made (sum equal to x, less than x, greater than x), 5 different comparisons if you include the boundary checks on the `while` loop.\n",
    "\n",
    "Below we prove that his works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_to_x(S1, S2, x):\n",
    "    n = len(S1)\n",
    "    i = 0\n",
    "    j = n - 1\n",
    "    \n",
    "    S1.sort()\n",
    "    S2.sort()\n",
    "    \n",
    "    while ((i <= n - 1) and (j >= 0)):\n",
    "        sum = S1[i] + S2[j]\n",
    "        \n",
    "        if sum == x:\n",
    "            return (S1[i], S2[j])\n",
    "        if sum < x:\n",
    "            i += 1\n",
    "        if sum > x:\n",
    "            j -= 1\n",
    "            \n",
    "    return (-1,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 330,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TESTS (presorted for clarity)\n",
      "Odd: (9, 6) = 15\n",
      "Odd, no such pair: (-1, -1) = None\n",
      "Even: (5, 10) = 15\n",
      "Even, no such pair: (-1, -1) = None\n",
      "First pair: (1, 10) = 11\n",
      "Last pair: (20, 2) = 22\n",
      "Size 1: (1, 2) = 3\n",
      "Size 1, too large: (-1, -1) = None\n",
      "Size 1, too small: (-1, -1) = None\n"
     ]
    }
   ],
   "source": [
    "print(\"TESTS (presorted for clarity)\")\n",
    "    \n",
    "print(\"Odd:\",\n",
    "sum_to_x([1, 3, 5, 7, 9],\n",
    "         [2, 3, 4, 5, 6],\n",
    "         15), \"= 15\")\n",
    "print(\"Odd, no such pair:\",\n",
    "sum_to_x([1, 3, 5, 7, 9],\n",
    "         [2, 3, 4, 5, 6],\n",
    "         16), \"= None\")\n",
    "print(\"Even:\",\n",
    "sum_to_x([1, 3, 5, 7, 9, 10],\n",
    "         [2, 3, 4, 5, 6, 10],\n",
    "         15), \"= 15\")\n",
    "print(\"Even, no such pair:\",\n",
    "sum_to_x([1, 3, 5, 7, 9, 10],\n",
    "         [2, 3, 4, 5, 6, 10],\n",
    "         2), \"= None\")\n",
    "print(\"First pair:\", \n",
    "sum_to_x([1, 3, 5, 7, 9, 10],\n",
    "         [2, 3, 4, 5, 6, 10],\n",
    "         11), \"= 11\")\n",
    "print(\"Last pair:\",\n",
    "sum_to_x([1, 3, 5, 7, 9, 20],\n",
    "         [2, 3, 4, 5, 6, 10],\n",
    "         22), \"= 22\")\n",
    "print(\"Size 1:\", \n",
    "sum_to_x([1],\n",
    "         [2],\n",
    "         3), \"= 3\")\n",
    "print(\"Size 1, too large:\",\n",
    "sum_to_x([1],\n",
    "         [2],\n",
    "         1), \"= None\")\n",
    "print(\"Size 1, too small:\",\n",
    "sum_to_x([1],\n",
    "         [2],\n",
    "         4), \"= None\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will prove that this always produces the correct result by contradiction. Suppose that there was a pair of indices $k, l$ such that $S_1[k] + S_2[l] = x$, but that our algorithm didn't find them. (If more than such a pair exist, then $k,l$ are the first such pair.) This means that $i$ reached the end of $S_1$ and $j$ reached the beginning of $S_2$, somehow passing over the correct pair. Suppose that $k$ was passed over by $i$ before $l$ was passed over by $j$. Therefore at that point when $i=k$, the sum was $S_1[k] + S_2[j]$, which we know satisfies $S_1[k] + S_2[j] > S_1[k] + S_2[l] = x$ since $j>l$ and $S_2$ is sorted. Since the sum is greater than $x$, $j$ would be decremented until the sum was equal to $x$ or less than $x$. But $sum > x$ will continue to hold for all $j>l$, which means that $j$ will be incremented until it reaches $l$, at which point the sum will be $x$ and the algorithm will have correctly found the pair $k,l$. An identical argument applies in the case when $j$ passes over $l$ before $i$ passes over $k$.\n",
    "\n",
    "Therefore if such a pair exists, the algorithm will find it. The algorithm cannot return an incorrect pair, since it first checks if the numbers sum to $x$. If no pair exists, the pointers will both reach the end and the algorithm will terminate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.8 [4]\n",
    "\n",
    "Given a set of $S$ containing $n$ real numbers, and a real number $x$. We seek an algorithm to determine whether two elements of $S$ exist whose sum is exactly $x$.\n",
    "\n",
    "(a): Assume that $S$ is unsorted. Give an $O(n \\log n)$ algorithm for the problem.  \n",
    "(b): Assume that $S$ is sorted. Give an $O(n)$ algorithm for the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "This problem is almost identical to problem 4.6, except here there is only one set of numbers and they do not have to be integers.\n",
    "\n",
    "**(a):**\n",
    "\n",
    "First sort $S$, which will be $O(n \\log n)$. Then apply the algorithm described in 4.6 with both $S_1 = S$ and $S_2 = S$. Namely, set $i=0$ and $j=n-1$, and calculate S[i] + S[j]. If it equals $x$, you found a pair and you are done. If it's too small, increment $i$; if it's too big, decrement $j$. By an argument identical to that in 4.6, this procedure will be $O(n)$.\n",
    "\n",
    "Note, that in the implementation below, almost verbatim from 4.6, we allow one element to appear twice in a potential pair. A simple `if:break` clause would be sufficient to test for this case and suppress this behavior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 265,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_to_x_S(S, x):\n",
    "    n = len(S)\n",
    "    i = 0\n",
    "    j = n - 1\n",
    "    \n",
    "    S.sort()\n",
    "    \n",
    "    while ((i <= n - 1) and (j >= 0)):\n",
    "        sum = S[i] + S[j]\n",
    "        \n",
    "        if sum == x:\n",
    "            return (S[i], S[j])\n",
    "        if sum < x:\n",
    "            i += 1\n",
    "        if sum > x:\n",
    "            j -= 1\n",
    "            \n",
    "    return (-1,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TESTS\n",
      "(9, 9) = 18\n",
      "(1, 1) = 2\n",
      "(1, 7) = 8\n",
      "(1, 9) = 10\n",
      "(-1, -1) != 9\n",
      "(1, 1) = 2\n"
     ]
    }
   ],
   "source": [
    "print(\"TESTS\")\n",
    "    \n",
    "print(sum_to_x_S([3, 1, 9, 7, 5],18), \"= 18\")\n",
    "print(sum_to_x_S([3, 1, 9, 7, 5],2), \"= 2\")\n",
    "print(sum_to_x_S([3, 1, 9, 7, 5],8), \"= 8\")\n",
    "print(sum_to_x_S([3, 1, 9, 7, 5],10), \"= 10\")\n",
    "print(sum_to_x_S([3, 1, 9, 7, 5],9), \"!= 9\")\n",
    "print(sum_to_x_S([1],2), \"= 2\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(b):**\n",
    "\n",
    "If $S$ is sorted, we can use the same algorithm, just remove the sorting step. The algorithm will be $O(n)$ by the same argument used in 4.6. The inner loop will run at most $2n$ times, since both $i$ and $j$ must traverse $n$ elements and each loop moves one of the counters ahead by $1$. The inner loop contains 1 computation and 3 comparisons."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.10 [5]\n",
    "\n",
    "Given a set $S$ of $n$ integers and an integer $T$, give an $O(n^{k−1} \\log n)$ algorithm\n",
    "to test whether $k$ of the integers in $S$ add up to $T$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Note that an algorithm like that used in 4.6 and 4.8 will not work here. For example, set $k=3$. We could maintain 2 pointers, one moving left to right and one right to left, and then try every different position for the third. But we will likely get values that are both below and above $T$, and therefore there is no way to know which pointer we should change.\n",
    "\n",
    "In this case we will have to do a more systematic and less clever search. Specifically, we can look at all the $k-1$-tuples, and for each perform a binary search to see if the element necessary for the correct sum is present.\n",
    "\n",
    "How many such $k-1$-tuples are there? If we allow numbers to appear more than once, then $n^{k-1}$. For example, if $n=3$ and $k=3$, the $2$-tuples are $\\{(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)\\}$; there are $n^{k-1} = 3^2 = 9$ of them. However, if we do not, then the only allowable tuples are $(0,1), (0,2), (1,2)$; there are $n \\choose {k-1}$, which is clearly less than $n^{k-1}$. Note that permutations are equivalent: $(1,0)$ is not included because $(0,1)$ is already present. These represent indices of $S$ to sum, and it doesn't matter what order we sum them in.\n",
    "\n",
    "Below is my implementation for `sum_to_T(S, T, k, dup=False)`, along with implementations of the helper functions `construct_subsets(k, n)`, `construct_tuples(k, n)`, and `binary_search(S, x)`. The `dup` flag determines whether numbers in $S$ can be used repeatedly, and specifies whether the `construct_subsets` or `construct_tuples` function is used.\n",
    "\n",
    "**What is the running time of the `sum_to_T` function?** We break it up into its parts: **(1)** sorting $S$, **(2)** constructing the set of $k-1$-tuples, and **(3)** a binary search for each tuple.\n",
    "\n",
    "**(1)**\n",
    "\n",
    "First, $S$ is sorted. This is taken to be $O(n \\log n)$ time.\n",
    "\n",
    "**(2)**\n",
    "\n",
    "Second, the $k-1$-tuples are constructed, of which there are at most $n^{k-1}$; substantially less if duplicates are not allowed, which is the default behavior. This is $O(k\\cdot n^{k-1})$, since the inner-loops in both the construction functions each add a single element to a single tuple in the collection. Therefore the number of times this occurs is limited by the total number of indices in the collection of tuples. Viewed differently, a set of tuples is like a matrix, with each tuple a separate row. Then there are $n^{k-1}$ rows and $k$ columns, for a total of $k\\cdot n^{k-1}$ elements.\n",
    "\n",
    "The problem is that the $O(k\\cdot n^{k-1})$ bound for tuple construction already violates our goal of an $O(n^{k-1} \\log n)$ algorithm. However, if we don't allow values in $S$ to be used twice, which seems like the more natural usage case, the number of tuples becomes drastically smaller. Specifically we have:\n",
    "$$ {n \\choose {k}} = \\frac{n!}{k! \\, (n-k)!} \\stackrel{(1)}{\\leq} \\frac{n^k}{k!} \\leq n^k$$\n",
    "\n",
    "\n",
    "where (1) follows from the fact that only the first $k$ terms of $n!$ are retained; the rest are divided out by the $(n-k)!$ term in the denominator. Since successive factors in $n!$ grow smaller, making them all $n$ can only increase the value of the product.\n",
    "\n",
    "These equalities become strict when you note that $k$ cannot equal 1. Otherwise the problem reduces to searching for a number $x$ in an unsorted list, which cannot be done in $O(n^{k-1}\\log n) = O(n^0\\log n) = O(\\log n)$ time. Therefore plugging $k=k-1$ into the inequalities, the number of tuples is $O\\left(\\frac{n^{k-1}}{(k-1)!}\\right)$ and construction is $O\\left(\\frac{k}{(k-1)!} \\cdot n^{k-1}\\right)$. Plugging in $k=2$ into the first factor, $\\frac{2}{1!} = 2$. Plugging in $k=3$, $\\frac{3}{2!} = 1.5$. And plugging in $k=4$, $\\frac{4}{3!} = \\frac{4}{6} = 0.67$. These are clearly getting smaller, with a maximum of $2$. Therefore construction is $O(n^{k-1})$, making it not the bottleneck in an $O(n^{k-1} \\log n)$ algorithm.\n",
    "\n",
    "**(3)**\n",
    "\n",
    "For each $k-1$-tuple calculate the sum of the elements $S[i]$ for each $i$ in the tuple. Then subtract this from $T$ to determine what the last element would have to be for the sum to be $T$. Then perform a binary search looking for this value. Finally, if a value is found, scan over the tuple to make sure that it wasn't already included in the sum.\n",
    "\n",
    "The binary search is $O(\\log n)$, but there are also $2$ scans over the $k-1$-tuple. This is done potentially for all $O\\left(\\frac{n^{k-1}}{(k-1)!}\\right)$ $k-1$-tuples. As shown above, multiplying this factor by $k$ reduces it to $O(n^{k-1})$. So including the binary search, the portion of the algorithm is $O(n^{k-1} \\log n)$.\n",
    "\n",
    "**Total**\n",
    "\n",
    "The total running time is $O(n \\log n + n^{k-1} + n^{k-1} \\log n)$. Since $k \\geq 2$ (since as noted above the $k=1$ case is equivalent to asking for a log-time search in an unsorted list, which is impossible), this reduces to $O(n^{k-1} \\log n)$ as desired. This is only true in the case where numbers in $S$ cannot be used more than once towards the sum, which I imagine is the more usual usage case. The function implemented below can also allow repeats, but will be slower, I believe by a factor of $k$.\n",
    "\n",
    "The most difficult part of this problem was actually constructing the set of $k$-tuples. If $k$ is known, it can easily be implemented as a series of $k$ nested loops. But here $k$ is arbitrary. The case where duplicates are allowed (`construct_tuples`) was tedious to get the details right. The case of unique indices (`construct_subsets`) cleverly involved recursion, so there I was hostage to inspiration.\n",
    "\n",
    "After having solved this problem, I had this thought, which I won't further explore now... but why not do this: sort $S$ and construct all $k-2$ tuples, similar to before. Then use the algorithm from 4.6 and 4.8 to determine if there is a *pair* of numbers in $S$ that sum to the needed amount. Sure, this last part is $O(n)$ for each tuple, rather than $O(\\log n)$, but the tuples are now of size $k-2$ rather than $k-1$. Why wouldn't this lead to an $O(n^{k-2}\\cdot n) = O(n^{k-1})$ solution?\n",
    "\n",
    "NOTE: A simpler and much more transparent method for constructing all partial subsets is written in problem 7.15 using the backtracking algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2]\n",
      "[0, 1, 3]\n",
      "[0, 1, 4]\n",
      "[0, 2, 3]\n",
      "[0, 2, 4]\n",
      "[0, 3, 4]\n",
      "[1, 2, 3]\n",
      "[1, 2, 4]\n",
      "[1, 3, 4]\n",
      "[2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "#Recursive\n",
    "def partial_subsets(k, l, n):\n",
    "    M = []\n",
    "    \n",
    "    if k == 1:\n",
    "        for i in range(l, n):\n",
    "            M.append([i])\n",
    "    else:\n",
    "        for i in range(l, n):\n",
    "            Mnew = partial_subsets(k - 1, i + 1, n)        \n",
    "            for tup in Mnew:\n",
    "                tup.insert(0,i)\n",
    "            M.extend(Mnew)\n",
    "    return M\n",
    "\n",
    "def construct_subsets(k, n):\n",
    "    return partial_subsets(k, 0, n)\n",
    "\n",
    "for i in construct_subsets(3, 5):\n",
    "    print(i) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0]\n",
      "[1, 0]\n",
      "[2, 0]\n",
      "[0, 1]\n",
      "[1, 1]\n",
      "[2, 1]\n",
      "[0, 2]\n",
      "[1, 2]\n",
      "[2, 2]\n"
     ]
    }
   ],
   "source": [
    "def construct_tuples(k, n):\n",
    "    M = []\n",
    "    for j in range(n**k):\n",
    "        I = []\n",
    "        for i in range(k):\n",
    "            I.append(1)\n",
    "        M.append(I)\n",
    "    for i in range(k):                #what index\n",
    "        for j in range(n**(k-1-i)):   #what loop, loops are size n**(i+1)\n",
    "            for m in range(n):        #what number being placed\n",
    "                for p in range(n**i): #how many times\n",
    "                        M[j*(n**(i+1)) + m*(n**i) + p][i] = m\n",
    "\n",
    "    return M\n",
    "\n",
    "for i in construct_tuples(2, 3):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mid(l, h):\n",
    "    n = h - l + 1\n",
    "    return l + n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "def binary_search(S, x):\n",
    "    #S must be sorted.\n",
    "    n = len(S)\n",
    "    l = 0\n",
    "    h = n - 1\n",
    "    count = 0\n",
    "    \n",
    "    while(l < h):\n",
    "        m = mid(l,h)\n",
    "        #print(l, m, h)\n",
    "        if S[m] == x:\n",
    "            return m\n",
    "        if S[m] < x:\n",
    "            l = m\n",
    "        if S[m] > x:\n",
    "            h = m - 1\n",
    "        \n",
    "        count += 1\n",
    "        if count > n:\n",
    "            break\n",
    "    \n",
    "    if S[l] == x:\n",
    "        return l\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "S = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "for i , _ in enumerate(S):\n",
    "    print(binary_search(S,i))\n",
    "print(binary_search(S,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 numbers from S that add up to 10 are:\n",
      "1\n",
      "4\n",
      "5\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 3, 4]"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sum_to_T(S ,T, k, dup=False):\n",
    "    n = len(S)\n",
    "    \n",
    "    S.sort()\n",
    "    \n",
    "    if dup == False:\n",
    "        M = construct_subsets(k - 1, n)\n",
    "    else:\n",
    "        M = construct_tuples(k - 1, n)\n",
    "\n",
    "    for tup in M:\n",
    "        sum = 0\n",
    "        for j in range(k - 1):\n",
    "            sum += S[tup[j]]\n",
    "        diff = T - sum\n",
    "        b = binary_search(S, diff)\n",
    "        if b != -1:\n",
    "            # Check if b was already in the tuple\n",
    "            dup = False\n",
    "            for i in tup:\n",
    "                if i == b:\n",
    "                    dup = True\n",
    "            if dup == True:\n",
    "                continue\n",
    "                \n",
    "            print(\"%s numbers from S that add up to %s are:\" % (k, T))\n",
    "            for i in tup:\n",
    "                print(S[i])\n",
    "            print(S[b])\n",
    "            tup.append(b)\n",
    "            return tup\n",
    "    print(\"There is no such subset.\")\n",
    "        \n",
    "    \n",
    "\n",
    "\n",
    "S = [1, 2, 3, 4, 5]\n",
    "T = 10\n",
    "k = 3\n",
    "sum_to_T(S, T, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.12 [3]\n",
    "\n",
    "Devise an algorithm for finding the $k$ smallest elements of an unsorted set of $n$ integers in $O(n + k \\log n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Well, an initial solution would be to do $k$ successive linear scans, pulling out the next smallest element, for an $O(kn)$ running time. Or do one scan, keeping track of the $k$ smallest elements seen so far, and comparing each new element against them. Again, this will be $O(kn)$, since up to $k$ comparisons are done for each of the $n$ elements in the set.\n",
    "\n",
    "However, looking at this last idea, if the $k$ smallest elements seen so far are kept in sorted order, we only need to compare potential new elements with the largest of these $k$ smallest elements. In fact, full sorted order is not needed, only fast access to the current largest element.  This suggests storing these $k$ elements in a max-heap, which can be constructed in $O(k)$ time (p116). Then, each of the remaining $n-k$ elements needs to be compared with the maximum, which is a constant time operation. In the event that the candidate is less than this maximum, we need to insert it into the heap, and delete the current maximum to maintain the heap's size of $k$. Replacing the maximum with the candidate is constant time, but we then need to perform a \"bubble-down\" operation to ensure the dominance property of the heap is preserved. Bubble down is an $O(\\log k)$ operation, and is done for at most $n-k$ elements.\n",
    "\n",
    "$\\hspace{2em} function \\text{ k_smallest}(S,k):$  \n",
    "$\\hspace{4em} \\text{Place the first } k \\text{ elements of } S \\text{ into a max-heap}$  \n",
    "$\\hspace{4em} \\text{For the remaining } n-k \\text{ elements of } S:$  \n",
    "$\\hspace{6em} \\text{If } candidate < \\text{ max(heap):}$  \n",
    "$\\hspace{8em} \\text{Replace max(heap) with } candidate \\text{ and bubble-down}$  \n",
    "\n",
    "\n",
    "The algorithm is $O(k + n \\log k)$.\n",
    "\n",
    "But we want an algorithm that is $O(n + k \\log n)$.\n",
    "\n",
    "Put all $n$ elements on a min-heap, which is $O(n)$. Then extract the $k$ smallest elements. Each extraction requires an $O(\\log n)$ bubble down, and there are $k$ extractions, for $O(k \\log n)$.\n",
    "\n",
    "$\\hspace{2em} function \\text{ k_smallest}(S,k):$  \n",
    "$\\hspace{4em} \\text{Place all } n \\text{ elements of } S \\text{ into a min-heap}$  \n",
    "$\\hspace{4em} \\text{Perform } k \\text{ \"extract-min\" operations}$  \n",
    "\n",
    "This algorithm is $O(n + k \\log n)$. The first algorithm would perform better in \"online\" situations, where we don't know how many elements there will be."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quicksort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.16 [3] Unfinished\n",
    "\n",
    "Use the partitioning idea of quicksort to give an algorithm that finds the median element of an array of $n$ integers in expected $O(n)$ time. (Hint: must you look at both sides of the partition?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The Quicksort Partition function randomly selects an element from the array and partitions the array into 2 groups, one of which only contains elements that are smaller than the selected element, and another which only contains elements that are greater. These groups will be on the left and right sides of the selected element, respectively, after the function is finished, thereby placing the element in its final position. The function takes $O(n)$ time.\n",
    "\n",
    "Specifically, $\\text{partition}(S, l, h)$ will modify the elements of $S$ that lie between $l$ and $h$ as described above and will return the new integer position of the element used for the partition.\n",
    "\n",
    "For simplicity, we'll assume that $n = \\text{length}(S)$ is odd, in which case the median will be located at position $\\lfloor n\\,/\\,2 \\rfloor$ when $S$ is sorted.\n",
    "\n",
    "After we run $\\text{partition}$, we can compare the new location of the partition element with the location of the median value; if it's less, then we know that the median must lie in the right partition, and vice versa. This leads naturally to the following algorithm:\n",
    "\n",
    "$\\hspace{2em} function \\text{ median}(S,k):$  \n",
    "$\\hspace{4em} n = \\text{length}(S)$  \n",
    "$\\hspace{4em} l = 0$  \n",
    "$\\hspace{4em} h = n-1$  \n",
    "$\\hspace{4em} mid = \\lfloor n\\,/\\,2 \\rfloor$  \n",
    "$\\hspace{4em} \\text{while } h > l: $  \n",
    "$\\hspace{6em} p = \\text{partition}(S, l, h)$  \n",
    "$\\hspace{6em} \\text{if } p = mid:$  \n",
    "$\\hspace{8em} \\text{return }p$  \n",
    "$\\hspace{6em} \\text{elif } p < mid:$  \n",
    "$\\hspace{8em} l = p + 1$  \n",
    "$\\hspace{6em} \\text{else}:$  \n",
    "$\\hspace{8em} h = p - 1$  \n",
    "$\\hspace{4em} \\text{return}\\ h$  \n",
    "\n",
    "\n",
    "The algorithm could also be written recursively.\n",
    "\n",
    "On average, how many partitions will it take to find the median? To answer this question, we need to know how much the search range is narrowed each time. First note that after the first partition, the location of the median value becomes random within the new range; it could be the first value... it could be the last. However, since each location is equally like, on average it will be in the middle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.17 [3]\n",
    "\n",
    "The median of a set of $n$ values is the $\\lceil n/2 \\rceil \\text{th}$ smallest value.\n",
    "\n",
    "(a): Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would Quicksort make then in the worst case?\n",
    "\n",
    "(b): Suppose quicksort were always to pivot on the $\\lceil n/3 \\rceil \\text{th}$ smallest value of the\n",
    "current sub-array. How many comparisons would be made then in the worst case?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "NOTE: In the implementation of the partition function given in the book, `i` is incremented from `l` until the condition `i<h`; so `i` only reaches `h-1`. This loss of $1$ comparison for each partition would essentially count the number of nodes in the tree of recursion calls. The reason why `i` need not reach `h` is because `s[h]` IS the partition element in the book's implementation and need not be compared with itself. In the solutions below we will assume that the counter `i` does reach `h` for 3 reasons: (1) simplicity; (2) even in the book's implementation, the condition can be trivially changed to `i<h+1` with no change in functionality, since `p = h`, and so the inner loop condition `(s[i] < s[p])` will fail; and (3) in this question we assume that the partition function somehow selects the median value. This may or may not located at `h` and so `h` would need to be checked anyway.\n",
    "\n",
    "**(a):**\n",
    "\n",
    "On a set of size $n$, the partition function always performs exactly $n$ comparisons. Therefore at each level of the tree of recursive calls, quicksort performs linear work, regardless of how many subranges the $n$ elements have been partitioned into.\n",
    "\n",
    "The randomness of quicksort comes from the random selection of a partition element at each stage. If the partition function always selected the median value, then the performance of quicksort is no longer random, but depends solely on the input sequence.\n",
    "\n",
    "What matters is the number of levels in the tree of recursion calls. If the median value is selected each time, then the two resulting partitions will have the same number of values. So the maximum size of any subrange in a given level of the recursion tree is half that of the previous level. Therefore the number of levels of the tree will be exactly m = $\\lceil \\lg n \\rceil$.\n",
    "\n",
    "If for simplicity we assume that the last level of the tree is completely filled, the total number of comparisons is\n",
    "\n",
    "$$ n \\lceil \\lg n \\rceil$$\n",
    "\n",
    "**(b):**\n",
    "\n",
    "If quicksort always pivoted on the $\\lceil n/3 \\rceil \\text{th}$ smallest value, each partition would decrease the largest partition by a fraction of $2\\, / \\, 3$. How many times must this happen to reduce to $1$?\n",
    "\n",
    "$\\left(\\frac{2}{3}\\right)^hn = 1 \\,\\,\\Rightarrow\\,\\, n = \\left(\\frac{3}{2}\\right)^h \\,\\,\\Rightarrow\\,\\, h = \\log_{3/2}n$\n",
    "\n",
    "\n",
    "Therefore the height of the tree is $\\log_{3/2}n$. However, the smallest branch of the tree will be of length $\\log_{3/1}n$. For simplicity, and to find an upper bound on the number of comparisons, we'll assume that every branch is of length $\\log_{3/2}n$. If $n$ comparisons are done at each level, and again we assume that the last level of the tree is completely filled, then an upper bound for the total number of comparisons is:\n",
    "\n",
    "$$ n \\lceil \\log_{3/2} n \\rceil$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Sorting Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  4.22 [3]\n",
    "\n",
    "Show that $n$ positive integers in the range $1$ to $k$ can be sorted in $O(n \\log k)$ time. The interesting case is when $k << n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Case:** $k \\geq n$. Do quicksort, which will be $O(n \\log n)$ running time. But since $\\log n \\leq \\log k$, this will also be $O(n \\log k)$.\n",
    "\n",
    "**Case:** $k < n$. Like a hash table with chaining, make an array of size $k$ where element $i$ contains a pointer to a linked-list bucket that will contain only elements whose value is $i+1$. For each element in our set, use the table to look up the memory address of the correct bucket and add the element to that bucket. With an index, the look up is $O(1)$, and inserting the element into the bucket is also $O(1)$. After all the elements have been inserted, we need to merge them. Since they are linked-lists, we only need to have the pointers in the last elements of each bucket point to the head of the next. This would take $O(k)$ if the buckets maintained pointers to their last values. Therefore this sorting is $O(n + k)$. And since $k < n < n \\log k$, this is also $O(n \\log k)$.\n",
    "\n",
    "Just looked this up, and this is very similar to Pidgeonhole Sort, Counting Sort, and Bucket Sort.\n",
    "\n",
    "For a slower algorithm that is exactly $O(n \\log k)$, construct a binary search tree of nodes $1$ through $k$ where each node contains a pointer to a bucket of equal-value elements. For each element in the set, perform the binary search in $O(\\log k)$ time to find the appropriate bucket and place the value in the bucket. After all the elements have been placed in the buckets, connect/merge them in $O(k)$ time as in the earlier solution. This algorithm will be $O(n\\log k + k) = O(n\\log k)$ since $k<n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lower Bounds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.30 [3]\n",
    "\n",
    "A company database consists of 10,000 sorted names, 40% of whom are known as good customers and who together account for 60% of the accesses to the database. There are two data structure options to consider for representing the database:\n",
    "\n",
    "- Put all the names in a single array and use binary search.\n",
    "- Put the good customers in one array and the rest of them in a second array. Only if we do not find the query name on a binary search of the first array do we do a binary search of the second array.\n",
    "\n",
    "Demonstrate which option gives better expected performance. Does this change if linear search on an unsorted array is used instead of binary search for both options?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "$\\text{P}(\\text{good}) = 0.60$ while $\\text{P}(\\text{bad}) = 0.40$.\n",
    "\n",
    "In the first option, queries on both good and bad customers take $\\lceil \\lg 10,000 \\rceil = 14$ comparisons.\n",
    "\n",
    "In the second option, queries on good customers take $\\lceil \\lg 4,000 \\rceil = 12$ comparisons, while queries on bad customers take $\\lceil \\lg 4,000 \\rceil + \\lceil \\lg 6,000 \\rceil = 12 + 13 = 25$ comparisons. The expected case is therefore $12*0.6 + 25*0.4 = 17.2$ comparisons.\n",
    "\n",
    "Clearly the first option is better, and simpler.\n",
    "\n",
    "What if linear search on an unsorted array is used instead. In this case, expected look up time is half the size of the array. For option 1, expected number of comparisons for each query would be 5,000 comparisons. For option 2 it would be $0.6\\cdot\\text{E[good query]} + 0.4\\cdot\\text{E[bad query]}$ $ = 0.6\\cdot2,000 + 0.4\\cdot3,000 = 2,400$ comparisons. In this case, option 2 is better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.31 [3]\n",
    "\n",
    "Suppose you are given an array $A$ of $n$ sorted numbers that has been circularly shifted $k$ positions to the right. For example, $\\{35, 42, 5, 15, 27, 29\\}$ is a sorted array that has been circularly shifted $k = 2$ positions, while $\\{27, 29, 35, 42, 5, 15\\}$ has been shifted $k = 4$ positions.\n",
    "\n",
    "- Suppose you know what $k$ is. Give an $O(1)$ algorithm to find the largest number in $A$.\n",
    "- Suppose you do not know what $k$ is. Give an $O(\\lg n)$ algorithm to find the largest number in $A$. For partial credit, you may give an $O(n)$ algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Case:** $k$ is known.\n",
    "\n",
    "In the first example given in the problem statement where $k=2$, the largest element is $42$ and is located at position $1$. It should be at position $n-1$, but instead is located at position $(n-1 + k) \\bmod n = (6 - 1 + 2) \\bmod 6 = 7 \\bmod 6 = 1$. Generally, when circularly shifting numbers, they move from position $i$ to position $(i + k) \\bmod n$. To find the largest element, plug in $i = n-1$.\n",
    "\n",
    "So in this case, the largest element is $A[(n - 1 + k) \\bmod n]$.\n",
    "\n",
    "**Case:** $k$ unknown.\n",
    "\n",
    "We need to determine $k$, after which it is an instant lookup to find the largest value. So how can we find $k$ in $O(\\lg n)$ time? $\\lg n$ suggests a binary search. Looking at the $k=2$ example $\\{35, 42, 5, 15, 27, 29\\}$, we note that the value $5$ should be in position $0$ but instead is in position $2$. Therefore the location of the smallest element is equal to $k$. So how can we find this smallest value? We use the fact that the elements are already sorted, modulo the circular permutation. We need to convert this into a test we can perform to determine if we need to look in the left or right subrange. Looking at the example again, we see that all the numbers in the array are greater than or equal to the first number, $35$, *until* the numbers reset, at which point they are all less than $35$. This observation probides our condition: we test if the median of the subrange is less than or greater than the first value; if less, then we look in the left subrange, if greater, we look in the right. The only exception will be when k=0, in which case the first value will be the smallest and all the numbers will be greater.\n",
    "\n",
    "The solution given below fails when the numbers are not distinct. Suppose we are given a set of $n$ numbers where $n-1$ of them are all the same. In this case, when we test the middle element, if it is the same as the first element, we have no idea if the differing element is to the left or to the right. Furthermore, we don't know if it will be less than or greater than all the other values, so we can't just ignore it. We have to find it. But there is no longer any property amongst the numbers that can expedite our search.\n",
    "\n",
    "With this in mind, I don't see how an $O(\\lg n)$ algorithm is possible in the case where the numbers are not distinct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 311,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mid(l, h):\n",
    "    n = h - l + 1\n",
    "    return l + n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 312,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def largest(A):\n",
    "    n = len(A)\n",
    "    l = 0\n",
    "    h = n - 1\n",
    "    k = -1\n",
    "    count = 0\n",
    "    \n",
    "    if A[0] < A[h]:\n",
    "        k = 0\n",
    "    else:\n",
    "        while l < h:     \n",
    "            m = mid(l,h)\n",
    "            prev = m - 1 if m != 0 else n-1\n",
    "            if A[prev] > A[m]:\n",
    "                k = m\n",
    "                break\n",
    "            if A[m] < A[0]:\n",
    "                h = m - 1\n",
    "            if A[m] > A[0]:\n",
    "                l = m + 1\n",
    "            count += 1\n",
    "            if count > n:\n",
    "                break\n",
    "    if k == -1:\n",
    "        m = l\n",
    "        prev = m - 1 if m != 0 else n-1\n",
    "        if A[prev] > A[m]:\n",
    "            k = m\n",
    "    return A[(n - 1 + k) % n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 313,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TESTS\n",
      "\n",
      "Distinct numbers, even number\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True \n",
      "\n",
      "Distinct numbers, odd number\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True \n",
      "\n",
      "All same number\n",
      "True\n",
      "True\n",
      "True \n",
      "\n",
      "Repeated non-largest elements\n",
      "True\n",
      "True\n",
      "True\n",
      "True\n",
      "True \n",
      "\n",
      "Repeated largest elements\n",
      "False\n",
      "False\n",
      "False\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# TESTS\n",
    "print(\"TESTS\\n\")\n",
    "print(\"Distinct numbers, even number\")\n",
    "print(largest([0, 1, 2, 3, 4, 5]) == 5)\n",
    "print(largest([5, 0, 1, 2, 3, 4]) == 5)\n",
    "print(largest([4, 5, 0, 1, 2, 3]) == 5)\n",
    "print(largest([3, 4, 5, 0, 1, 2]) == 5)\n",
    "print(largest([2, 3, 4, 5, 0, 1]) == 5)\n",
    "print(largest([1, 2, 3, 4, 5, 0]) == 5, \"\\n\")\n",
    "\n",
    "print(\"Distinct numbers, odd number\")\n",
    "print(largest([0, 1, 2, 3, 4, 5, 6]) == 6)\n",
    "print(largest([5, 6, 0, 1, 2, 3, 4]) == 6)\n",
    "print(largest([4, 5, 6, 0, 1, 2, 3]) == 6)\n",
    "print(largest([3, 4, 5, 6, 0, 1, 2]) == 6)\n",
    "print(largest([2, 3, 4, 5, 6, 0, 1]) == 6)\n",
    "print(largest([1, 2, 3, 4, 5, 6, 0]) == 6, \"\\n\")\n",
    "\n",
    "print(\"All same number\")\n",
    "print(largest([0,0,0,0,0]) == 0)\n",
    "print(largest([1,1,1,1,1]) == 1)\n",
    "print(largest([5,5,5,5,5]) == 5, \"\\n\")\n",
    "\n",
    "print(\"Repeated non-largest elements\")\n",
    "print(largest([1,0,0,0,0]) == 1)\n",
    "print(largest([0,1,0,0,0]) == 1)\n",
    "print(largest([0,0,1,0,0]) == 1)\n",
    "print(largest([0,0,0,1,0]) == 1)\n",
    "print(largest([0,0,0,0,1]) == 1, \"\\n\")\n",
    "\n",
    "print(\"Repeated largest elements\")\n",
    "print(largest([1,2,2,2,2]) == 1)\n",
    "print(largest([2,1,2,2,2]) == 1)\n",
    "print(largest([2,2,1,2,2]) == 1)\n",
    "print(largest([2,2,2,1,2]) == 1)\n",
    "print(largest([2,2,2,2,1]) == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.32 [3]\n",
    "\n",
    "Consider the numerical 20 Questions game. In this game, Player 1 thinks of a number in the range $1$ to $n$. Player 2 has to figure out this number by asking the fewest number of true/false questions. Assume that nobody cheats.\n",
    "\n",
    "(a): What is an optimal strategy if $n$ in known?\n",
    "\n",
    "(b): What is a good strategy is $n$ is not known?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):** If $n$ is known, do a binary search between $1$ and $n$. If $n \\leq 2^{20}$, you're sure to win. If $n > 2^{20}$, ask 19 binary search questions, and take a guess for question 20.\n",
    "\n",
    "**(b):** If $n$ is not known, do a one-sided binary search for increasing powers of 2, meaning ask \"Is the number less than 16?\", \"Is the number less than 32?\", \"Is the number less than 64?\"... . Once you get a True answer, do a binary search between that number and the previous number. Meaning if \"Is the number less than 1024?\" returns True, do a binary search between 512 and 1023. Since 20 questions is sufficient to determine any number amongst $2^{20} \\approx (2^{10})^2 \\approx (1,000)^2 = 1,000,000$, maybe the first number in the one-sided binary search should be $2^{18}$. It's only greater than $2^{20}$ where you have to worry."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.33 [5]\n",
    "\n",
    "Suppose that you are given a sorted sequence of distinct integers $\\{a_1, a_2, . . . , a_n\\}$. Give an $O(\\lg n)$ algorithm to determine whether there exists an index $i$ such that $a_i = i$. For example, in $\\{−10,−3, 3, 5, 7\\}$, $a_3 = 3$. In $\\{2, 3, 4, 5, 6, 7\\}$, there is no such $i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Let $f(x)$ be the function that maps $x$ to $A[x]$. We want to know if $f(x) = x$ for any $x$. Put another way, we want to know if $f(x)$ ever intersects the line $y = x$. Since $f$ is restricted to distinct integers, we know that $f(x+1) - f(x) \\geq 1$. The slope of $f$ is always greater than or equal to that of the line $y=x$. So once $f$ crosses the line, it can't go back.\n",
    "\n",
    "Therefore we can test the first and last values of A: if the first is less than $1$ and the last is greater than $n$, we know that somewhere inbetween $f$ crossed $y=x$. The only question is whether the crossing value is in $A$. We can perform a binary search: if the median value in a given range is greater than its position value, we look in the left subrange. If it's less, we look right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mid(l, h):\n",
    "    n = h - l + 1\n",
    "    return l + n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def stationary(A):\n",
    "    n = len(A)\n",
    "    l = 0\n",
    "    h = n - 1\n",
    "    k = -1\n",
    "    count = 0\n",
    "\n",
    "    if A[l] == 1:\n",
    "        return 1\n",
    "\n",
    "    if not ((A[l] <= 1) and (A[h] >= n)):\n",
    "        return None\n",
    "\n",
    "    while l < h:     \n",
    "        m = mid(l,h)\n",
    "        if A[m] == m + 1:\n",
    "            k = m + 1\n",
    "            break\n",
    "        if A[m] < m + 1:\n",
    "            l = m + 1\n",
    "        if A[m] > m + 1:\n",
    "            h = m - 1\n",
    "        \n",
    "        count += 1\n",
    "        if count > n:\n",
    "            break\n",
    "\n",
    "    if k == -1:\n",
    "        m = l\n",
    "        if A[m] == m + 1:\n",
    "            k = m + 1\n",
    "            \n",
    "    return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 322,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TESTS\n",
      "Intersect towards middle, odd: True\n",
      "Intersect towards middle, even: True\n",
      "Intersect at end, odd: True\n",
      "Intersect at end, even: True\n",
      "Intersect at beginning, odd: True\n",
      "Intersect at beginning, even: True\n",
      "All intersect: True\n",
      "No intersect, above: True\n",
      "No intersect, below: True\n",
      "Size 1, below: True\n",
      "Size 1, above: True\n",
      "Size 1, True: True\n"
     ]
    }
   ],
   "source": [
    "print(\"TESTS\")\n",
    "print(\"Intersect towards middle, odd:\", stationary([-10, -3, 3, 5, 7]) == 3)\n",
    "print(\"Intersect towards middle, even:\", stationary([-10, -3, 3, 5, 7, 8]) == 3)\n",
    "print(\"Intersect at end, odd:\", stationary([-1, 0, 1, 2, 3, 4, 7]) == 7)\n",
    "print(\"Intersect at end, even:\", stationary([-1, 0, 1, 2, 3, 4, 5, 8]) == 8)\n",
    "print(\"Intersect at beginning, odd:\", stationary([1, 3, 4, 5, 6, 7, 8]) == 1)\n",
    "print(\"Intersect at beginning, even:\", stationary([1, 3, 4, 5, 6, 7]) == 1)\n",
    "print(\"All intersect:\", stationary([1, 2, 3, 4, 5, 6, 7]) != None)\n",
    "print(\"No intersect, above:\", stationary([2,3,4,5,6,7]) == None)\n",
    "print(\"No intersect, below:\", stationary([-7, -6, -5, -4, -3, -2]) == None)\n",
    "print(\"Size 1, below:\", stationary([0]) == None)\n",
    "print(\"Size 1, above:\", stationary([2]) == None)\n",
    "print(\"Size 1, True:\", stationary([1]) == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.34 [5]\n",
    "\n",
    "Suppose that you are given a sorted sequence of distinct integers $\\{a_1, a_2, . . . , a_n\\}$,\n",
    "drawn from $1$ to $m$ where $n < m$. Give an $O(\\lg n)$ algorithm to find an integer $\\leq m$\n",
    "that is not present in $a$. For full credit, find the smallest such integer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "If no integer is skipped, then $a[i] = i$, where the index is base 1. If $k$ integers have been skipped before position $i$, then $a[i] = i+k$. Each skipped integer increases the gap between $a[i]$ and $i$ by $1$. For example, if $a = \\{1, 2, 3, 7, 8, 9\\}$, the integers $4$, $5$, and $6$ were skipped after the number $3$, after which the numbers satisfy $s[i] = i + 3$, because 3 integers were skipped. For example $a[5] = 5 + 3 = 8$.\n",
    "\n",
    "To find the first skipped integer, we seek to find the first position $i$ such that $a[i] = i$ but $a[i+1] > i+1$; the missing number will be $i+1$. To do so we can do a binary search. If we check position $i$ and find that $A[i] > i$, we are after the first skipped number, so we look in the left subrange. If we find that $A[i] = i$, we then check whether $A[i+1] > i+1$. If so, then we found our man. If not, then we look in the right subrange.\n",
    "\n",
    "Binary search is $O(\\lg n)$. We are performing it directly on the sorted array that is given to us, so there is no cost for constructing another data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mid(l, h):\n",
    "    n = h - l + 1\n",
    "    return l + n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 328,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def first_missing(A):\n",
    "    n = len(A)\n",
    "    l = 0\n",
    "    h = n - 1\n",
    "    count = 0\n",
    "    \n",
    "    if A[n - 1] == n:\n",
    "        return None\n",
    "    \n",
    "    if A[0] != 1:\n",
    "        return 1\n",
    "    if (A[0] == 1) and (A[1] != 2):\n",
    "        return 2\n",
    "    \n",
    "    while l < h:    \n",
    "        m = mid(l,h)\n",
    "        if A[m] == m + 1:\n",
    "            if A[m + 1] > m + 2:\n",
    "                return m + 2\n",
    "            else:\n",
    "                l = m + 1\n",
    "        else:\n",
    "            h = m - 1\n",
    "            \n",
    "        count += 1\n",
    "        if count > n:\n",
    "            break\n",
    "    m = l\n",
    "    if A[m] == m + 1:\n",
    "        if A[m + 1] > m + 2:\n",
    "            return m + 2\n",
    "        else:\n",
    "            return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 329,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TESTS\n",
      "Missing near middle, odd: True\n",
      "Missing near middle, even: True\n",
      "Missing near middle, odd: True\n",
      "Missing near middle, even: True\n",
      "Missing first, even True\n",
      "Missing first, odd True\n",
      "Missing last, odd: True\n",
      "Missing last, even: True\n",
      "Missing a lot, even: True\n",
      "None, even: True\n",
      "None, odd: True\n",
      "Size 1: True\n",
      "Size 1, None: True\n"
     ]
    }
   ],
   "source": [
    "print(\"TESTS\")  \n",
    "print(\"Missing near middle, odd:\", first_missing([1, 2, 3, 5, 6]) == 4)\n",
    "print(\"Missing near middle, even:\", first_missing([1, 2, 3, 5, 6, 7]) == 4)\n",
    "print(\"Missing near middle, odd:\", first_missing([1, 2, 4, 5, 6]) == 3)\n",
    "print(\"Missing near middle, even:\", first_missing([1, 2, 4, 5, 6, 7]) == 3)\n",
    "print(\"Missing first, even\", first_missing([2, 3, 5, 6]) == 1)\n",
    "print(\"Missing first, odd\", first_missing([2, 3, 5, 6, 7]) == 1)\n",
    "print(\"Missing last, odd:\", first_missing([1, 2, 3, 4, 5, 6, 8]) == 7)\n",
    "print(\"Missing last, even:\", first_missing([1, 2, 3, 4, 5, 6, 7, 9]) == 8)\n",
    "print(\"Missing a lot, even:\", first_missing([1, 3, 5, 7, 9, 11]) == 2) \n",
    "print(\"None, even:\", first_missing([1, 2, 3, 4, 5, 6]) == None) \n",
    "print(\"None, odd:\", first_missing([1, 2, 3, 4, 5]) == None) \n",
    "print(\"Size 1:\", first_missing([2]) == 1)\n",
    "print(\"Size 1, None:\", first_missing([1]) == None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation Challenges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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
}