Chapter_09_Medians_and_Order_Statistics/exercises_9.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9.2 Selection in expected linear time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.2-1\n",
    "\n",
    "> Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.2-2\n",
    "\n",
    "> Argue that the indicator random variable $X_k$ and the value $T(max(k - 1, n - k))$ are independent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.2-3\n",
    "\n",
    "> Write an iterative version of RANDOMIZED-SELECT."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(a, p, r):\n",
    "    x = a[r - 1]\n",
    "    i = p - 1\n",
    "    for k in range(p, r - 1):\n",
    "        if a[k] < x:\n",
    "            i += 1\n",
    "            a[i], a[k] = a[k], a[i]\n",
    "    i += 1\n",
    "    a[i], a[r - 1] = a[r - 1], a[i]\n",
    "    return i\n",
    "\n",
    "\n",
    "def randomized_partition(a, p, r):\n",
    "    x = random.randint(p, r - 1)\n",
    "    a[x], a[r - 1] = a[r - 1], a[x]\n",
    "    return partition(a, p, r)\n",
    "\n",
    "\n",
    "def randomized_select(a, p, r, i):\n",
    "    while True:\n",
    "        if p + 1 == r:\n",
    "            return a[p]\n",
    "        q = randomized_partition(a, p, r)\n",
    "        k = q - p + 1\n",
    "        if i == k:\n",
    "            return a[q]\n",
    "        if i < k:\n",
    "            r = q\n",
    "        else:\n",
    "            p = q + 1\n",
    "            i -= k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.2-4\n",
    "\n",
    "> Suppose we use RANDOMIZED-SELECT to select the minimum element of the array $A = \\langle 3; 2; 9; 0; 7; 5; 4; 8; 6; 1 \\rangle$. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED-SELECT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Select 9, 8, 7, 6, 5, 4, 3, 2, 1."
   ]
  }
 ],
 "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
}