Chapter_08_Sorting_in_Linear_Time/problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-1 Probabilistic lower bounds on comparison sorting\n",
    "\n",
    "> In this problem, we prove a probabilistic $\\Omega(n \\lg n)$ lower bound on the running time of any deterministic or randomized comparison sort on $n$ distinct input elements. We begin by examining a deterministic comparison sort $A$ with decision tree $T_A$. We assume that every permutation of $A$'s inputs is equally likely."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Suppose that each leaf of $T_A$ is labeled with the probability that it is reached given a random input. Prove that exactly $n!$ leaves are labeled $1/n!$ and that the rest are labeled 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There should be only $n!$ leaves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Let $D(T)$ denote the external path length of a decision tree $T$ ; that is, $D(T)$ is the sum of the depths of all the leaves of $T$. Let $T$ be a decision tree with $k > 1$ leaves, and let $LT$ and $RT$ be the left and right subtrees of $T$. Show that $D(T)=D(LT)+D(RT)+k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add $T$ means all the $k$ depths of leaves increase by 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Let $d(k)$ be the minimum value of $D(T)$ over all decision trees $T$ with $k > 1$ leaves. Show that $d(k)=\\min _{1 \\le i \\le k - 1}\\{d(i)+d(k-i)+k\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$D(T)=D(LT)+D(RT)+k$, $d(k)=\\min _{1 \\le i \\le k - 1}\\{d(i)+d(k-i)+k\\}$ iterates all the possibilities."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Prove that for a given value of $k > 1$ and $i$ in the range $1 \\le i \\le k - 1$, the function $i \\lg i + (k - i) \\lg(k - i)$ is minimized at $i = k/2$. Conclude that $d(k) = \\Omega(k \\lg k)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "f(i) &=& i \\lg i + (k - i) \\lg (k - i) \\\\\n",
    "f'(i) &=& \\lg i - \\lg (k - i) \\\\\n",
    "0 &=& \\displaystyle \\lg \\frac{i}{k-i} \\\\\n",
    "1 &=& \\displaystyle \\frac{i}{k-i} \\\\\n",
    "i &=& k / 2 \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. Prove that $D(T_A)=\\Omega(n!\\lg (n!))$, and conclude that the average-case time to sort $n$ elements is $\\Omega(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$d(T_A) = d(n!) = \\Omega(n! \\lg n!)$\n",
    "\n",
    "Average:\n",
    "$$\n",
    "\\frac{\\Omega(n! \\lg n!)}{n!} = \\Omega(\\lg n!) = \\Omega(n \\lg n)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Now, consider a _randomized_ comparison sort $B$. We can extend the decision-tree model to handle randomization by incorporating two kinds of nodes: ordinary comparison nodes and \"randomization\" nodes. A randomization node models a random choice of the form RANDOM$(1, r)$ made by algorithm $B$; the node has $r$ children, each of which is equally likely to be chosen during an execution of the algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*f*__. Show that for any randomized comparison sort $B$, there exists a deterministic comparison sort $A$ whose expected number of comparisons is no more than those made by $B$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-2 Sorting in place in linear time\n",
    "\n",
    "> Suppose that we have an array of $n$ data records to sort and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:\n",
    "1. The algorithm runs in $O(n)$ time.\n",
    "2. The algorithm is stable.\n",
    "3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Give an algorithm that satisfies criteria 1 and 2 above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Counting sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Give an algorithm that satisfies criteria 1 and 3 above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Partition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Give an algorithm that satisfies criteria 2 and 3 above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insertion sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Can you use any of your sorting algorithms from parts (a)-(c) as the sorting method used in line 2 of RADIX-SORT, so that RADIX-SORT sorts n records with $b$-bit keys in $O(bn)$ time? Explain how or why not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, stable and quick."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. Suppose that the $n$ records have keys in the range from 1 to $k$. Show how to modify counting sort so that it sorts the records in place in $O(n+k)$ time. You may use $O(k)$ storage outside the input array. Is your algorithm stable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as permutation group:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def counting_in_place(a):\n",
    "    k = max(a)\n",
    "    c = [0 for _ in range(k + 1)]\n",
    "    for v in a:\n",
    "        c[v] += 1\n",
    "    for i in range(1, k + 1):\n",
    "        c[i] += c[i - 1]\n",
    "    r = c[:]\n",
    "    for i in range(len(a)):\n",
    "        while True:\n",
    "            if a[i] == 0:\n",
    "                if i < r[0]:\n",
    "                    break\n",
    "            else:\n",
    "                if r[a[i] - 1] <= i < r[a[i]]:\n",
    "                    break\n",
    "            c[a[i]] -= 1\n",
    "            pos = c[a[i]]\n",
    "            a[i], a[pos] = a[pos], a[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not stable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-3 Sorting variable-length items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is $n$. Show how to sort the array in $O(n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the number of integers which have $b_i$ digits is $n_i$, divide the integers into different buckets using counting sort, the integers in the same bucket have the same $b_i$, then use radix sort in each bucket:\n",
    "\n",
    "$$\n",
    "\\sum_{i} b_i n_i = n\n",
    "$$\n",
    "\n",
    "therefore the algorithm is $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def counting_sort(a, m):\n",
    "    b = [0 for _ in range(len(a))]\n",
    "    k = 10\n",
    "    c = [0 for _ in range(k)]\n",
    "    for s in a:\n",
    "        c[ord(s[m]) - ord('0')] += 1\n",
    "    for i in range(1, k):\n",
    "        c[i] += c[i - 1]\n",
    "    for i in range(len(a) - 1, -1, -1):\n",
    "        c[ord(a[i][m]) - ord('0')] -= 1\n",
    "        b[c[ord(a[i][m]) - ord('0')]] = a[i]\n",
    "    return b\n",
    "\n",
    "\n",
    "def radix_sort(a):\n",
    "    for m in range(len(a[0]) - 1, -1, -1):\n",
    "        a = counting_sort(a, m)\n",
    "    return a\n",
    "\n",
    "\n",
    "def count_and_divide(a):\n",
    "    a = map(str, a)\n",
    "    b = [0 for _ in range(len(a))]\n",
    "    k = 0\n",
    "    for s in a:\n",
    "        k = max(k, len(s))\n",
    "    c = [0 for _ in range(k + 1)]\n",
    "    for s in a:\n",
    "        c[len(s)] += 1\n",
    "    for i in range(1, k + 1):\n",
    "        c[i] += c[i - 1]\n",
    "    r = c[:]\n",
    "    for i in range(len(a) - 1, -1, -1):\n",
    "        c[len(a[i])] -= 1\n",
    "        b[c[len(a[i])]] = a[i]\n",
    "    for i in range(k + 1):\n",
    "        if c[i] < r[i]:\n",
    "            b[c[i]:r[i]] = radix_sort(b[c[i]:r[i]])\n",
    "    return map(int, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is $n$. Show how to sort the strings in $O(n)$ time. (Note that the desired order here is the standard alphabetical order; for example, $a < ab < b$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sort the strings by their first characters with counting-sort, then divide the strings by their first characters, repeat the process in each new group. Since each character is used only once for sorting, the amortized running time is $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_key(s, i):\n",
    "    if i >= len(s):\n",
    "        return 0\n",
    "    return ord(s[i]) - ord('a') + 1\n",
    "\n",
    "\n",
    "def counting_sort(a, p=0):\n",
    "    k = 27\n",
    "    b = ['' for _ in range(len(a))]\n",
    "    c = [0 for _ in range(k)]\n",
    "    for s in a:\n",
    "        c[get_key(s, p)] += 1\n",
    "    for i in range(1, k):\n",
    "        c[i] += c[i - 1]\n",
    "    r = c[:]\n",
    "    for i in range(len(a) - 1, -1, -1):\n",
    "        c[get_key(a[i], p)] -= 1\n",
    "        b[c[get_key(a[i], p)]] = a[i]\n",
    "    for i in range(1, k):\n",
    "        if c[i] < r[i]:\n",
    "            b[c[i]:r[i]] = counting_sort(b[c[i]:r[i]], p+1)\n",
    "    return b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-4 Water jugs\n",
    "\n",
    "> Suppose that you are given $n$ red and $n$ blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.\n",
    "\n",
    "> Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Describe a deterministic algorithm that uses $\\Theta(n^2)$ comparisons to group the jugs into pairs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare each red jug with each blue jug."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Prove a lower bound of $\\Omega(n \\lg n)$ for the number of comparisons that an algorithm solving this problem must make."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "n! &\\le& 3^h \\\\\n",
    "h &=& \\Omega(n \\lg n)\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Give a randomized algorithm whose expected number of comparisons is $O(n \\lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Random choose a red jug as pivot and partition blue rugs, and use the blue rug which is equal to the red rug as pivot and partition red rugs.\n",
    "\n",
    "Worst case is $O(n^2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(a, b, p, r):\n",
    "    pos = random.randint(p, r - 1)\n",
    "    i = p - 1\n",
    "    for j in range(p, r):\n",
    "        if b[j] <= a[pos]:\n",
    "            i += 1\n",
    "            b[i], b[j] = b[j], b[i]\n",
    "            if b[i] == a[pos]:\n",
    "                k = i\n",
    "    b[i], b[k] = b[k], b[i]\n",
    "    pos = i\n",
    "    i = p - 1\n",
    "    for j in range(p, r):\n",
    "        if a[j] <= b[pos]:\n",
    "            i += 1\n",
    "            a[i], a[j] = a[j], a[i]\n",
    "            if a[i] == b[pos]:\n",
    "                k = i\n",
    "    a[i], a[k] = a[k], a[i]\n",
    "    return pos\n",
    "\n",
    "\n",
    "def quick_sort(a, b, p, r):\n",
    "    if p + 1 < r:\n",
    "        q = partition(a, b, p, r)\n",
    "        quick_sort(a, b, p, q)\n",
    "        quick_sort(a, b, q + 1, r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-5 Average sorting\n",
    "\n",
    "> Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an $n$-element array $A$ __*k-sorted*__ if, for all $i=1,2, \\dots,n-k$, the following holds:\n",
    "\n",
    "> $$\n",
    "\\frac{\\sum_{j=i}^{i+k-1}A[j]}{k} \\le \\frac{\\sum_{j=i+1}^{i+k}A[j]}{k}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. What does it mean for an array to be 1-sorted?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Give a permutation of the numbers $1,2,\\dots,10$ that is 2-sorted, but not sorted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1, 2, 1, 2, 1, 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Prove that an $n$-element array is $k$-sorted if and only if $A[i] \\le A[i + k]$ for all $i=1,2,\\dots,n-k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\frac{\\sum_{j=i}^{i+k-1}A[j]}{k} &\\le& \\displaystyle \\frac{\\sum_{j=i+1}^{i+k}A[j]}{k} \\\\\n",
    "\\displaystyle \\sum_{j=i}^{i+k-1}A[j] &\\le& \\displaystyle \\sum_{j=i+1}^{i+k}A[j] \\\\\n",
    "A[i] &\\le& A[i + k]\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Give an algorithm that $k$-sorts an $n$-element array in $O(n \\lg (n / k))$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to sort $k$ groups, each group has the same $(i \\mod k)$. We can sort one group in $O(n/k\\lg (n/k))$, to sort $k$ groups, it is $O(n \\lg (n/k)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_sort(a, k):\n",
    "    for i in range(k):\n",
    "        a[i:len(a):k] = sorted(a[i:len(a):k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> We can also show a lower bound on the time to produce a $k$-sorted array, when $k$ is a constant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. Show that we can sort a $k$-sorted array of length $n$ in $O(n\\lg k)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same as Exercise 6.5-9."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*f*__. Show that when $k$ is a constant, $k$-sorting an $n$-element array requires $\\Omega(n \\lg n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\Omega(n \\lg n/k) = \\Omega(n \\lg n) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-6 Lower bound on merging sorted lists\n",
    "\n",
    "> The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine MERGE in Section 2.3.1. In this problem, we will prove a lower bound of $2n - 1$ on the worst-case number of comparisons required to merge two sorted lists, each containing $n$ items.\n",
    "First we will show a lower bound of $2n - o(n)$ comparisons by using a decision tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Given $2n$ numbers, compute the number of possible ways to divide them into two sorted lists, each with $n$ numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\displaystyle \\binom{2n}{n}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform at least $2n - o(n)$ comparisons."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on Exercise C.1.13, \n",
    "\n",
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\binom{2n}{n} &\\le& \\displaystyle 2^h \\\\\n",
    "h &\\ge& \\displaystyle \\lg\\frac{(2n)!}{(n!)^2} \\\\\n",
    "&=& \\displaystyle \\lg (2n!) - 2\\lg (n!) \\\\\n",
    "&=& \\displaystyle \\Theta(2n\\lg 2n) - 2\\Theta(n \\lg n) \\\\\n",
    "&=& \\displaystyle \\Theta(2n) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Now we will show a slightly tighter $2n - 1$ bound."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Show that if two elements are consecutive in the sorted order and from different lists, then they must be compared."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have to know the order of the two consecutive elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Use your answer to the previous part to show a lower bound of $2n - 1$ comparisons for merging two sorted lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are $2n-1$ pairs of consecutive elements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8-7 The 0-1 sorting lemma and columnsort\n",
    "\n",
    "$\\dots$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}