Chapter_21_Data_Structures_for_Disjoint_Sets/problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21-1 Off-line minimum\n",
    "\n",
    "> The __*off-line minimum problem*__ asks us to maintain a dynamic set $T$ of elements from the domain $\\{1, 2, \\dots, n\\}$ under the operations INSERT and EXTRACT-MIN. We are given a sequence $S$ of $n$ INSERT and $m$ EXTRACT-MIN calls, where each key in $\\{1, 2, \\dots, n\\}$ is inserted exactly once. We wish to determine which key is returned by each EXTRACT-MIN call. Specifically, we wish to fill in an array $extracted[1 \\dots m]$, where for $i = 1, 2, \\dots, m$, $extracted[i]$ is the key returned by the $i$th EXTRACT-MIN call. The problem is \"off-line\" in the sense that we are allowed to process the entire sequence $S$ before determining any of the returned keys.\n",
    "\n",
    "> __*a*__. In the following instance of the off-line minimum problem, each operation INSERT$(i)$ is represented by the value of $i$ and each EXTRACT-MIN is represented by the letter E:\n",
    "\n",
    "> 4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5.\n",
    "\n",
    "> Fill in the correct values in the _extracted_ array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4, 3, 2, 6, 8, 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> To develop an algorithm for this problem, we break the sequence $S$ into homogeneous subsequences. That is, we represent $S$ by\n",
    "\n",
    "> $I_1, E, I_2, E, I_3, \\dots, I_m, E, I_{m+1}$\n",
    "\n",
    "> where each $E$ represents a single EXTRACT-MIN call and each $\\text{I}_j$ represents a (possibly empty) sequence of INSERT calls. For each subsequence $\\text{I}_j$ , we initially place the keys inserted by these operations into a set $K_j$ , which is empty if $\\text{I}_j$ is empty. We then do the following:\n",
    "\n",
    "> ```\n",
    "OFF-LINE-MINIMUM(m, n)\n",
    "1  for i = 1 to n\n",
    "2       determine j such that i \\in K_j\n",
    "3       if j \\ne m + 1\n",
    "4            extracted[j] = i\n",
    "5            let l be the smallest value greater than j\n",
    "                   for which set K_l exists\n",
    "6            K_l = K_j \\cup K_l , destroying K_j\n",
    "7  return extracted \n",
    "```\n",
    "\n",
    "> __*b*__. Argue that the array extracted returned by OFF-LINE-MINIMUM is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Greedy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Describe how to implement OFF-LINE-MINIMUM efficiently with a disjoint-set data structure. Give a tight bound on the worst-case running time of your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DisjointSetForest:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.link(self.find_set(x), self.find_set(y))\n",
    "\n",
    "    def link(self, x, y):\n",
    "        self.p[x] = y\n",
    "\n",
    "    def find_set(self, x):\n",
    "        if x != self.p[x]:\n",
    "            self.p[x] = self.find_set(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "\n",
    "def off_line_minimum(q, n):\n",
    "    pos = [-1] * (n + 1)\n",
    "    m = 0\n",
    "    for v in q:\n",
    "        if v == 'E':\n",
    "            m += 1\n",
    "        else:\n",
    "            pos[v] = im = m\n",
    "    ds = DisjointSetForest(m + 1)\n",
    "    extracted = [None] * m\n",
    "    for i in xrange(1, n + 1):\n",
    "        j = ds.find_set(pos[i])\n",
    "        if j < m:\n",
    "            extracted[j] = i\n",
    "            ds.link(j, j + 1)\n",
    "    return extracted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21-2 Depth determination\n",
    "\n",
    "> In the __*depth-determination problem*__, we maintain a forest $\\mathcal{F} = \\{T_i\\}$ of rooted trees under three operations:\n",
    "\n",
    "> MAKE-TREE$(v)$ creates a tree whose only node is $v$.\n",
    "\n",
    "> FIND-DEPTH$(v)$ returns the depth of node $v$ within its tree.\n",
    "\n",
    "> GRAFT$(r, v)$ makes node $r$, which is assumed to be the root of a tree, become the child of node $v$, which is assumed to be in a different tree than $r$ but may or may not itself be a root.\n",
    "\n",
    "> __*a*__. Suppose that we use a tree representation similar to a disjoint-set forest: $v.p$ is the parent of node $v$, except that $v.p = v$ if $v$ is a root. Suppose further that we implement GRAFT$(r, v)$ by setting $r.p = v$ and FIND-DEPTH$(v)$ by following the find path up to the root, returning a count of all nodes other than $v$ encountered. Show that the worst-case running time of a sequence of $m$ MAKE-TREE, FIND-DEPTH, and GRAFT operations is $\\Theta(m^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$m/3$ MAKE-TREE, $m/3$ GRAFT to make a chain, $m/3$ FIND-DEPTH."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> By using the union-by-rank and path-compression heuristics, we can reduce the worst-case running time. We use the disjoint-set forest $\\mathcal{S} = \\{S_i\\}$, where each set $S_i$ (which is itself a tree) corresponds to a tree $T_i$ in the forest $\\mathcal{F}$. The tree structure within a set $S_i$, however, does not necessarily correspond to that of $T_i$. In fact, the implementation of $S_i$ does not record the exact parent-child relationships but nevertheless allows us to determine any node's depth in $T_i$.\n",
    "\n",
    "> The key idea is to maintain in each node $v$ a \"pseudodistance\" $v.d$, which is defined so that the sum of the pseudodistances along the simple path from $v$ to the root of its set $S_i$ equals the depth of $v$ in $T_i$. That is, if the simple path from $v$ to its root in $S_i$ is $v_0, v_1, \\dots, v_k$, where $v_0 = v$ and $v_k$ is $S_i$'s root, then the depth of $v$ in $T_i$ is $\\sum_{j=0}^k v_j.d$.\n",
    "\n",
    "> __*b*__. Give an implementation of MAKE-TREE."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self):\n",
    "        self.d = 0\n",
    "        self.p = self\n",
    "        self.rank = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Show how to modify FIND-SET to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudodistances correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_depth(v):\n",
    "    if v == v.p:\n",
    "        return (v.d, v)\n",
    "    (pd, p) = find_depth(v.p)\n",
    "    d = v.d + pd\n",
    "    v.d = d - p.d\n",
    "    v.p = p\n",
    "    return (d, p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Show how to implement GRAFT$(r, v)$, which combines the sets containing $r$ and $v$, by modifying the UNION and LINK procedures. Make sure that your implementation updates pseudodistances correctly. Note that the root of a set $S_i$ is not necessarily the root of the corresponding tree $T_i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graft(r, v):\n",
    "    (vd, vp) = find_depth(v)\n",
    "    if r.rank <= vp.rank:\n",
    "        r.d = vd + 1\n",
    "        r.p = vp\n",
    "        if r.rank == vp.rank:\n",
    "            vp.rank += 1\n",
    "    else:\n",
    "        r.d = vd + 1\n",
    "        vp.d = vp.d - r.d\n",
    "        vp.p = r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. Give a tight bound on the worst-case running time of a sequence of $m$ MAKE-TREE, FIND-DEPTH, and GRAFT operations, $n$ of which are MAKE-TREE operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(m\\alpha(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21-3 Tarjan's off-line least-common-ancestors algorithm\n",
    "\n",
    "> The least common ancestor of two nodes $u$ and $v$ in a rooted tree $T$ is the node $w$ that is an ancestor of both $u$ and $v$ and that has the greatest depth in $T$. In the off-line least-common-ancestors problem, we are given a rooted tree $T$ and an arbitrary set $P = \\{\\{u, v\\}\\}$ of unordered pairs of nodes in $T$, and we wish to determine the least common ancestor of each pair in $P$.\n",
    "\n",
    "> To solve the off-line least-common-ancestors problem, the following procedure performs a tree walk of $T$ with the initial call LCA$(T.root)$. We assume that each node is colored WHITE prior to the walk.\n",
    "\n",
    "> ```\n",
    "LCA(u)\n",
    " 1  MAKE-SET(u)\n",
    " 2  FIND-SET(u).ancestor = u\n",
    " 3  for each child v of u in T\n",
    " 4       LCA(v)\n",
    " 5       UNION(u, v)\n",
    " 6       FIND-SET(u).ancestor = u\n",
    " 7  u.color = BLACK\n",
    " 8  for each node v such that {u, v} \\in P\n",
    " 9       if v.color == BLACK\n",
    "10            print \"The least common ancestor of\"\n",
    "                    u \"and\" v \"is\" FIND-SET(v).ancestor\n",
    "```\n",
    "\n",
    "> __*a*__. Argue that line 10 executes exactly once for each pair $\\{u, v\\} \\in P$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each node is visited exactly once, if $u$ is visited before $v$, then $v$ is WHITE, line 10 will not be executed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Argue that at the time of the call LCA$(u)$, the number of sets in the disjoint-set data structure equals the depth of $u$ in $T$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LCA(v) increase the number of sets by 1, UNION(u, v) decrease the number of sets by 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. Prove that LCA correctly prints the least common ancestor of $u$ and $v$ for each pair $\\{u, v\\} \\in P$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The visited nodes always point to the current chain of search path."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. Analyze the running time of LCA, assuming that we use the implementation of the disjoint-set data structure in Section 21.3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(n^2 \\alpha(n))$"
   ]
  }
 ],
 "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
}