Chapter_20_van_Emde_Boas_Trees/exercises_20.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 20.2 A recursive structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-1\n",
    "\n",
    "> Write pseudocode for the procedures PROTO-VEB-MAXIMUM and PROTO-VEBPREDECESSOR."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "\n",
    "class ProtoVEB:\n",
    "    def __init__(self, u):\n",
    "        self.u = u\n",
    "        self.sqrt = int(math.sqrt(u))\n",
    "        if self.is_leaf():\n",
    "            self.a = [0, 0]\n",
    "        else:\n",
    "            self.summary = ProtoVEB(self.sqrt)\n",
    "            self.cluster = []\n",
    "            for _ in xrange(self.sqrt):\n",
    "                self.cluster.append(ProtoVEB(self.sqrt))\n",
    "\n",
    "    def is_leaf(self):\n",
    "        return self.u == 2\n",
    "\n",
    "    def high(self, x):\n",
    "        return x / self.sqrt\n",
    "\n",
    "    def low(self, x):\n",
    "        return x % self.sqrt\n",
    "\n",
    "    def index(self, x, y):\n",
    "        return x * self.sqrt + y\n",
    "\n",
    "    def member(self, x):\n",
    "        if self.is_leaf():\n",
    "            return self.a[x]\n",
    "        return self.cluster[self.high(x)].member(self.low(x))\n",
    "\n",
    "    def minimum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] > 0:\n",
    "                return 0\n",
    "            if self.a[1] > 0:\n",
    "                return 1\n",
    "            return None\n",
    "        min_idx = self.summary.minimum()\n",
    "        if min_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[min_idx].minimum()\n",
    "        return self.index(min_idx, offset)\n",
    "\n",
    "    def maximum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[1] > 0:\n",
    "                return 1\n",
    "            if self.a[0] > 0:\n",
    "                return 0\n",
    "            return None\n",
    "        max_idx = self.summary.maximum()\n",
    "        if max_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[max_idx].maximum()\n",
    "        return self.index(max_idx, offset)\n",
    "\n",
    "    def predecessor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] == 1 and x == 1:\n",
    "                return 0\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].predecessor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        pred_idx = self.summary.predecessor(self.high(x))\n",
    "        if pred_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[pred_idx].maximum()\n",
    "        return self.index(pred_idx, offset)\n",
    "\n",
    "    def successor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 0 and self.a[1] == 1:\n",
    "                return 1\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].successor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        succ_idx = self.summary.successor(self.high(x))\n",
    "        if succ_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[succ_idx].minimum()\n",
    "        return self.index(succ_idx, offset)\n",
    "\n",
    "    def insert(self, x):\n",
    "        if self.is_leaf():\n",
    "            self.a[x] = 1\n",
    "        else:\n",
    "            self.summary.insert(self.high(x))\n",
    "            self.cluster[self.high(x)].insert(self.low(x))\n",
    "\n",
    "    def display(self, space=0, summary=False):\n",
    "        if self.is_leaf():\n",
    "            if summary:\n",
    "                print(' ' * space + 'S ' + str(self.u) + ' ' + str(self.a))\n",
    "            else:\n",
    "                print(' ' * space + 'C ' + str(self.u) + ' ' + str(self.a))\n",
    "        else:\n",
    "            if summary:\n",
    "                print(' ' * space + 'S ' + str(self.u))\n",
    "            else:\n",
    "                print(' ' * space + 'C ' + str(self.u))\n",
    "            self.summary.display(space + 2, True)\n",
    "            for c in self.cluster:\n",
    "                c.display(space + 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-2\n",
    "\n",
    "> Write pseudocode for PROTO-VEB-DELETE. It should update the appropriate summary bit by scanning the related bits within the cluster. What is the worst-case running time of your procedure?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "    def delete(self, x):\n",
    "        if self.is_leaf():\n",
    "            self.a[x] = 0\n",
    "        else:\n",
    "            self.cluster[self.high(x)].delete(self.low(x))\n",
    "            if self.cluster[self.high(x)].minimum() is None:\n",
    "                self.summary.delete(self.high(x))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(u) = 2T(\\sqrt{u}) + \\Theta(\\lg \\sqrt{u}) = \\Theta(\\lg u \\lg \\lg u)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-3\n",
    "\n",
    "> Add the attribute $n$ to each proto-vEB structure, giving the number of elements currently in the set it represents, and write pseudocode for PROTO-VEB-DELETE that uses the attribute $n$ to decide when to reset summary bits to 0. What is the worst-case running time of your procedure? What other procedures need to change because of the new attribute? Do these changes affect their running times?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "    def insert(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[x] == 0:\n",
    "                self.a[x] = 1\n",
    "                self.n += 1\n",
    "                return True\n",
    "            return False\n",
    "        new_elem = self.cluster[self.high(x)].insert(self.low(x))\n",
    "        if new_elem:\n",
    "            self.n += 1\n",
    "        self.summary.insert(self.high(x))\n",
    "        return new_elem\n",
    "\n",
    "    def delete(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[x] == 1:\n",
    "                self.a[x] = 0\n",
    "                self.n -= 1\n",
    "                return True\n",
    "            return False\n",
    "        del_elem = self.cluster[self.high(x)].delete(self.low(x))\n",
    "        if del_elem:\n",
    "            self.n -= 1\n",
    "        if self.cluster[self.high(x)].n == 0:\n",
    "            self.summary.delete(self.high(x))\n",
    "        return del_elem\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Worst-case: $T(u) = 2T(\\sqrt{u}) + O(1) = \\Theta(\\lg n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-4\n",
    "\n",
    "> Modify the proto-vEB structure to support duplicate keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProtoVEB:\n",
    "    def __init__(self, u):\n",
    "        self.u = u\n",
    "        self.n = 0\n",
    "        self.sqrt = int(math.sqrt(u))\n",
    "        if self.is_leaf():\n",
    "            self.a = [0, 0]\n",
    "        else:\n",
    "            self.summary = ProtoVEB(self.sqrt)\n",
    "            self.cluster = []\n",
    "            for _ in xrange(self.sqrt):\n",
    "                self.cluster.append(ProtoVEB(self.sqrt))\n",
    "\n",
    "    def is_leaf(self):\n",
    "        return self.u == 2\n",
    "\n",
    "    def high(self, x):\n",
    "        return x / self.sqrt\n",
    "\n",
    "    def low(self, x):\n",
    "        return x % self.sqrt\n",
    "\n",
    "    def index(self, x, y):\n",
    "        return x * self.sqrt + y\n",
    "\n",
    "    def member(self, x):\n",
    "        if self.is_leaf():\n",
    "            return self.a[x]\n",
    "        return self.cluster[self.high(x)].member(self.low(x))\n",
    "\n",
    "    def minimum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] > 0:\n",
    "                return 0\n",
    "            if self.a[1] > 0:\n",
    "                return 1\n",
    "            return None\n",
    "        min_idx = self.summary.minimum()\n",
    "        if min_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[min_idx].minimum()\n",
    "        return self.index(min_idx, offset)\n",
    "\n",
    "    def maximum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[1] > 0:\n",
    "                return 1\n",
    "            if self.a[0] > 0:\n",
    "                return 0\n",
    "            return None\n",
    "        max_idx = self.summary.maximum()\n",
    "        if max_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[max_idx].maximum()\n",
    "        return self.index(max_idx, offset)\n",
    "\n",
    "    def predecessor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] > 0 and x == 1:\n",
    "                return 0\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].predecessor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        pred_idx = self.summary.predecessor(self.high(x))\n",
    "        if pred_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[pred_idx].maximum()\n",
    "        return self.index(pred_idx, offset)\n",
    "\n",
    "    def successor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 0 and self.a[1] > 0:\n",
    "                return 1\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].successor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        succ_idx = self.summary.successor(self.high(x))\n",
    "        if succ_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[succ_idx].minimum()\n",
    "        return self.index(succ_idx, offset)\n",
    "\n",
    "    def insert(self, x):\n",
    "        self.n += 1\n",
    "        if self.is_leaf():\n",
    "            self.a[x] += 1\n",
    "        else:\n",
    "            self.cluster[self.high(x)].insert(self.low(x))\n",
    "            self.summary.insert(self.high(x))\n",
    "\n",
    "    def delete(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[x] > 0:\n",
    "                self.a[x] -= 1\n",
    "                self.n -= 1\n",
    "                return True\n",
    "            return False\n",
    "        del_elem = self.cluster[self.high(x)].delete(self.low(x))\n",
    "        if del_elem:\n",
    "            self.n -= 1\n",
    "            self.summary.delete(self.high(x))\n",
    "        return del_elem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-5\n",
    "\n",
    "> Modify the proto-vEB structure to support keys that have associated satellite data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProtoVEB:\n",
    "    def __init__(self, u):\n",
    "        self.u = u\n",
    "        self.n = 0\n",
    "        self.sqrt = int(math.sqrt(u))\n",
    "        if self.is_leaf():\n",
    "            self.a = [0, 0]\n",
    "            self.data = [None, None]\n",
    "        else:\n",
    "            self.summary = ProtoVEB(self.sqrt)\n",
    "            self.cluster = []\n",
    "            for _ in xrange(self.sqrt):\n",
    "                self.cluster.append(ProtoVEB(self.sqrt))\n",
    "\n",
    "    def is_leaf(self):\n",
    "        return self.u == 2\n",
    "\n",
    "    def high(self, x):\n",
    "        return x / self.sqrt\n",
    "\n",
    "    def low(self, x):\n",
    "        return x % self.sqrt\n",
    "\n",
    "    def index(self, x, y):\n",
    "        return x * self.sqrt + y\n",
    "\n",
    "    def member(self, x):\n",
    "        if self.is_leaf():\n",
    "            return self.a[x]\n",
    "        return self.cluster[self.high(x)].member(self.low(x))\n",
    "\n",
    "    def get_data(self, x):\n",
    "        if self.is_leaf():\n",
    "            return self.data[x]\n",
    "        return self.cluster[self.high(x)].get_data(self.low(x))\n",
    "\n",
    "    def minimum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] == 1:\n",
    "                return 0\n",
    "            if self.a[1] == 1:\n",
    "                return 1\n",
    "            return None\n",
    "        min_idx = self.summary.minimum()\n",
    "        if min_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[min_idx].minimum()\n",
    "        return self.index(min_idx, offset)\n",
    "\n",
    "    def maximum(self):\n",
    "        if self.is_leaf():\n",
    "            if self.a[1] == 1:\n",
    "                return 1\n",
    "            if self.a[0] == 1:\n",
    "                return 0\n",
    "            return None\n",
    "        max_idx = self.summary.maximum()\n",
    "        if max_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[max_idx].maximum()\n",
    "        return self.index(max_idx, offset)\n",
    "\n",
    "    def predecessor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[0] == 1 and x == 1:\n",
    "                return 0\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].predecessor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        pred_idx = self.summary.predecessor(self.high(x))\n",
    "        if pred_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[pred_idx].maximum()\n",
    "        return self.index(pred_idx, offset)\n",
    "\n",
    "    def successor(self, x):\n",
    "        if self.is_leaf():\n",
    "            if x == 0 and self.a[1] == 1:\n",
    "                return 1\n",
    "            return None\n",
    "        offset = self.cluster[self.high(x)].successor(self.low(x))\n",
    "        if offset is not None:\n",
    "            return self.index(self.high(x), offset)\n",
    "        succ_idx = self.summary.successor(self.high(x))\n",
    "        if succ_idx is None:\n",
    "            return None\n",
    "        offset = self.cluster[succ_idx].minimum()\n",
    "        return self.index(succ_idx, offset)\n",
    "\n",
    "    def insert(self, x, data):\n",
    "        if self.is_leaf():\n",
    "            if self.a[x] == 0:\n",
    "                self.a[x] = 1\n",
    "                self.data[x] = data\n",
    "                self.n += 1\n",
    "                return True\n",
    "            return False\n",
    "        new_elem = self.cluster[self.high(x)].insert(self.low(x), data)\n",
    "        if new_elem:\n",
    "            self.n += 1\n",
    "        self.summary.insert(self.high(x), None)\n",
    "        return new_elem\n",
    "\n",
    "    def delete(self, x):\n",
    "        if self.is_leaf():\n",
    "            if self.a[x] == 1:\n",
    "                self.a[x] = 0\n",
    "                self.data[x] = None\n",
    "                self.n -= 1\n",
    "                return True\n",
    "            return False\n",
    "        del_elem = self.cluster[self.high(x)].delete(self.low(x))\n",
    "        if del_elem:\n",
    "            self.n -= 1\n",
    "        if self.cluster[self.high(x)].n == 0:\n",
    "            self.summary.delete(self.high(x))\n",
    "        return del_elem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-6\n",
    "\n",
    "> Write pseudocode for a procedure that creates a proto-vEB$(u)$ structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See exercise 20.2-1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-7\n",
    "\n",
    "> Argue that if line 9 of PROTO-VEB-MINIMUM is executed, then the proto-vEB structure is empty."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 20.2-8\n",
    "\n",
    "> Suppose that we designed a proto-vEB structure in which each _cluster_ array had only $u^{1/4}$ elements. What would the running times of each operation be?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are $u^{3/4}$ clusters in each proto-vEB.\n",
    "\n",
    "MEMBER/INSRT: $T(u) = T(u^{1/4}) + O(1) = \\Theta(\\lg \\log_4 u) = \\Theta(\\lg \\lg u)$.\n",
    "\n",
    "MINIMUM/MAXIMUM: $T(u) = T(u^{1/4}) + T(u^{3/4}) + O(1) = \\Theta(\\lg u)$.\n",
    "\n",
    "SUCCESSOR/PREDECESSOR/DELETE: $T(u) = T(u^{1/4}) + T(u^{3/4}) + \\Theta(\\lg u^{1/4}) = \\Theta(\\lg u \\lg \\lg u)$."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}