TDA - Greedy.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<script>\n",
       "  function $$(id) {\n",
       "    return Array.prototype.slice.call($(id));\n",
       "  }\n",
       "\n",
       "  function code_toggle() {\n",
       "    $$('div.input').forEach(input => {\n",
       "        input.style.display = code_shown ? 'none' : 'flex'\n",
       "    })\n",
       "\n",
       "    $('#toggleButton').val(code_shown ? 'Show Code' : 'Hide Code')\n",
       "    code_shown = !code_shown\n",
       "  }\n",
       "\n",
       "  $( document ).ready(function(){\n",
       "    code_shown=false;\n",
       "    $('div.input').hide()\n",
       "  });\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "\n",
    "<script>\n",
    "  function $$(id) {\n",
    "    return Array.prototype.slice.call($(id));\n",
    "  }\n",
    "\n",
    "  function code_toggle() {\n",
    "    $$('div.input').forEach(input => {\n",
    "        input.style.display = code_shown ? 'none' : 'flex'\n",
    "    })\n",
    "\n",
    "    $('#toggleButton').val(code_shown ? 'Show Code' : 'Hide Code')\n",
    "    code_shown = !code_shown\n",
    "  }\n",
    "\n",
    "  $( document ).ready(function(){\n",
    "    code_shown=false;\n",
    "    $('div.input').hide()\n",
    "  });\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Teoría de Algoritmos I - Greedy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tardos 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample.\n",
    "\n",
    "> Let G be an arbitrary connected, undirected graph with a distinct cost c(e) on every edge e. Suppose e' is the cheapest edge in G; that is, c(e') < c(e) for every edge e != e∗. Then there is a minimum spanning tree T of G that contains the edge e'.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "True. For example, if we use Kruskal the first edge will be e'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "\n",
    "For each of the following two statements, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample.\n",
    "\n",
    "> (a) Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph G, with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost c_e by its square, c_e^2, thereby creating a new instance of the problem with the same graph but different costs.\n",
    "True or false? T must still be a minimum spanning tree for this new instance.\n",
    "\n",
    "> (b) Suppose we are given an instance of the Shortest s-t Path Problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost c_e by its square, c_e^2, thereby creating a new instance of the problem with the same graph but different costs.\n",
    "True or false? P must still be a minimum-cost s-t path for this new instance.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "**(a)** \n",
    "True. The relative order between the edges is the same.\n",
    "\n",
    "**(b)** \n",
    "False. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "tags": [
     "remove_input"
    ]
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAe0AAAHVCAYAAADcnaM7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XeAFPX9PvBnZrZf75WrHEfvvXOA9N6xJ7ao0fToN83E\nxKhJ/JpmYokKCkgRkA7Sq/Rejnoc7Xov2+f3h7/wDaEM4N3tZ3af1587z+e9d4ifh9mdnZVUVQUR\nERGJT/b1D0BERER3h6VNRESkEyxtIiIinWBpExER6QRLm4iISCdY2kRERDrB0iYiItIJljYREZFO\nsLSJiIh0gqVNRESkEyxtIiIinWBpExER6QRLm4iISCdY2kRERDrB0iYiItIJljYREZFOsLSJiIh0\ngqVNRESkEyxtIiIinWBpExER6QRLm4iISCdY2kRERDrB0iYiItIJljYREZFOsLSJiIh0gqVNRESk\nEyxtIiIinWBpExER6YTB1z9AYzNHxPV3VhRtMVuD8iHBG5WUsnPg5EdWrnjvre847fVREuA2GI1l\n7Tp3/uxq3vn00uLizhJUuwxv3eReqW97q4o8K4+WTzDIqDPKqOsQr+xbOt2W2++j2m5BRthjguTq\ndrFy5U/6mMt9/bsSEVGTsOOVygpfPLHfl7YprbPFeWgNmmVlp7Tu3A0Wmy3NAufMgWMnwuV0ovTa\nVRzavhlh8c0GxKS1QEVJETweDzwuF+pbt5vqdNgRL+1XXU6H2+20ewsiI+2JH5w1ud0W1VPrhrPQ\nIW+rCK9wdR+7bfa8ZR0vXS1KNBmVerNBrnnnWx3/+tXRC5Ebjpe0izR7S6NtUsUjHYxHBqcbytad\nd0f1TlYqomyy29d/RkREdE8KAOz1xRNLqqr64nmbTNpLKzPclYXniue9hP4PDEdK8+bXj127eAGb\nlizAoAlTkZCarjlLK+92OeGor4fDbofDXg/V68XGxfOR1rI1jEaj215b7e7YuVNRTFRI6az3P25t\ntztMRoPiaJ8Zf+AXk9ss/f3cnX3cjnpPnA1F6RFS4V9HWPcX1XoNkVbJbZClBv1zISKi+1aAVypZ\n2o0h7aWVGQDOeWrLEW0FWjqPw2azNnhh309eVb2w19cDqoqKkmKsXzQXaS3bQJHghMdtHz122MkN\nq1ZFHTlyKt1mMVYFW5Ti10fHvRPlLqqce9TRpnW0UjgwTbnWI1mpYqkTETUZlnZj+XdpA4Cqqiid\n92PEh1tx+cwp5Eyc5rPCvpe8y+lEbVUlaiorEJ+ShvMnjrj3blwnWy0WZ11drTKgW5uvpvVN2/a7\nD9cNjza78lJD1EsD0gznnu9uytN8ciIiulc+K22/f0/7P0mShIhxP8OlT36I5MwWiE9J01zj68IG\nAKPJhPDoGIRHx+DaxQvYt2m9IWfidCSkplsAQFW9/bZ5vf1SextQWVba6WBJkSO/IqSs2NX1wHvv\nfdqpvr7eEBsknc0MdR9f/aBtxcUKryk+WHKZDZJ//4uNiMjPBFRpA4ASFIHYR/4XhUt/i6qqGoSF\nhdw2K0Jh301ekmQoioyM1u0AQAJgAZC4N+9CYnmNAx37DoJiMMSV1td3f9HZfcC2rctNR4+cbBYW\nZCqMsannPhylvBtpgbvMrhp6JRuqNX8QIiLyiYB6efw/qaqKUNQi8vRSZLZsCUm68T1hvRT2/eYd\n9npUlBSjvKgQrdp3qD61d1v1rq3b401GpT462Hjx6c7KrB90Q+6yXHfs5NaGAr5nTkR0Hd/Tbiy3\nK20A8DrtKJn/MpJjw9F3+EhI0tf3mvF1ofoqP3D8FISER6CsqADR8Yles2q/sujjj2JdLqcUFWy6\n9EC6vHTWGGXLxgvu8P6pSgWLnIgCFEu7sdyptAHA66hD6aJfIT7Civ4jx6Dw0kUhC9WX+fraGpQW\nXIMlKMiruOoKV8z/LEaC6okJMZ7vGuvZtHSaZU2FXVXCLZJH8wmJiPSPpd1YtEob+PqM23HwC3RI\nsmLb4k91Vai+yodFRqH42hWoXo+7XcvMMws/+ldUTXWVkhgsHW8X5T64YIptg+ZAIiJ9Ymk3lrsp\n7X/z5u2BemAhhkyYAllR7pgVuVB9kfd6PSgvLkLR5Uuoqyit7dgm48SmNeuivY7auuww156cdOX4\n93qaztqMklfzyYiIxMaPfIlASu6Isn0rsX7pIgweNwmK4dZ/PL4uSBHzsqwgKi4BUXEJuHbxQtD8\nzxZ06zV8NFSviqv551u8dSTP5ek4YtHV/XurT5w6FzY4XTnyXDfjWd7GlYjo7vFM+7+oHhfKlr2B\nKKMDg8eOv+m4CAWp53xpYQHOHjngLsg766ysqDB+d3iLv42Jvnxw/xVn1LPdTBd4Jk5EOsCXxxvL\nvZY2AKgeN+SKS+gRXQOzpxYGgxGA7wvP3/L5Z05h24ql6NJ/kOP4nh3e+tpaOTHMePz7XdWPX+jB\nu7kRkbD48rhIJMUANSodm4+ug3p0BYZNmY6Sa1eFKjx/yG9f+cW/byVrbtmlB+qqq3Al73znr5IS\nUw9dLMldOH9p6/Rw7OmX5N39w97mIxkRskNzMBGRH+OZ9h2oXg/K1/wFSuFJ1FeV6+Ze5f6QV1Uv\nyoqKcOX8WfXC8UOOEItS9LMxme99vm5P2rQ2yv6H2huv8HPiROQjPjvTln3xpHohyQoiRrwIT1xL\nJLfuqJvC84e8JMmIiotHTGKSVFtTa2nVb3jKZnO/316wtXnk2XV4O+KPjtnTlqoPAIDDrbK9iSgg\n8Ez7LqiqCoPqREbZTsQGG2Cx2W6ZE6Xw/D2vqirKigqgyIonKdxy4oO//TUzIUQ53iPOtfWnfcz7\nOsQrtZrDiYjuH8+0RSZJEjyyGftzr2Ll3Nmor7u5E/RSeP6QlyQJUXEJCI+JVWqNoe3GPfmCzZbe\nqdvnZ5TvT98Y89s1nm7Nv/VFfe9159yRmk9ERKQjvBDtHoT0nolKjwcr5szCqBkPwxb89TeE6anw\n/DFfWVqCs0cPYfCkGXJCanrmArf3rW3OQsecBblyqMV7bWiqd9HciZbNmoOIiATH0r4HkiQhvP8j\nqDJbUVADZASLV2DMf/1+eP9xU8wejxvXLuallLodT//SFd96zkezkpqZaw8+1824bUprY6HmcCIi\nwfA97fuleoB1r6Pg5EHkTJoubIEx/zVVVXF8zy4c3L5ZleB1ZyWEHjjwqPr7/HKnqXmkbNd8MiKi\n/8PPaeuOpKAqPBuS8QSCw8I14yIVWCDmC/LzcGTXNgyZPEOKa5ZitNfW9njeaft44ey3FRNcJd3j\nXGv+p59pe69kQ7XmMCIiH+GFaN9AaI/JsPWajuVzZqGuuuq2OdEKLNDzsqzAFhIKj2QIH/fU90La\nDx2ffhzNH39sc/TvNns6pLy61ZF9ucpr0hxMRNTE+PJ4A7BfPIzOqcGIQxlk+cZ/B4leYMzf6Gre\neWxaMt/rdbs8GVHGXdNbqitfGWg+qbmQiAIJXx7XM0tqBxxz1GLbnNcxdNwERMTEARCvkJjXzm9e\nuhA5E6fLYVHR8vnjR/utc9ZkJrmbzVv7xReWydk4Mr2tsUBzEBFRI+GZdgOqPbEF1RvfxfBpM+G0\n24UrJObvL6+qKvZuWO0+c+SgN8wiXxmX6Z373hjLbs2hROSv+C1fjaUpSxsAanN3oHbz+/Daa3mv\ncj/LezxuXD53BlUFVyps7vKT9QXnC8dlerb/pI/pNO+DThRQ+PK4vwjK7gNLWmc0qzsOG0o186IU\nEvPaeUUxwGS24OiB/eEDxk3uVWOJ876+d/fwP+xxVk7Mwkf/GmveqfmERETfAEu7EShmK/IqI7Fv\n/p8wdOIUxDdLvWVOpEJi/t7zSemZcvtefS3XLuZZilT307+zm5st+HRe7NQW3nU/7WvK5dk3ETU0\nfuSrkZhiMxAx5qf48vMFuJp3/qbjohcS83eXlyQZiWkZiE1vEXHam/iguUXfIa/vM74a85bzvRdW\n2ztrDiYiugcs7UZkTeuIyPE/w7HzN15wrJdCYv7e8gaDEe169pX6jp5kqXUh/kjE4BdfrRw9qfMH\njqdmH3Ymaj4REZEGXojWRCIKdyOm9jwMRqMQBcN80+Qd9noc3bXNk3twryfaJp/9cXf13Rd7mi9o\nDiIikfHq8cYiSmk7ruaiZNGvIHmcGDJ5ppAFw3zj5d1uFy6cOIbk2LAzbQxXV+/YvNn6vw+Y1mdH\nK/Wag4lINPw+bX9nTsxG9NTfQlXMcNRr79N6KiTmtfMGgxFZ7TvBGp+RdUhp/cKh+vhH2/yzfk7H\n9+1Pb85za9+8nogIvHq8SZnjmyNm+msoUcuQCgkSbv0qh68LhvnGzddWVaK8tNTUb/RElFy7MmyR\nJcN07MyejVUF+a7/6Wc+rTmAiAIWS7uJmWLTUYl0rNnwDjKiTcju0OmG46IVDPONm89o3c5QDwxd\nUakM3r77quvP+51Xxzf3zP3LcMses0Hy7/euiOie8eVxH5Haj8WebVtx8sC+64+JXjDMN14+KT1T\nnvL8D82tB45JX3Yt5nvvVvXps/qsJ7Ko1st/WBPRddwQfMQYlYyYGW9g/2cvIzQqGjJU3RQM842T\nl2UFGa3bIqN126A1Fy/85H+WSR6P0+7okywt+Oco86rmkbJd84mIyK/xTNuHjBEJiH3kbVyL6obN\nSxfqqmCYb/x8/7GTlWEPPmE7b8yc0X22+o8ST5DJ7eUr5kSBjGfaPqYEhaNCDQNCYlBw+ZLmpi5q\nwTDfePlBE2eYXU6n+Wce5YOVH71TG6dUH/zDYGVBTrqhQnMgEfkVnmkLQJIkRE7+DU4cP4X9Wzfh\ndp+d10PBMN84eaPJBDeU8L6THkmyx7UfNmKe84NBn7qnaQ4lIr/C0haEITgSMTPewLnLxaitvflz\n3HoqGOYbLx8UGoaew0Yb+4yeaNpdIM38zsUhz/T82PX48tOuaM0nISLdY2kLRAkKR9T0N3DC0gGn\njx+/fsYtSmEwL05+15oVGDhuilQX3WpkXXynMZMXuf/Z7j3Hd9ecdUdqDiAi3eJ72gKqdBlwbu9+\nFF++iPTslrxIjfk75rvlDDO07dEHx77aPujDapspsur8h1UlhRiSYSjXHEhEusJ7jwvK66hFyfyf\nw12Wj8ETpyMxLUNzjR4KhvnGzxfknbOvXzRXbhsrr/3HCONn3ZOUas3hRHQveO9xupFsDkL0tN8h\noucURKW20MyLUhjM+z4fn5Zp6T1qgulosTS63yzHR6svGmM0n4CIdIEvjwtMNttg7TkdO4tOQznw\nGfoOGw5ZVm7KiVQYzIuR/2rtSgyZPEMKj44xfRFk/cPvV8w/aa28kPvJeNOK2CDZrTmEiITEM20d\ncIen4lqlExu/WAyvx3PDMRELg3lx8tagYLigREZ1HNznpDd5ZsbfnB9PX1Q/SHMQEQmJpa0DstGM\nqIm/Qqnbgq1rVl1/XPTCYF6cfGRsHIZOe9QyYPJDoXmRPR9e5Onf/uNDziTeYY1IX3ghmo6oHhfk\nqmvoHlGBirwT2LpssS4Kg3nx8lcunMPGz+d5Im3y+Z/0wN9/0Mt8XnMREf0bL0QjbZJihBqRgk37\nz2PTkoXoP2aiEAXAvP7yW75YhJxJM5TMnkOb/3yr9ObkZYZRmguJyOd4IZoOWTuNgf3qaRz8aifi\nmqXAaDLfNitiYTAvUD49U8ps094E1fvYU2ePJR/dtq7+k3GmBfxGMSIx8UxbhyRZQcSoH8IRnoGj\nh47dNid8YTAvRN5oNsNosZqrwluMKg7KGtv+PcdHUxbWD3a4VUlzKBE1KZa2TkmygvDhL6Cqy+PI\nv1YGR/2N9yvXS2EwL04+KDQMA8ZPNQ2e9ljQtvLop767N3F4Ua2Xr8YRCYSlrWOSJMMjGbEv9wpW\nzvsE9ro6AGIUAPP6zXvcLlRWVFovR/f6To9Fke9mveN8mfc0JxIDS9sPhPZ7FGpaD6yYOxt5uSeE\nKgDm9Z3vN+mhmKDmXbuPW+h6d+x8xwjNAUTUqPjSlx+QJAlhAx5HtTkIR/bvErYAmNdf3mgyo8vA\noUpW+86Ko7Jk6mxnTfHp7Wvqf5tjOa45kIgaHM+0/YQkSQjtNQ1BU97AmXMXUVtVece8HgqDeXHy\noZFRiEnPjlpZmfnLvxwyv5LyV8dvvsjld3gTNTWWtr9RzCi1pmLFnNmoqay4ZcTXBcC8fvPBYeHo\nNXKcuaBG7Tj1c9c/PzyKZppPQEQNhi+P+6HQHpNRrRiwfM4sjH/sCVhtQdePiVQAzOszv3XZYgyZ\nPBOhkVGmfcGWn63asHBbNvIO/26w5fafPySiBsEzbT8V0nU8wkb9GFWWJHi9X3/JiIgFwLx+80Eh\noXBIpsTK+K7T3j5g+FXLfzh+tOeKJ0RzEBHdN5a2HzM3a4fD9dFY+MG7OHPkoNAFwLx+8ylZ2Zj0\nzPfMSrMOvR78MviXblXmTVmIGglL288p1jBYes7EznWr0HXQUOELgHl95o1mM3o+MMrYd/oz2ROO\nD/5bwp8df/jsmCteczgR3ROWdgAIbjsY4cO/h8P79kNVvXfMilAAzOs3X3jpIr5cuapZeFq7rMeW\nu/82+BP7pGqHyn2GqIHwf6YAEdy6P8If+jPyvTGoKC2+ZUa0AmBen/mcidPQe8QYecy3njWdUZOm\n/qOgdXd+bzdRw2BpBxDZaMbxAieWfzoLhZfzbzgmagEwr998aEQkhk5/zJqbMPLldgti/tbzI/uj\nvJc50TfD0g4w5oQWiBj1I6z7fAEK8vMA6KMAmNd1Xur4wMSUa8aU0S3+4fzHG9sdWZpDieiWWNoB\nyJrRBRFjforjeSUibOjMB0DeFhyCwVMeMqd16Bn35xNhL+c5w2x8r5vo3vF/mgBlTesI9H0ah3Pz\n0bZHb10VAPP6zBfk5yH34D50HDQy+vuXB/+j2V8d7/1xpyNTcyERXcfSDnCeliNweM9u5J/JvWNO\ntAJgXt/5iKS0iI6Dx8T+fKv6Rq+P7I9U2FVFcwgRsbQDnSW5FaIm/xpbVq1A/plTt8yIXgDM6y8v\nSRIy27THhCe/a6qObjdijdqzJYubSBtLm2BOaIHoqa+iJLw9VPXGj+booQCY12/eFhKKHsPGBq2T\ne7/W/H35w6Gf2ic43CrvqEZ0GyxtAgCY4jJRHtUOq9Zuw5mjhwH4fkNnPnDykiRLbfoMjthyCY+m\n/NX5J37tJ9Gt8TOTdAO58yR8Nf9nKC8uxNkjB4XY0JkPjPye9WsweOJ0ufja5fRlHnncIOfej0NN\nqkdzMVEA4Zk23cAUnYKYGa/j1JEj6NhvkDAbOvOBkU9Mz0SH3gMUNO83bvDG7Hey3nG8dKLYY9Uc\nQhQgWNp0E2NkEuKf+CdcHaejprrmjlmRC4B5fedb9R2aoCS27tb9Q+e7r251ZGsOIwoALG26JcUW\nhmKEYfmCBTj81Y5bZvRUAMzrL280mdBn5Hhjj5GTwpdVZT912Rls0RxK5OdY2nRbkiQjcvKvcezw\nURzYvuWGY77e0JkPnHxadivEZHfO6vCB69PEPzv+sO6cO1LzCYj8FEub7sgQEo2YGW/i3KVi1NbZ\nAYi1oTMfOPnug0eYEtr1aj5ugeudZ1fau2ouJPJDvHqcNCnBEYic9nuc8FQAW97H6QN7kDNxmlAb\nOvOBkU9Mz1TiUzNsSzasfPE7tebn2gVVVGkOIfIjPNOmu1bhMiD31BnEpWUiPiVNMy96ATCvz3x8\ns1SMfOzZsL9KM//Y+l94iZ/ppkDC0qa7JluCEffwWyiutGPH2lVQVe9ts3opAOb1m3cr5vjgrB49\npy9x/50vl1OgYGnTPZEtwYie9hqqY9rDBeMtMyJs6Mz7f16SZLTr2Vfu2H+I9f1D3p//Yb+xheZw\nIp1jadM9k802mDqNx46rBmxbsxJe7/+dcYuyoTMfOPlD27cgZ+J0Oa/dd74/Y13o2M157nDNhUQ6\nxdKm++aObo6rZXZsWrYEXo9HyA2d+cDIJ2dmwQ5jUq6S+djIz1zv/GqTvZXmACIdkv77W538TdpL\nKzMAnPP1z+GvVLcTpUteRYTBiZJLF4Tc0JkPrPyls6exbdki58Pt5D+9N8q4S3MY0b0rwCuVe33x\nxCxt+sZUtwtq4Qm0UPORnBgLxXDnTxLqqQCY12e+uqIc4Wb1TJ/yFX8fGF54OTVcdmoOJrp7Pitt\nvjxO35hkMEJO6oAjVx1Yu2g+3C7XbbMibOjM+38+JDwCHmtk1msHgt5o+57jn/OPu+I0hxPpAEub\nGoy16wTUWuKwZuE8uJw3n9iIsqEzHzj5i2fOmFNad4p8dJn7L99bY++ouYhIcCxtajCSrCBi9I9Q\nH5KCkydO3XBMxA2def/P50ychp4PjJIHT3nImhefM7HcYzG4vf79liD5N97GlBqUJCuIGPl9lMOD\nvMvrkRgditLCa0Ju6MwHTv7rO/ildRy/2/3OtUPbzm152PhWQoh8+/dxiATFM21qcJIkwy0ZsT/3\nCpZ98iE2Lp4v9IbOfODk0zr0iHdHZnRr977r7TVn+W1hpD8sbWo0YQO/DaR0htEWjIiYWM28rzd0\n5v0/bzCaMHDCNFNa5z6JL2wL+rHmUCLBsLSp0UiShPAhz8LUbgRKHfwYGPNi5CVJQmxSipJfVNNm\n2uHu339sqb2v5hMQCYKlTY1KkiSE9JyK3JBu2LJuPepqqm/KiLShMx84+ZyJ0+CMajFo0Vnji30+\ndjzEC9RID1ja1CRU2YiyoFQs/3QWaqsqrz8u6obOfGDkI2PjMOZb3zGfsUeM6/CB+weaA4h8jKVN\nTSa013SYOozG8jmz4LDXC7+hMx8YeVtwCEY88oS55bAHO612dso8XOAJ0hxG5CMsbWpSoT0mIXTU\nT3Cp0surypkXJm8wGBGe0CzsLxdS3ug72/XOx4ecSZpDiXyApU1NzpzcBufMLSGbrbAFh2jmfb2h\nMx84+cT05qa09l3Dn1zp+svLG+xtNYcTNTGWNvmEITQWtt4PY+W8T1BeUnTbnEgbOvOBkT975JDU\nqf9g44qy1CecqoF7JAmFfyHJZ4LbD0XQgG9h48qVuNW3zYm4oTMfGPl2Pfqg+7iHMp7IH/GroXMc\nk3hlOYmCpU0+FdwmB2Ez3sJldwQqSoqvPy7yhs584OSdwfGd9pcHTe/0gfO7dS6V+yX5HP8Sks9J\nBhOOXHNgxZxZKL56WTcbOvP+nw8KCcWoR542lxpi+3f+0MM7qJHP8QtDSAiW5NYIG/F9rJ7/J8he\nNwZPniH8hs58YORNFgsemPGYua6suO0npQeyu3iP57eOUeo1hxM1ApY2CcPWvDsw5iew5u/UzYbO\nfGDkFcWAmjp72FNzj71pgrt4/gT1J8ObG8o0n4SogfHlcRKKLaMLpIHfxb7zFbhy4dxtcyJt6MwH\nTn7guClSi+79oiZ/7vrzhwf5WW5qeixtElKhEoeNy5bg0tnTNx0TdUNn3v/ziWkZaN+rv9IpZ2To\nX0/HPqW5mKiBsbRJSJZmbRE18ZfYvHIZLp07c/1xkTd05gMn36JDZ6nzhG93ejK395O8CQs1JZY2\nCcuc1ApRU15FWWR7qKqqmw2d+cDJX5Hjx/zvHvWVZ1bYu2kOJGoALG0Smjm+OUrCWmPZ0lVYv2ie\nrjZ05v0/n5CajgdmPGb6+BheenCJfYDmYKJviKVNumDq/QhgtKC6slIzK8qGznxg5N0uF1TIxvKk\nASOqPCZFcwHRN8DSJl0wxaQhZsbr2LN1C0oKC26bE21DZz4w8oMnTUdCx76tB6xO/vvQOfYJmguJ\n7hNLm3TDGNUMsY//DVdjeqO6qvqm46Ju6MwHTr5Fz5zEPUWWmf1nOWZoDiC6Dyxt0hXFGooibyiW\nfzYXR/d8df1xPWzozPt/Pjg0DCMffcp8tNI28YnVaj/NQUT3iKVNuiPJCqKm/hZHDhzA4V3bdbOh\nMx8YeVtwCEY/9ozZOujZsbNP21L5DWHUkFjapEuG0FhEz3gTuReuYvOyz3WzoTMfGHmTxYI62Zb9\no43qHzq+5/gui5saCkubdMsQEoWo6W8g/dE3UVVZdcvv5P5PomzozAdOvqqyynLFFTyg8wfO51jc\n1BBY2qR7VUoY9u/djz2b1t+2uEXc0Jn3/3zOxGkY/ejTpgpzYr+550LTNBcSaWBpk+4p1lBET38d\n5y9exVfr191U3KJu6MwHRt5ksWDojMdsu5s9/P0pSzGCZ9z0TbC0yS8o1hBET3sNVTHt4ZaM1x8X\nfUNnPnDy1W45fUuB7VtdPnA+y+Km+8XSJr8hW4JhaD8a2/I92LZmBa5eOKebDZ15/88bTWYMm/m4\n+aonbGC3fzmfYXHT/WBpk9/xxLbClZIabFg8HwPGTdbFhs58YORNFguGzfyWxRnTste24tBozcFE\n/4WlTX5HNlkRNeVVGBOycPH8ec28KBs684GRLysqwPnTZyJ+d7H9b/vPds7UXED0H1ja5JdkowXR\nk38DZ9dHUOOS4PG4b5kTbUNnPnDycS3aJR6psEwYMNsxTXMh0f/H0ia/JRlM8IQkYsPuU/hy8UK4\n3a4bjou8oTPv/3mLLQgjHvy2+WCpafKYzxyjNAcQgaVNASCox1RUGSKxbtF8uF1fF7foGzrzgZG3\nhYRixENPmMN7TephV43cj0kT/5KQ35MUAyLH/BS11gScPn1WNxs684GRDw4Lhykhu2P3pXF/fWhx\nfX/NgRTQWNoUECRZQcToH6OkxUTs/HIN+o2eoIsNnfnAyTfvPrDZotPSC8+urO+iOZgCFkubAoYk\nSXApNiC5Ew7s3A6n3X7HvEgbOvP+n7fX1UGFZPrXEbz88SFnkuYCCkgsbQo4YUOfhTu+LVbO+wSO\n+rpbZkTb0JkPjPzgSTMw+rGnTWWtp3eudqjcn+km/EtBAUeSJIQNfgZSdg7KnMabjou6oTMfGPnw\nqBgcqI9/Mvlvrg/nHnUlaA6ggMLSpoAkSRJCek7FKVsnbFqzFvW1NQDE39CZD4y82WpFu75DI55a\n5X5j4wV3uOYgChgsbQpoHtmE8qA0LJ8zCxdOHtfFhs58YOSzO3WVsrv2CXl4BX6uOYwChsHXPwCR\nL0mShLD81nGEAAAgAElEQVQ+M1Epy9i6cgFyxk/RxYbOfGDkO/QdqLTq1DlxUemWjEHW3Pwom3zr\nW/tRwGBpEwEI6zUdltT2sCaZ4PGUQlFu/7+GKBs68/6flyQJZaVlwY98ceqteKt778mnTa+ZDRK/\nHiyA8eVxov/PnNgaBypDsPD9f6KqrPSWGZE2dOYDJ99v1AS51hjZsdfHzqc0F5FfY2kT/QclNA6W\n7lOxYu5sVJQW33BM1A2def/PJ2dmYei0R8zna61Dfrje3UlzMfktljbRfwnpOAJBfR/F5tVroKpf\nvxIp8obOfGDkzVYbRj/+jNnU/8mBZ8tUs+YQ8kssbaJbCG4/FMFT38QlZyjOHDko/IbOfGDkzRYr\nrrqCB3X8l/vj17c7sjSHkd9haRPdhmQw4ciVOuxYtwqdB+QIv6EzHxh5g9GEXiPHB/16u/c3C0+4\n4jSHkl9haRPdgTWtI6LG/AT7tm5B0ZVLd8yKsKEzHxj5lKyWyGjb2fr0avU3moPJr7C0iTTYsnoi\nfOQPkHu1+rYZkTZ05gMjf/7EUbn7iAnhX9pbp1TYVUVzEfkFljbRXbBmdoOzy8PYk1uIaxcv3HBM\nxA2d+cDIJzVvaX1pq/J631nO59xefnw7ELC0ie5BsTkZ65d+jisXzgEQe0NnPjDyrXv1D77itPUb\nNc8xTnMA6R5Lm+geWFLaI3LCL7Bx2RIc3b1D+A2def/Pm8wWDJ32qHnrZfnhf+xzpmgOIl1jaRPd\nI0tya0RN/g2KPCEYyHuVMy9APiQ8AuOffN5U0+Ghbvwebv/G/7hE98GckAX0fBz7Dp3EhZPH75j1\n9YbOfGDkbcEh2FcR8kjyX50f7LvqCdYcTLrE0ib6Bow9H8L2L9fi7PGjtzwuyobOfGDkqyvKpXqX\nGj1mgftXPOP2T/yPSvQNmGIzED3tNezauB7lJSU3HBNtQ2c+MPI5E6dDCYtPGzbP/bDmItIdfjUn\n0TdkiklF/Lf/iSsWJwyVhxASFibshs58YOSj4xPNVld5Vp1ngWxTPF7NAaQbPNMmagCyJRgF7hAs\nmzcHu75cLfSGzrz/581WK7yhie3bzLb+nfco9y8sbaIGIhmMiJ72Gs6cPInUVm2F3dCZD5x8ZrcB\nSa/u8L6y7aI7THMY6QJLm6gBGcLiEPfI27hW6YLT5b5j1tcbOvP+n09t0RItOve0TVni+aXDrUqa\nQ0l4LG2iBmYIjUHE5Fdx2JOOU4cPXv9O7v8kwobOfGDkO/bLUdI7943dVRYepTmYhMfSJmok5S4T\nDuzZj31bNt5Q3CJt6Mz7f77w0kUc+mpX2EuHE195dKm9r+YCEhpLm6iRKEHhiJ7xOs6cy8fujV8C\nEG9DZz5w8vEtO6XMP6m+yFud6htLm6gRKbYwRE//PapiO+HKpcvCbujM+38+Ki4B3YeOMv10k/eV\n3BKPVXMACYmlTdTIFGsIlDbDcbQYiGmWhviUVM01ohcA8/rMZ7XvJLXpNTD4mCspRnMICYmlTdRE\nlFZDUVqnYsvK5fB6b3+/C70UAPP6zLfu3sey0jD4xW8vd/bWHEbCYWkTNRHZbEPUlFdRUOXE3m1b\nbpnx9YbOfGDkqzzGrDnHvD/4ww5Hc82hJBSWNlETkk0WRE36NRydH0aNU4XX47l+TJQNnXn/z4dF\nRqF1996mX2zxvHrwmidIczgJg6VN1MRkoxmuoDis33kU65cugsftFmpDZz4w8if370FyVkvzh2fD\nO2suIGGwtIl8JLjPQ6hACFbOnY2Ni+cLtaEzHxj5AeOmGKTuD41996CqfXUkCYGlTeQjkmJE5NiX\nUW+NRcteg4Tb0JkPjHxxjTv7xTX2P/35K4f2API5ljaRD0mKAVETf4m67k/i3IXLcDkdt83qoQCY\n11/eFhKKHsPGmH6xTf3F2TKvRXMQ+RRLm8jHJEmCE0YcPHkRq+fPg9NhvymjlwJgXp/55m07IC49\nO/SptdIEzWHkUyxtIkGED3sezuhsrPpsDhz2+uuP+3pDZz4w8r1HjjN1mPB0qzI7FM2h5DMsbSJB\nSJKM8AeeA7IGotJtBiDOhs68/+cNBiNOXCjomPS2fe6SUy7eMU1QLG0igUiShJCeU3HM1BarFy3k\nVeXMN2l+6/LFSG3VzvzMau//1LlU9oOA+B+FSEBexYK6iCwoFhvCoqI18yIWAPP6zPcaNlqWQ2KS\nR85zTNFcSE2OpU0kIEmSED7o2zC1HYYVc2fD7XbdNityATCvv7wsyxgwfqo5a8C4JM3F1ORY2kQC\nC+szEyGjX0alEg2P233TcdELgHl95oNCw+COazWw0xzrS+fLvWbNQdRkWNpEgjPFZ2FfqQWLPvgH\nqivKrz+ulwJgXp95WVZQY4rpOnaB6xnNYdRkWNpEOmCITIa56yQsnzMLlWWlPt/QmQ+MfM9hY0x5\n1Ya+L66xd9IcSk3C4OsfgIjuTkjnMYBsxMaVK1Ffes3nGzrz/p83WSxo3aOPed35w5OA+oOaw6nR\n8UybSEdCOg5H8NTX0Wnqs7AGBWvmRSoA5vWZP7prO5r3GZH1+uHQdpoLqNGxtIl0RjZaca4uBCvm\nzkJp4bXb5kQsAOb1mY9OSrG+trHql08sq++puZAaFUubSIesGV0QOvR5rP5sDkquXbnpuMgFwLz+\n8rKioP+4KeY5J/C9bRfdYZoDqNGwtIl0Kii7D8KGfw9nCutveFz0AmBen/m45BRkdehqemGD/LDm\nEGo0vBCNSMdsWT1Qhx7YfXwpUkO9UL1eXRQA8/rMdx4wxBCm9orzqP+CIqma86jh8UybyA8UW9Ow\nbtFnWL9onm4KgHn95RWDARWwdkj6u/qPfVc92ldCUoNjaRP5AWtaR0RN+AVU2QBJkjTzIhQA8/rM\nG4wmWKMS46Yudn9PczA1OJY2kZ+wpLRD9JTfoCyqA1T19i9dilQAzOszfy3/oqGwXun4/Cp7F80F\n1KD4njaRHzEnZuMagNOLfo6O7VsiLbvVDcdFLADm9ZfPmTgNkiybnDUnMoET+zUXUoPhmTaRHzL1\neQzb1q7C+ZPHrj8magEwr898fLNUeJrnjH18jTJQczE1GJY2kR8yxzdH9NTfYcf6L1FVXi58ATCv\nz7zD4w2df6T++d9scbTUHEINgqVN5KdMsemIf+JdnDNkYsPi+cIXAPP6y5stVvR4YIzprb34YYVd\nVTSH0TfG0ibyY7I5CCWmBKhGKypKSzXzeioM5sXIp7dqg5CYxPD/2eztqjmQvjGWNpGfk40WxMx4\nA/t37cKxvbtvmxOhAJjXX16SJAyZ+rBZaTu8vdvLG640NpY2UQAwRiQgZuabOJ1fBJfbe9NxUQqA\neX3mCy/n4725q8ak/c31exZ342JpEwUIQ1gswia8gkPOZJw6/H9fjSxaATCv0/y4KaiTgzIfXWof\noLmI7htLmyjAlLnN2P/VHuzfuglX886LWQDM6y6flJ6JPqMmWhafxncOF3iCNBfTfWFpEwUYQ3Ak\nYma+iVOnzmLD4s+ELADm9ZmPTUpGz6GjpGIpmqXdSFjaRAFICQpHzINvIm7ItxGTmqWZ10NhMC9G\nPqNdJ+u8+u6PfHjQmaQ5iO4ZS5soQCnWUChtR2JLbgV2rFsNVb35AjVAX4XBvBj5UwX1/V7erP6Y\nF6U1PJY2UYDzpnRFfkE5tq1ZeVNxi1AAzOsv36JjF8ljDk2cudg+SHMo3ROWNlGAk81BiJ7yKq6W\n1uLAzh3XHxelAJjXX16WZbTo1N2y8pz0BM+2Gxa/5YuIIJttiJryKurd1ai256Hq2gVs+WKREAXA\nvD7zB7dtQs74KdJV7A5KQVGt5iK6KzzTJiIAX985zWGNwfqte7BxyXwMGDdZmAJgXp/5+PQWwQNm\n17/1/n5nM82FdFdY2kR0g5CBT8GU1AbH9u+Dx+2+Y1bkwmBejHxc83bxv96BZzUX011haRPRDSSD\nEVETf4FKORx5+Vdvm9NDYTDv+3zLLt2kaq+p+Qur7V00h5AmljYR3URSjIgc9zKupY3C2bN5cLuc\nNxzXS2Ew7/u8ohjQa8R4c3FwVgvNQaSJpU1EtyRJEuyqEQdPXsSaBfPgcjoA6KswmBcjn5Seichu\nY/t+cEjle9vfEEubiG5LkiREjHgR9vAMrJ4/F/lnc31eAMzrM19YXtPsuVX1b+254gnRHEy3xdIm\nojuSZAXhw1+AN6MvDu3aJUQBMK+/fF1NNVRJMX97hfsxzTDdFkubiDRJkoyQXtMRPOm3OH7kKOx1\ndXfMi1YYzIuR7z96As6UqwPmH3fFaS6iW2JpE9Fd85pDURmUihVzZ6O+tuaWGVELg3nf51OzW2Hs\n49+RU7PbaK6jW2NpE9FdkyQJYQMeh5zVHyvnfQKP58bPcYtcGMyLkQ+JiDT8cm/oD1/f7tD+ejm6\nCUubiO6JJEkI6/cwgke/jEo5Em63C4A+CoN5MfL1xtCW/7tPeo73Jb93LG0iui/G2EzsKTLg8w/+\nifMnjuqmMJj3fb552w5wytbE51Y5umsOoxuwtInovhlj0mHqPB7bVi1Dj6EjdFEYzPs+L8syug0Z\nadlZFvaA5kC6Ab/li4i+kdCu4wHZiNxTO5HZpv0dsyIUBvNi5Js1b4FQi5JcVL/MGGv1ujSHEwCe\naRNRAwjtPAqmcb9Gfq0JlaUlt8yIVBjMi5FfsXBhYvO/2z+4WOE1aS4gACxtImogkmzA4cs1WDF3\nFsqKCm84JmJhMO/7fM7EaYhKTLF9a7lzjOYiAsDSJqIGZMvqhZCcZ7Dqs09RWnANgLiFwbwY+U4D\nhpp3XFan5pZ4rJqLie9pE1HDCmrVH5JswLnSAjgdYhcG877PR8TEokv/HO/Zmn0h2dGues0hAY5n\n2kTU4GzZvVHdaiL27N6Pjn0HClsYzIuRb9mtd9BWc/+cY0Uem+agAMfSJqJGo3SejP07tqEgP++O\nOT0VDPONk1/61YXJT6x0TdEcFuBY2kTUaKwZXRAx5qf4cskiFF2+dMuMCIXBvO/zHfoMNB285h29\nI98dqjk0gLG0iahRWdM6ImrSKyiPagdV9d5wTJTCYN73+ZDwCCSkZSrPrXHP1BwcwFjaRNTozInZ\nuGTKwOJ5C5B/JheAWIXBvBj5gkv5hg59Byma4QDG0iaiJiFJEqwDnsSWVStwcNsm4QqDed/ncyZO\ngyumZb+Zy7xDNBcFKJY2ETUZc0ILRE99FUf27UGvYaOEKgzmxch7JcX2+TH7M7suu0M0FwcgljYR\nNSlTXCYSn/kY9dmjUVFaeses6AXDfMPng0LDkN66nfS9de5JmgMCEEubiJqcbLbhisOKFfM+Re7h\nA7fM6KFgmG+cfLte/Y0nyuQh1Q6VHfVf+AdCRD4hm22Inv577N22HScP7L3hmJ4KhvmGz4dGRGLa\nsz/weEzBvCjtv7C0ichnjJFJiJ75Bk5dLIHbqwLwfWEwL0beIxsiunzkeeNsmdeiOTSAsLSJyKeM\n4fEIHfdzHKyNxZ6NXwpRGMz7Pi/LCuola+oTKxxjNQcHEJY2EQmhzGtD7okTSM5q6fPCYF6MfGlh\nofGrK+qky1X8vu1/Y2kTkRAMIdGIe+TPuHylEPu3brpjVsSCYb7h84MnTUdGq7bq5ye9yZqLAgS/\nmpOIhKEERyB6xhuovHYYHihQ4LkpI2rBMN84+YTUdFuwdDTe7V173iBLmuv9Hc+0iUgoSlA41OYD\nsPFYEXatXwdVVa8fE71gmG+c/B+WnvjOk8vtvTUHBACWNhGJKaM38i4XYue61VBVr24KhvmGzye1\nbB+2/Jzy4L8/YRDIWNpEJCTZEozoaa8hv7ACO9at0U3BMN/w+ZSsbDglY8yvtzhaaw7zc3xPm4iE\nJZttiJ76W7hKzqJX85aIa5aqucbXBcN8w+dlWUa3ISPN5VVfxQHlJzSH+jGeaROR0GSTFd7Edjh0\npgCbli2B13PzxWn/JkLBMN84+bTs1lJtUo8uhws8QZqD/RhLm4h0ISTnaZQ4FGz44nN4PO6bjotU\nMMw3Tn7OvC/6T1/qfloz7MdY2kSkC5LBhKgJv0S5GoLLV4tuOCZiwTDf8Pl+oyfgXJmnz+Y8d7jm\nIj/F0iYi3ZAMRkSO/xkuJQ3D6dyzcLtcwhYM8w2fT8tuhczW7fCzTe7Rmgv9FC9EIyJdkSQJdtWI\nw6cu4sTOTaitKEXOxGnCFQzzjZNv26u/0XbFIgPHNdf7I55pE5HuSJKEiFE/hDM8FdbQCETHJ2qu\n0UMhMa+dD42IhKV5ry6zD7sSNIf4IZY2EemSJCuIHPtTKK0fQA1sd8zqpZCYv7v8ufyr6T/aqL6s\nOcgPsbSJSLckSUZwj8k46EnDl18shaO+/qaMrwuG+YbPN2veAnUeOeGtXY4MzYF+hqVNRLrnNYeh\nKqgZVs77BPa62uuPi1AwzDd8XpYVtOra2/jPg5isOdTPsLSJSPckSULYoCeB9F5Y9dlceL28V7m/\n58OiY2RzVFK0ZtDPsLSJyC9IkoTQ/o8iaNRLuFhUg42L5wtTMMw3fH7Hqi+Q2KZr8s82e9ppLvAj\nLG0i8huSJMEQk4aTjhjIJgtCIyI114hYSMzfXd4SGhH89m7XT6sdasB0WcD8okQUOMzN2sLSZTyW\nz5mFmsqK2+ZELiTmtfPR8YkICosw/mCdvbvmYj/B0iYivxTafRIsXSdhx5ZttzwueiExf3f5Vt37\nWFfnGSZoDvATvCMaEfmtkC5joXpH4mL1UYQ7ixAW9fV1S3opJOa182ktW6N9ku0ysExzjj/gmTYR\n+TVJNuDwpVqsmDsb5SVFuiok5rXzBoMRxYjo/Z3V7h6aw/wAz7SJyO8FtewL1ePEyjnvAR43Bk+a\nrotCYv7u8nanO2j2EdcLfxqiPGwzSl7NwTrG0iaigBDcJgeQDYi1X9RVITGvnY+Ki4fRGmR8eUNd\nxz8PtxzQHK5jfHmciAJGcKv+qOv0MHbuO4GiK5dvmxOpkJi/u3xtTa1l+Tl5jGZY51jaRBRwSkOz\nsXbRZyi8nH/TMRELiXntfM6EaZj+0IxLmgt0jqVNRAHH1rw7Ikb9COsWzUfJtSvXHxe1kJjXzidn\nZiG30pDz1EpnT82FOsbSJqKAZM3ogqjJv0Z5ZHveq9xP8g63N3T+CfVpt1fVXK9XLG0iCljmxGxc\nNKRi0axZWL9ontCFxLx2PjapGSSTJejXWxytNYfoFEubiAKaJEkIHvIcVMUAl9OhmddLgQViXpIk\ntOjcw/zFWWWo5iCdYmkTUcAzJ7VC9JTfYuvaNaivrbltTk8FFqj5Vp27Sw8+NPXmKwz9BEubiAiA\nOSELcU+8jzxrG1SUFN90XIRCYl47bzAase1c7fCXN9jbag7VIZY2EdH/J5ssuFRvxvJ5n+L0kUPX\nHxelkJi/u3z+lYKEj49Kj2oGdYh3RCMi+g+KNQQx03+PPfN/BtXrRWhEhFCFxLx2/vSh/fC43Zl7\nrhhCuicp1ZqLdIRn2kRE/8UY1QzRM17HiQsF2LR0oVCFxLx2PmfiNDTLyHK/tcvZRXORzvBMm4jo\nFowRiTCO+wUSio6isnA3ElLvnBe1wAI1H52QZJlg3lsIfKW5Vk94pk1EdAeVlnjs37ULh3dtv21G\n9AILxLzRZMLb2yoeWXLKFaM5QEdY2kREd2AIjUH0jDdx7MgxHNy57abjeiiwQM0XVblbvL3bnaM5\nREdY2kREGgwhUYiZ+SYq47rBA+X643oqsEDMZ7bvZDxULA/zp9uasrSJiO6CEhQBT3ofbDh0Cbs3\nfomreed1VWCBmI9NagZVNgbPPepK1ByoEyxtIqJ7kTUA5y5cwobPP8PA8VN0U2CBmJckCROffkHu\n1TK2UnOoTrC0iYjugWINRcyMN6BEJqO0pFQzL0qBBWz+0iXTsNk1r/jLS+QsbSKieyRbghEz/feo\naTcNVbV2eL3eW+aEK7AAzG/5YhGKKh1pf9ntzNBcoAMsbSKi+yCbbagzRmD9pq+wecUX8Ho9NxwX\nscACMZ8zcRoy23YwLDip9tNcpAMsbSKibyBk6HMoqvVi47Il8Hq+Lm5RCyxQ8ynZbZTTFUpfzYU6\nwNImIvoGZKMF0ZNeQZnHimuFJcIXWCDmYxIT8diTj+VqLtYBljYR0TckGUyImvBLnIvuj60rv0D/\nsROFLbBAzEuSjLxyT7enV7l6ag4RHEubiKiBOBUbpLiWOLJnN9wu1x2zeik8f8nbHU7rolPqY5qD\nBMfSJiJqIJIkI3LcS6i1JWLNwnlwOZ23zPm6wAIxH9csBbVOb4ze70XO0iYiakCSrCBi5A/gzRyA\nOinopuMiFFgg5mVZQWpWS/Xd/a5emkMFxtImImpgkqwgqNtEHHAk48uli+G02wGIU2CBmm+W3caU\n2SLboRkUGEubiKiReKwRqLIlY+W8T3Dx9CmhCiwQ8ztWfYHDZab+O/LdoZoLBMXSJiJqJJIkIWzw\nM/Akd8bWFUt4r3IB8lfL61v8YadTt1eRG3z9AxAR+TNJkhCe8yRCOgyFNcYFl7MURpPptnmRC88f\n8va6OvO+rRcHA1inuVhAPNMmImpkkiTBEJ2Or/IdWPLx+6irrrplTvTC84d8UnomCqucWRcrvLf/\nl5PAWNpERE3E1KwdDG2GYfmcWaipuvHbIvVQeP6QN1ksmPH443lJodKtP48nOJY2EVETCus1DaaO\nY7F7x67rj+ml8Pwl77aEZ/x0q6Gb5iABsbSJiJpYaPeJwNCfIK/ci7PHDuuq8PwhX1tTLX+wr+5Z\nzWECYmkTEfmCbMThyzXYsWYFuuU8oJvC84d8VFw8nB6EfH7SFas5VDAsbSIiHwluMwhhQ76DPVs2\nory48I5ZUQrPH/KSJCMqLhEfH3J11hwsGH7ki4jIh0LaD4VsMOBStQMRt7krtkiF5y/54oJrpv4T\nWhQClzXzIuGZNhGRjwW1HoTitOHY/tUhlFy7esMxEQvPH/KDJ03HSXdClwq7qmguEghLm4hIEOUR\nbbBmwVwUXbkEQNzC85f8ss2Hh/xxp6Ol5kKBsLSJiARhy+qJ8JE/wNpF85F7aL/QhecP+aSslpZ1\nF6Crj36xtImIBGLN7IaoSa/gao2KAeMmC1t4/pBPzmwhn6uUdfVVnSxtIiLBmBOz4en5BHZu3oIr\nF87dMauXghQxH5uYjB69ul/RHCIQljYRkYAkWYFt8LPYuGwJLp09fcuMngpSxLysKEhu3zNh4wV3\nuOYwQbC0iYgEZUlug6hJr2Dr2jVw1NffcMzXhecv+ePHTiY9vUbVzd3RWNpERAIzJ2Yj9on3cMHc\nAmVFX9+ARZTC84d8UnomLpW7Orq9quZcEbC0iYgEJxvNyK8xYuVnc7BvywZhCs8f8jWVFfCoMM49\n6krUDAuApU1EpANKcASip72G4wf2I6tjZyEKz1/y7bp1rw8xSy7NBQJgaRMR6YQpJhVxD/0JBXUG\naL2aK2pBipjvNHBYcNJdrBEBS5uISEeMUcmwDf8R9pcHI/fwwVtmRC5IEfOVpSUY+vfzb2ouFABL\nm4hIh8qkcOzdsQNH9+y64XHRC1LEfEhEJOqd7rBtF91hmgN8jKVNRKRDhrA4xMx8E0cOHMSR3TsB\n6KMgRczLsozYhETn7COuVppDfIylTUSkU4bQGETPeBMV8d1x+eJFbFw8X/iCFDWf2aGr1WC2Ct+J\nwv+ARER0e4aQKLia9cCB09eQlNkC8Slpmmt8XZAi5pu37SANzBlQpznMx1jaRER+wNLrIVwtrsDu\njV9CVW9/abkIBSliXlW9eO6dLd+7WOE1aQ71IZY2EZEfUGxhiJ7+Oi7kX8OpI4dvmRGlIEXMS5IM\nr6TY/rnf2UJzsA8ZfP0DEBFRw1CsIYie/ntUKm5U1hxBaJAFkvT1uZlIBSlqvqam1rI939sWwDHN\nBT7CM20iIj8im4NQawjD+vXbsWXlcni9XiELUsR8h979UW8MjdNc4EM80yYi8kOhw7+PgsWvYM38\nOSgvuIKcidOEKkhR8217N7sAfK65zld4pk1E5IdkkwVRk36NKgSh85DRQhakiPlP1h4c/v5+ZzPN\nxT7C0iYi8lOy0YyYab9DaetpOHH0GDxu922zeijUpsjXOtXYJafc7TUH+AhLm4jIz9lVI46dzseX\nixfA7b75y6z0UqhNkY9LyTDlVhq7aA7xEZY2EZGfk2QFkWNfRrUxGmsXzofb5bx+TE+F2hT5uGYp\nKK2HsF/5xdImIgoAkmJAxJifwNt8AOrlYAC+L0gR8yHhEfju89/6SnOYj/DqcSKiACHJCmxdxmNv\nTRHqVryGykJeVf7fJEnCnqN57d9VnSlPdzXlaw5uYjzTJiIKMN6gaNSHpsAcHIrIuHjNvCiF2lT5\n3NyzCYtOujppBn2ApU1EFGAkSUbEiO9DSu2GtYsW8F7l/5W/knfBcLHGKOTXdLK0iYgCkCRJCBv8\nNKwjfoIKNRguh+OmjIiF2hT5roOGoLReEvJiNJY2EVGAkiQJckQydp2vxtLZ/0JdTfX1Y6IWalPk\nszt0wcxJQ3dpLvIBljYRUYAzZ3SD0nIwVsyZjdrqKqELtSnyisGAMrc5bc8VT4jm4ibGq8eJiAhh\nfWaiSjFi+8bNKL1wUthCbar89p0HWppCnO27J1l3aA5pQixtIiICAIT2nALVPRrt8tYiKDRIM6+X\nAr6ffGRCkvVkfn4GAKFKmy+PExHRdZLBivN1NqyYOxuVZaW3zempgO8nHxEbL12rN7bUHNTEWNpE\nRHSD4PYPwNbrQaycOxsVpcU3Hfd1oTZFPi45BT06ZZ/THNbE+PI4ERHdJKTjcEgGI67UAuFR//e4\nCIXaFHlbcAgS2ndBteOsHGKWvJqDmwjPtImI6JaC2w5GQfJgbN2+F6WF14Qp1KbK//3DRcPe3u3M\n0gw2IZ5pExHRHVVEtcOqeX+B5HVj8KQZQhRqU+Tr6uot+6560gHkai5oIjzTJiKiOwrK7oOw4d+H\nVzqw+dsAAAq7SURBVDLAGhSsmRexgO8nn9GmvXS+SuGZNhER6UtQi54whLyKsnALQj0FkBXlljlR\nC/h+8iazBbVqQT1QqbmuqfBMm4iI7oo5oQXOq4lY+NGHuJp3/qbjIhfw/eSj4hMwauTgAs2FTYil\nTUREd01SDAge8hw2fLEYl8+fvf646AV8v/k/fLR60vLTrmjNAU2EpU1ERPfEktIOkRN+ga1r18Dl\ndOimgO8nLykm69qz7jTNIU2EpU1ERPfMktwasd9+FyfqIrDh8890UcD3k4+ITzIfK1KF+ZpOljYR\nEd0XyWBCAaLhlY2or6vVzPu6gO8nH5OUojgMQRGaw5oIrx4nIqL7ZgiNQcz017Bjwc/h9XjRvG37\nW+ZEKOD7yae3aoN+bbxHgXWaM5sCz7SJiOgbMcWmI3r675F7tQpe9ebjohTw/eRVVcVvP905o6jW\nK8RJLkubiIi+MVN0CixDXsS+YjNyDx+8/rhIBXw/+YL8PFy8UtRsxyWPEC+RC/EvByIi8g9lShRO\nb98Ol9OJqNhYoQr4fvO2IJvrQrkjBMDNX3nWxHimTUREDcYYkYCYmW/i0J49WL9onnAFfD/5oJAQ\nz5VqNVRzURPgmTYRETUoQ1gsYh78IyylpxCTYgNwize6/4PIhZ2Qmo6EydMqX7G8f0RzYRPgmTYR\nETU4Q2g03Ol98eWuE9i/dRNU9dbFLXphA0BlVU3I5yddCZqLmwBLm4iIGo3SbjRyT5/H3s0bbipu\nPRQ2AJw9dSr4XwddfTUHNAGWNhERNRolKBzRM17H2QuXcObEieuP66WwAcBstUrVbkOk5pAmwPe0\niYioUSnWUMTMeAMVRg8qqw6itqwIm5cu1EVhA4DZYkO5R+FHvoiIKDDI5iBUA1i7ZiMcl49h8MTp\nuihsAIhPSUVbT7P9wDXNeY2NL48TEVGTiRjzUxii03D62FF4vd47ZkUobAAIDgtHh5bpFZoDmwBL\nm4iImoxstiF62u9Q7DCitLz6tjlRChsAqspK8cN3Nz6vObQJsLSJiKhJyUYLIif8AqfDe+H44cPw\nejw3HBepsAGgoqQYdqc7SDPYBFjaRETkE/VeA46dzseXSxbB43YDEK+wr128gO2rvoDX61XqXKrP\nO9PnPwAREQUmSTEiavzPUCmFYt3ihbh8/oxwhb1pyQLkTJyGrObpl4trVZ9fvO3zH4CIiAKXpBgR\nOe5l1B9Yhn1b1wpX2P/Od0iLuJBq/Jfzrn6pRsQzbSIi8ilJVmDrOgEho1/G0f374XI67pj3xUvo\nXyxb2+pve5xpd/ULNSKWNhERCUENT0aVOQ6r58+F02G/ZcZX73lXV9cGnSrxRN/9b9M4WNpERCQE\nSVYQPvwFOGNa4ssln9903Ke3MrUFySV1asjd/zaNg+9pExGRMCRJRvjQ54DKq6jwVsLmKofJbPH5\nVeW2kDClvhLm+/qlGhBLm4iIhCJJEhCehB2n81C//WN07dcfO1cv9+lFat0GDzf+3Xh6HeC659+n\nIfHlcSIiEpI5qzek5n2xdcVS9Bo+2qdXlZcVFeD5L9V+9/QLNAKWNhERCUmSJIT3fxTB3SfhSkGZ\nZr4xX0KvKCnG+jP1OXf9wzcSvjxORERCC+szEw7Vg/OFOxBrcSE4LPymTGO/511TVYkah5dXjxMR\nEWmSFBy9UoPln85CVfmNZ91NcZHakZ3b4FElXohGRER0N4I7joSqAivmzsaoGQ8jLDKqya4qHzhu\nMrKkK18C+xviV7lvLG0iItKNkE4jIRlMKHAYUdeEHwOLT0mD62Kxz7/piy+PExGRrgS3G4JLsf2w\nY8MGdB00tMmuKv/gs3Vji2q9Pj3ZZWkTEZHuSJIMY/cZ2LNlE0oLrt0x2xCFLUkSTGaT+0ih16d3\nRWNpExGRLgW37o+woc9j9fw5qCorvWWmQW9l+v/au5vYKOowjuO/2dnZ7i6FdpfdtiDVGqpciBVi\nfDvgSzAqpBEIQsDowcSDb0m9+RKiRmOiMfHmwZeLB1EgNTFiBRS1BAHFAkFoaVFehJYW+iZS2G13\nx5PQSru0dbeT/+73c53Z9Onpm5l5dicYTLX1eBttnmkDAIwVnne37JIy9ZYGNC3VIdu+krVsL6nd\nsnBh9w0luy9k9R+YIK60AQBGK6qoVttQhTZ+/KHOnDwuKTdfA6u5466hJTc5o1/STxGiDQAwnuUP\nqHjxc9r2xSYd3LMzJ1vlP377XfmaTQP3ZXPuiSLaAIC8EKq6VdFlr2j/7l1aVLsi+1vllh3ovOBG\nszTupBBtAEDeCFbO16ynP9GFG+/RuY72jOdO9BZ6InHJ7kv6ItmadTKINgAgr1h+R8d6pYYN63W8\n5fCo50zmmfex5t8UDgWHsj3vRBBtAEDecSKzFFv1hnZsbdDvhw6OODbZJbXFK9fqtTULf8jRyONC\ntAEAeSlQPlex1W+ptXNArixJ/2+rfNqMEr1a31qb67kz4XvaAIC8FYhXSfc+o587muQ7sk1t+5sm\nvVXe09WpQyd7F0iB3A8+BqINAMh7vU65uvYf0M3zaya9VR4MhZQYTIVzPWsm3B4HAOQ9J3qdyp54\nT0dbj+pw096M5451Cz0QCimZHAoOptxcjzsmog0AKAhOaYXia95W36w7lXKtUc/J9Mzb73dU9+zj\nDVMx61iINgCgYPhLynSxvEZbGvepaWfjiGPjWVL749TZ2b92pDx7rzbRBgAUHP+CFWo+1KK9jd/L\ndd1xb5U37tgzr755aM4UjjoCi2gAgIJjF0cUX/uOWj97SbbtV/MvP41rq7woFHLbz58vmaIxr0K0\nAQAFyQ6XKP7Yu+rvPqLbozFVXF917Q9ZPn/PRXdGzocbA7fHAQAFy1cUVmr2AjUdaNHOLV/LddNj\nnttx4pj+6utzHpxrN0/hiCMQbQBAwYs88rJOdfVrR8PmUcP97zPvRUuX64HqwDkPRpREtAEAkK8o\nrJmr3lTnRVu9/QMjjg1fUus+2+mr/TxZ59GYRBsAAEnyBUKKLl+nluLbdLBpn9Kp1FVb5UXBsBJp\ne6ZXM7KIBgDAMAPpgP5sO6kTzQfU33VG969YfXmrvCgUUiJtefZOba60AQAYxvI7mrl8nf72Tdf0\nWLnK5lRePjYjElU8Fj3t1WxEGwCA/7D8jmIrX5c9/2Fd8l35AbTSWFyPrlq2y6u5iDYAAKOwbEfB\nmqXa012srfUbNZhMajCZ0PsfrX/Sq5mINgAAGaRLK9XvxPXNhk/lpl11n+2usizL9mIWog0AQAaW\nz1ZkyQtKRKq1/asvZfudQUmlXsxCtAEAuAbL8qn0oeflX1wnJ1SckOTJ749bruvdy7ynQtWLm32S\nAl7PAQDID4M97enTHzyV9OJv5320AQDIF9weBwDAEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABD\nEG0AAAxBtAEAMATRBgDAEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABDEG0AAAxBtAEAMATRBgDA\nEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABDEG0AAAxBtAEA\nMATRBgDAEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABDEG0AAAxBtAEAMATRBgDAEEQbAABDEG0A\nAAxBtAEAMATRBgDAEEQbAABD/APHLlQLnwMBYAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x114a6e668>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "import numpy as np\n",
    "plt.figure(figsize=(8,8))\n",
    "\n",
    "x = np.linspace(start=0, stop=2, num=100)\n",
    "circle = [(4 - x**2)**0.5 for x in x]\n",
    "line = [2 - x for x in x]\n",
    "plt.fill(np.append(x,[0]), circle+[0])\n",
    "plt.fill(np.append(x,[2]), line+[2], alpha = 0.3)\n",
    "plt.fill(x, circle, edgecolor='black', fill=False, ls='--', lw=1, hatch='//')\n",
    "plt.axis('off')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "\n",
    "You are consulting for a trucking company that does a large amount of business shipping packages between New York and Boston. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a fixed limit W on the maximum amount of weight they are allowed to carry. Boxes arrive at the New York station one by one, and each package i has a weight wi. The trucking station is quite small, so at most one truck can be at the station at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise, a customer might get upset upon seeing a box that arrived after his make it to Boston faster. At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive, and whenever the next box does not fit, they send the truck on its way.\n",
    "\n",
    "But they wonder if they might be using too many trucks, and they want your opinion on whether the situation can be improved. Here is how they are thinking. Maybe one could decrease the number of trucks needed by sometimes sending off a truck that was less full, and in this way allow the next few trucks to be better packed.\n",
    "\n",
    "Prove that, for a given set of boxes with specified weights, the greedy algorithm currently in use actually minimizes the number of trucks that are needed. Your proof should follow the type of analysis we used for the Interval Scheduling Problem: it should establish the optimality of this greedy packing algorithm by identifying a measure under which it “stays ahead” of all other solutions.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Si movemos un paquete de un camión al siguiente, pueden ocurrir dos cosas:\n",
    "\n",
    "1) Que el paquete pueda entrar en el siguiente camión, en cuyo caso se disminuirá la cantidad de camiones.\n",
    "\n",
    "2) Que el paquete no pueda entrar en el sigueiente camión, en cuyo caso se deberá mover el último paquete de este camión al siguiente (donde nuevamente podrán darse los casos 1) o 2)).\n",
    "\n",
    "De esta forma, un algoritmo distinto del algoritmo greedy usará la misma cantidad de camiones o más que el greedy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4\n",
    "\n",
    "Some of your friends have gotten in to the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. Purchases at stock exchanges—what’s being bought— are one source of data with a natural ordering in time. Given a long sequence S of such events, your friends want an efficient way to detect certain “patterns” in them—for example, they may want to know if the four events\n",
    "\n",
    "> buy Yahoo, buy eBay, buy Yahoo, buy Oracle\n",
    "\n",
    "occur in this sequence S, in order but not necessarily consecutively.\n",
    "They begin with a collection of possible events (e.g., the possible transactions) and a sequence S of n of these events. A given event may occur multiple times in S (e.g., Yahoo stock may be bought many times in a single sequence S). We will say that a sequence S′ is a subsequence of S if there is a way to delete certain of the events from S so that the remaining events, in order, are equal to the sequence S′. So, for example, the sequence of four events above is a subsequence of the sequence\n",
    "\n",
    "> buy Amazon, buy Yahoo, buy eBay, buy Yahoo, buy Yahoo,  \n",
    " buy Oracle\n",
    "\n",
    "Their goal is to be able to dream up short sequences and quickly detect whether they are subsequences of S. So this is the problem they pose to you: Give an algorithm that takes two sequences of events—S′ of length m and S of length n, each possibly containing an event more than once—and decides in time O(m + n) whether S′ is a subsequence of S.\n",
    "\n",
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def is_subsequence(S, s):\n",
    "    i, j = 0, 0\n",
    "    while i < len(s) and j < len(S):\n",
    "        i += S[j] == s[i]\n",
    "        j += 1\n",
    "    return i >= len(s)\n",
    "\n",
    "print(is_subsequence([1,2,1,3,1,2], [1,3,1,2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "\n",
    "Let’s consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations.\n",
    "\n",
    "Give an efficient algorithm that achieves this goal, using as few base stations as possible.\n",
    "\n",
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5.5, 14, 24]"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def stations(houses):\n",
    "    last_station = -4\n",
    "    stations = []\n",
    "    for position in houses:\n",
    "        if not last_station - 4 < position < last_station + 4:\n",
    "            last_station = position + 4\n",
    "            stations.append(last_station)\n",
    "    return stations\n",
    "\n",
    "\n",
    "houses = [1.5, 2, 4, 5, 9, 10, 10.5, 15, 20 ]\n",
    "stations(houses)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6\n",
    "\n",
    "Your friend is working as a camp counselor, and he is in charge of organizing activities for a set of junior-high-school-age campers. One of his plans is the following mini-triathalon exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is to send the contestants out in a staggered fashion, via the following rule: the contestants must use the pool one at a time. In other words, first one contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out of the pool, a second contestant begins swimming the 20 laps; as soon as he or she is out and starts biking, a third contestant begins swimming . . . and so on.)\n",
    "\n",
    "Each contestant has a projected swimming time (the expected time it will take him or her to complete the 20 laps), a projected biking time (the expected time it will take him or her to complete the 10 miles of bicycling), and a projected running time (the time it will take him or her to complete the 3 miles of running). Your friend wants to decide on a schedule for the triathalon: an order in which to sequence the starts of the contestants. Let’s say that the completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathalon, assuming they each spend exactly their projected swimming, biking, and running times on the three parts. (Again, note that participants can bike and run simultaneously, but at most one person can be in the pool at any time.) What’s the best order for sending people out, if one wants the whole competition to be over as early as possible? More precisely, give an efficient algorithm that produces a schedule whose completion time is as small as possible.\n",
    "\n",
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4, 3, 1), (3, 2, 3), (2, 3, 2)]"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def triathlon(people):\n",
    "    return sorted(people, key = lambda x: x[1]+x[2])\n",
    "    \n",
    "triathlon([\n",
    "    (3,2,3),\n",
    "    (4,3,1),\n",
    "    (2,3,2)\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7\n",
    "\n",
    "The wildly popular Spanish-language search engine El Goog needs to do a serious amount of computation every time it recompiles its index. Fortunately, the company has at its disposal a single large supercomputer, together with an essentially unlimited supply of high-end PCs.\n",
    "They’ve broken the overall computation into n distinct jobs, labeled J1, J2, . . . , Jn, which can be performed completely independently of one another. Each job consists of two stages: first it needs to be preprocessed on the supercomputer, and then it needs to be finished on one of the PCs. Let’s say that job Ji needs pi seconds of time on the supercomputer, followed by fi seconds of time on a PC.\n",
    "\n",
    "Since there are at least n PCs available on the premises, the finishing of the jobs can be performed fully in parallel—all the jobs can be processed at the same time. However, the supercomputer can only work on a single job at a time, so the system managers need to work out an order in which to feed the jobs to the supercomputer. As soon as the first job in order is done on the supercomputer, it can be handed off to a PC for finishing; at that point in time a second job can be fed to the supercomputer; when the second job is done on the supercomputer, it can proceed to a PC regardless of whether or not the first job is done (since the PCs work in parallel); and so on.\n",
    "Let’s say that a schedule is an ordering of the jobs for the supercomputer, and the completion time of the schedule is the earliest time at which all jobs will have finished processing on the PCs. This is an important quantity to minimize, since it determines how rapidly El Goog can generate a new index.\n",
    "\n",
    "Give a polynomial-time algorithm that finds a schedule with as small a completion time as possible.\n",
    "\n",
    "#### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4, 4), (3, 5), (2, 5)]"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Mismo que 6\n",
    "def process(jobs):\n",
    "    return sorted(jobs, key = lambda x: x[1])\n",
    "    \n",
    "process([\n",
    "    (3,5),\n",
    "    (4,4),\n",
    "    (2,5)\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 8\n",
    "\n",
    "Suppose you are given a connected graph G, with edge costs that are all distinct. Prove that G has a unique minimum spanning tree.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Supongamos que T y T' son dos arboles de tendido mínimo distintos. Al ser distintos debe existir una arista e' en T' que no esté en T. Si agregamos la arista e' a T se debe generar un ciclo. En este caso pueden ocurrir 2 cosas:\n",
    "\n",
    "1) No hay una arista e en el ciclo con mayor peso que e', entonces e' no puede pertenecer a un arbol de tendido mínimo, entonces llegamos a un absurdo ya que T' no podría ser MST.\n",
    "\n",
    "2) Hay otra arista e en el ciclo con mayor peso que e', entonces e no puede pertenecer a un arbol de tendido mínimo, entonces llegamos a un absurdo ya que T no podría ser MST."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 9\n",
    "\n",
    "One of the basic motivations behind the Minimum Spanning Tree Problem is the goal of designing a spanning network for a set of nodes with minimum total cost. Here we explore another type of objective: designing a spanning network for which the most expensive edge is as cheap as possible.\n",
    "\n",
    "Specifically, let G = (V , E) be a connected graph with n vertices, m edges, and positive edge costs that you may assume are all distinct. Let T = (V , E') be a spanning tree of G; we define the bottleneck edge of T to be the edge of T with the greatest cost.\n",
    "\n",
    "A spanning tree T of G is a minimum-bottleneck spanning tree if there is no spanning tree T' of G with a cheaper bottleneck edge.\n",
    "\n",
    "(a) Is every minimum-bottleneck tree of G a minimum spanning tree of G? Prove or give a counterexample.\n",
    "\n",
    "(b) Is every minimum spanning tree of G a minimum-bottleneck tree of G? Prove or give a counterexample.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "(a) Falso. Si la arista máxima de G es la única forma de conectar un vértice, entonces todos los arboles van a ser \"minimum-bottleneck\".\n",
    "\n",
    "(b) Verdadero. Si hay otro arbol con menor \"bottleneck\" entonces, si agregamos la arista al MST se genera un ciclo en el cual la arista máxima no es la insertada, por lo que se llega a un absurdo (no era MST).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 10 (Final 18/02/19)\n",
    "\n",
    "Let G=(V,E) be an undirected graph with costs c_e ≥ 0 on the edges e∈E. \n",
    "Assume you are given a minimum-cost spanning tree T in G. Now assume\n",
    "that a new edge is added to G, connecting two nodes v, w ∈ V with cost c.\n",
    "\n",
    "a) Give an efficient algorithm to test if T remains the minimum-cost \n",
    "spanning tree with the new edge added to G (but not to the tree T). \n",
    "Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? \n",
    "Please note any assumptions you make about what data structure is used \n",
    "to represent the tree T and the graph G.\n",
    "\n",
    "b) Suppose T is no longer the minimum-cost spanning tree. \n",
    "Give a linear-time algorithm (time O(|E|)) to update the tree T to \n",
    "the new minimum-cost spanning tree.\n",
    "\n",
    "#### Solution "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def dfs(G, v, visited, parents):\n",
    "    for u, c in G[v].items():\n",
    "        if not u in visited:\n",
    "            visited.add(u)\n",
    "            parents[u] = v\n",
    "            dfs(G, u, visited, parents)\n",
    "    return parents\n",
    "            \n",
    "def still_mst(G, T, v, w, c):\n",
    "    parents = dfs(T, v, {v}, {v: None})\n",
    "    max_edge = 0\n",
    "    current = w\n",
    "    following = parents[current]\n",
    "    while following:\n",
    "        max_edge = max(max_edge, T[current][following])\n",
    "        current = following\n",
    "        following = parents[current]\n",
    "    return max_edge < c\n",
    "\n",
    "G = {\n",
    "    'a': {'b': 2, 'c': 1},\n",
    "    'b': {'a': 2},\n",
    "    'c': {'a': 1, 'e': 5},\n",
    "    'd': {'e': 1, 'f': 1},\n",
    "    'e': {'c': 5, 'd': 1},\n",
    "    'f': {'d': 1, 'g': 7, 'h': 3},\n",
    "    'g': {'f': 7},\n",
    "    'h': {'f': 3}\n",
    "}\n",
    "\n",
    "print(still_mst(G, G, 'a', 'g', 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 11\n",
    "\n",
    "Suppose you are given a connected graph G = (V , E), with a cost ce on each edge e. In an earlier problem, we saw that when all edge costs are distinct, G has a unique minimum spanning tree. However, G may have many minimum spanning trees when the edge costs are not all distinct. Here we formulate the question: Can Kruskal’s Algorithm be made to find all the minimum spanning trees of G?\n",
    "\n",
    "Recall that Kruskal’s Algorithm sorted the edges in order of increasing cost, then greedily processed edges one by one, adding an edge e as long as it did not form a cycle. When some edges have the same cost, the phrase “in order of increasing cost” has to be specified a little more carefully: we’ll say that an ordering of the edges is valid if the corresponding sequence of edge costs is nondecreasing. We’ll say that a valid execution of Kruskal’s Algorithm is one that begins with a valid ordering of the edges of G.\n",
    "\n",
    "For any graph G, and any minimum spanning tree T of G, is there a valid execution of Kruskal’s Algorithm on G that produces T as output? Give a proof or a counterexample.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Verdadero.\n",
    "\n",
    "**TODO: JUSTIFICAR**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 12\n",
    "\n",
    "Suppose you have n video streams that need to be sent, one after another, over a communication link. Stream i consists of a total of bi bits that need to be sent, at a constant rate, over a period of ti seconds. You cannot send two streams at the same time, so you need to determine a schedule for the streams: an order in which to send them. Whichever order you choose, there cannot be any delays between the end of one stream and the start of the next. Suppose your schedule starts at time 0 (and therefore ends at time  ni=1 ti, whichever order you choose). We assume that all the values bi and ti are positive integers.\n",
    "\n",
    "Now, because you’re just one user, the link does not want you taking up too much bandwidth, so it imposes the following constraint, using a fixed parameter r:\n",
    "\n",
    "> (∗) For each natural number t > 0, the total number of bits you send over the time interval from 0 to t cannot exceed rt.\n",
    "\n",
    "Note that this constraint is only imposed for time intervals that start at 0, not for time intervals that start at any other value.\n",
    "\n",
    "We say that a schedule is valid if it satisfies the constraint (∗) imposed by the link.\n",
    "\n",
    "**The Problem.**\n",
    "Given a set of n streams, each specified by its number of bits bi and its time duration ti, as well as the link parameter r, determine whether there exists a valid schedule.\n",
    "\n",
    "Example. Suppose we have n = 3 streams, with\n",
    "\n",
    ">(b1, t1) = (2000, 1), (b2, t2) = (6000, 2), (b3, t3) = (2000, 1),\n",
    "and suppose the link’s parameter is r = 5000. Then the schedule that runs the streams in the order 1, 2, 3, is valid, since the constraint (∗) is satisfied:\n",
    "\n",
    "> t = 1: the whole first stream has been sent, and 2000 < 5000 · 1 t = 2: half of the second stream has also been sent,\n",
    "> and 2000+3000<5000·2\n",
    "> Similar calculations hold for t = 3 and t = 4.\n",
    "\n",
    "(a) Consider the following claim:\n",
    "> Claim: There exists a valid schedule if and only if each stream i satisfies\n",
    "> bi ≤ rti.\n",
    "\n",
    "Decide whether you think the claim is true or false, and give a proof\n",
    "of either the claim or its negation.\n",
    "\n",
    "(b) Give an algorithm that takes a set of n streams, each specified by its number of bits bi and its time duration ti, as well as the link parameter r, and determines whether there exists a valid schedule. The running time of your algorithm should be polynomial in n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 196,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "streams = [(5000, 1), (5000, 1), (6000, 1)]\n",
    "\n",
    "# Solution by sorting\n",
    "def streaming(streams, r):\n",
    "    rates = sorted(streams, key = lambda x: x[0]/x[1])\n",
    "    b_total, t_total = 0, 0\n",
    "    for b, t in rates:\n",
    "        for j in range(t):\n",
    "            b_total += b/t\n",
    "            t_total += t\n",
    "            if b_total/t_total > r: return False\n",
    "    return True\n",
    "\n",
    "streaming(streams, 5000)\n",
    "\n",
    "# Solution by slacks\n",
    "def streaming(streams, r):\n",
    "    slacks = map(lambda x: r*x[1]-x[0], streams)\n",
    "    return sum(slacks) >= 0\n",
    "\n",
    "streaming(streams, 5000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 13\n",
    "\n",
    "A small business—say, a photocopying service with a single large machine—faces the following scheduling problem. Each morning they get a set of jobs from customers. They want to do the jobs on their single machine in an order that keeps their customers happiest. Customer i’s job will take ti time to complete. Given a schedule (i.e., an ordering of the jobs), let Ci denote the finishing time of job i. For example, if job j is the first to be done, we would have Cj = tj; and if job j is done right after job i, we would have Cj = Ci + tj. Each customer i also has a given weight wi that represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of i’s job. So the company decides that they want to order the jobs to minimize the weighted sum of the completion times,  $\\sum_{i=1}^n$ wiCi.\n",
    "\n",
    "Design an efficient algorithm to solve this problem. That is, you are given a set of n jobs with a processing time ti and a weight wi for each job. You want to order the jobs so as to minimize the weighted sum of the completion times,  ni=1 wiCi.\n",
    "\n",
    "**Example**. Suppose there are two jobs: the first takes time t1 = 1 and has weight w1 = 10, while the second job takes time t2 = 3 and has weight w2 = 2. Then doing job 1 first would yield a weighted completion time of 10 · 1 + 2 · 4 = 18, while doing the second job first would yield the larger weighted completion time of 10 · 4 + 2 · 3 = 46.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Supongamos una solución $S_A$ y $S_{Greedy}$, para la solución greedy se debe cumplir que si $J_i$ se encuentra antes que $J_j$ entonces $\\frac{w_i}{t_i} \\geq \\frac{w_j}{t_j}$. Para el caso en el cual son consecutivos, todas los demás valores de C_i se mantendrían iguales, por lo que las sumás pesadas se podrían resumir a:\n",
    "\n",
    "$$Greedy = w_j*(C + t_j) + w_i*(C+t_j+t_i)$$\n",
    "$$Alternativo = w_i*(C + t_i) + w_j*(C+t_i+t_j)$$\n",
    "\n",
    "Entonces la diferencia será:\n",
    "\n",
    "$$Greedy - Alternativo = w_i*t_j - w_j*t_i$$\n",
    "\n",
    "Dado que $\\frac{w_i}{t_i} \\geq \\frac{w_j}{t_j}$, entonces esta diferencia va a ser positiva siempre. Entonces la solución Greedy es óptima."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(100, 4), (100, 1)]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def schedule_jobs(jobs):\n",
    "    return sorted(jobs, key = lambda x: x[0]/x[1])\n",
    "\n",
    "jobs = [(100,1), (100,4)]\n",
    "\n",
    "schedule_jobs(jobs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 14\n",
    "\n",
    "You’re working with a group of security consultants who are helping to monitor a large computer system. There’s particular interest in keeping track of processes that are labeled “sensitive.” Each such process has a designated start time and finish time, and it runs continuously between these times; the consultants have a list of the planned start and finish times of all sensitive processes that will be run that day.\n",
    "\n",
    "As a simple first step, they’ve written a program called status_check that, when invoked, runs for a few seconds and records various pieces of logging information about all the sensitive processes running on the system at that moment. (We’ll model each invocation of status_check as lasting for only this single point in time.) What they’d like to do is to run status_check as few times as possible during the day, but enough that for each sensitive process P, status_check is invoked at least once during the execution of process P.\n",
    "\n",
    "(a) Give an efficient algorithm that, given the start and finish times of all the sensitive processes, finds as small a set of times as possi- ble at which to invoke status_check, subject to the requirement that status_check is invoked at least once during each sensitive process P.\n",
    "\n",
    "(b) While you were designing your algorithm, the security consultants were engaging in a little back-of-the-envelope reasoning. “Suppose we can find a set of k sensitive processes with the property that no two are ever running at the same time. Then clearly your algorithm will need to invoke status_check at least k times: no one invocation of status_check can handle more than one of these processes.”\n",
    "\n",
    "This is true, of course, and after some further discussion, you all begin wondering whether something stronger is true as well, a kind of converse to the above argument. Suppose that k∗ is the largest value of k such that one can find a set of k sensitive processes with no two ever running at the same time. Is it the case that there must be a set of k∗ times at which you can run status_check so that some invocation occurs during the execution of each sensitive process? (In other words, the kind of argument in the previous paragraph is really the only thing forcing you to need a lot of invocations of status_ check.) Decide whether you think this claim is true or false, and give a proof or a counterexample.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "TODO: Probar A  \n",
    "TODO: B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 8]\n"
     ]
    }
   ],
   "source": [
    "processes = [(0,4),(7,10),(1,4),(6,8),(3,5)]\n",
    "events = []\n",
    "for pid, (s,f) in enumerate(processes):\n",
    "    events.append((pid, s, 's'))\n",
    "    events.append((pid, f, 'f'))\n",
    "\n",
    "events.sort(key=lambda x: x[1])\n",
    "\n",
    "checked = set()\n",
    "checks = []\n",
    "previous = set()\n",
    "for event in events:\n",
    "    pid, time, t = event\n",
    "    if t == 'f' and not pid in checked:\n",
    "        checked = checked.union(previous)\n",
    "        checks.append(time)\n",
    "        previous = set()\n",
    "    elif t == 's':\n",
    "        previous.add(pid)\n",
    "        \n",
    "# b TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 15\n",
    "\n",
    "The manager of a large student union on campus comes to you with the following problem. She’s in charge of a group of n students, each of whom is scheduled to work one shift during the week. There are different jobs associated with these shifts (tending the main desk, helping with package delivery, rebooting cranky information kiosks, etc.), but we can view each shift as a single contiguous interval of time. There can be multiple shifts going on at once.\n",
    "\n",
    "She’s trying to choose a subset of these n students to form a super- vising committee that she can meet with once a week. She considers such a committee to be complete if, for every student not on the committee, that student’s shift overlaps (at least partially) the shift of some student who is on the committee. In this way, each student’s performance can be observed by at least one person who’s serving on the committee.\n",
    "\n",
    "Give an efficient algorithm that takes the schedule of n shifts and produces a complete supervising committee containing as few students as possible.\n",
    "\n",
    "Example. Suppose n = 3, and the shifts are\n",
    "\n",
    "- Monday 4 P.M.–Monday 8 P.M., \n",
    "- Monday 6 P.M.–Monday 10 P.M., \n",
    "- Monday 9 P.M.–Monday 11 P.M..\n",
    "\n",
    "Then the smallest complete supervising committee would consist of just the second student, since the second shift overlaps both the first and the third.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Obtener el intervalo que termina primero, incluir en la solución el intervalo con el que tiene intersección y que termina más tarde. Marcar como vistos todos los intervalos con los que tiene intersección el intervalo seleccionado. Tomar el intervalo que termina primero de los no marcados y hacer lo mismo que antes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 16\n",
    "\n",
    "Some security consultants working in the financial domain are cur- rently advising a client who is investigating a potential money-laundering scheme. The investigation thus far has indicated that n suspicious trans- actions took place in recent days, each involving money transferred into a single account. Unfortunately, the sketchy nature of the evidence to date means that they don’t know the identity of the account, the amounts of the transactions, or the exact times at which the transactions took place. What they do have is an approximate time-stamp for each transaction; the evidence indicates that transaction i took place at time ti ± ei, for some “margin of error” ei. (In other words, it took place sometime between ti − ei and ti + ei.) Note that different transactions may have different margins of error.\n",
    "\n",
    "In the last day or so, they’ve come across a bank account that (for other reasons we don’t need to go into here) they suspect might be the one involved in the crime. There are n recent events involving the account, which took place at times x1, x2, . . . , xn. To see whether it’s plausible that this really is the account they’re looking for, they’re wondering whether it’s possible to associate each of the account’s n events with a distinct one of the n suspicious transactions in such a way that, if the account event at time xi is associated with the suspicious transaction that occurred approximately at time tj, then |tj − xi| ≤ ej. (In other words, they want to know if the activity on the account lines up with the suspicious transactions to within the margin of error; the tricky part here is that they don’t know which account event to associate with which suspicious transaction.)\n",
    "\n",
    "Give an efficient algorithm that takes the given data and decides whether such an association exists. If possible, you should make the running time be at most O(n2).\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Iterar eventos en orden, por cada uno buscar el intervalo que termina antes que lo contenga y matchearlo, si no hay entonces no existe solución."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 17\n",
    "\n",
    "Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from what we saw in the Interval Scheduling Problem.)\n",
    "\n",
    "Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times.\n",
    "\n",
    "Example. Consider the following four jobs, specified by (start-time, end- time) pairs.\n",
    "- (6 P.M., 6 A.M.), \n",
    "- (9 P.M., 4 A.M.), \n",
    "- (3 A.M., 2 P.M.), \n",
    "- (1 P.M., 7 P.M.).\n",
    "\n",
    "The optimal solution would be to pick the two jobs (9 P.M., 4 A.M.) and (1 P.M., 7 P.M.), which can be scheduled without overlapping.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Para cada uno de los intervalos suponer que la solución lo incluye y calcular la solución. Y luego ver cual es la mejor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 18\n",
    "\n",
    "Your friends are planning an expedition to a small town deep in the Canadian north next winter break. They’ve researched all the travel options and have drawn up a directed graph whose nodes represent intermediate destinations and edges represent the roads between them.\n",
    "\n",
    "In the course of this, they’ve also learned that extreme weather causes roads in this part of the world to become quite slow in the winter and may cause large travel delays. They’ve found an excellent travel Web site that can accurately predict how fast they’ll be able to travel along the roads; however, the speed of travel depends on the time of year. More precisely, the Web site answers queries of the following form: given an edge e = (v, w) connecting two sites v and w, and given a proposed starting time t from location v, the site will return a value fe(t), the predicted arrival time at w. The Web site guarantees that fe(t) ≥ t for all edges e and all times t (you can’t travel backward in time), and that fe(t) is a monotone increasing function of t (that is, you do not arrive earlier by starting later). Other than that, the functions fe(t) may be arbitrary. For example, in areas where the travel time does not vary with the season, we would have fe(t) = t + le, where le is the time needed to travel from the beginning to the end of edge e.\n",
    "\n",
    "Your friends want to use the Web site to determine the fastest way to travel through the directed graph from their starting point to their intended destination. (You should assume that they start at time 0, and that all predictions made by the Web site are completely correct.) Give a polynomial-time algorithm to do this, where we treat a single query to the Web site (based on a specific edge e and a time t) as taking a single computational step.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "**Variación de Dijkstra**\n",
    "\n",
    "```\n",
    "def travel(G, s, d):\n",
    "    q = heap()\n",
    "    distances = {}\n",
    "    parents = {}\n",
    "    time[s] = 0\n",
    "    parent[s] = None\n",
    "    q.enqueue(s,0)\n",
    "    while not q.empty():\n",
    "        u = q.dequeue()\n",
    "        for v in u.adjacents():\n",
    "            if f(u,v,time[u]) < time[v]:\n",
    "                time[v] = f(u,v,time[u]) \n",
    "                parent[v] = u\n",
    "                q.enqueue(v, time[v])\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 19\n",
    "\n",
    "A group of network designers at the communications company CluNet find themselves facing the following problem. They have a connected graph G = (V , E), in which the nodes represent sites that want to com- municate. Each edge e is a communication link, with a given available bandwidth be.\n",
    "For each pair of nodes u, v ∈ V, they want to select a single u-v path P on which this pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains; that is, b(P) = mine∈P be. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the value b(P).\n",
    "\n",
    "It’s getting to be very complicated to keep track of a path for each pair of nodes, and so one of the network designers makes a bold suggestion: Maybe one can find a spanning tree T of G so that for every pair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate for u, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldn’t do better than the u-v path in T.)\n",
    "This idea is roundly heckled in the offices of CluNet for a few days, and there’s a natural reason for the skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneck rate; why should there be a single tree that simultaneously makes everybody happy? But after some failed attempts to rule out the idea, people begin to suspect it could be possible.\n",
    "\n",
    "Show that such a tree exists, and give an efficient algorithm to find one. That is, give an algorithm constructing a spanning tree T in which, for each u, v ∈ V, the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Hacer Prim o Kruskal tomando máximos. Nos vamos asegurando que los b_w son lo más grandes posibles. Esto es equivalente a encontrar el MST del grafo con las aristas negativas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 20\n",
    "\n",
    "Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear through the coming winter. There are n towns in this county, and the road system can be viewed as a (connected) graph G = (V , E) on this set of towns, each edge representing a road joining two of them. In the winter, people are high enough up in the mountains that they stop worrying about the length of roads and start worrying about their altitude—this is really what determines how difficult the trip will be.\n",
    "\n",
    "So each road—each edge e in the graph—is annotated with a number ae that gives the altitude of the highest point on the road. We’ll assume that no two edges have exactly the same altitude value ae. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j.\n",
    "\n",
    "The highway crews are going to select a set E′ ⊆ E of the roads to keep clear through the winter; the rest will be left unmaintained and kept off limits to travelers. They all agree that whichever subset of roads E′ they decide to keep clear, it should have the property that (V , E′) is a connected subgraph; and more strongly, for every pair of towns i and j, the height of the winter-optimal path in (V , E′) should be no greater than it is in the full graph G = (V , E). We’ll say that (V , E′) is a minimum-altitude connected subgraph if it has this property.\n",
    "Given that they’re going to maintain this key property, however, they otherwise want to keep as few roads clear as possible. One year, they hit upon the following conjecture:\n",
    "\n",
    "> The minimum spanning tree of G, with respect to the edge weights ae, is a minimum-altitude connected subgraph.\n",
    "\n",
    "(In an earlier problem, we claimed that there is a unique minimum span- ning tree when the edge weights are distinct. Thus, thanks to the assump- tion that all ae are distinct, it is okay for us to speak of the minimum spanning tree.)\n",
    "\n",
    "Initially, this conjecture is somewhat counterintuitive, since the min- imum spanning tree is trying to minimize the sum of the values ae, while the goal of minimizing altitude seems to be asking for a fairly different thing. But lacking an argument to the contrary, they begin considering an even bolder second conjecture:\n",
    "\n",
    "> A subgraph (V , E′) is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree.\n",
    "\n",
    "Note that this second conjecture would immediately imply the first one, since a minimum spanning tree contains its own edges.\n",
    "So here’s the question.\n",
    "\n",
    "(a) Is the first conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.\n",
    "\n",
    "(b) Is the second conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 21\n",
    "\n",
    "Let us say that a graph G=(V,E) is a near-tree if it is connected and has at most n + 8 edges, where n = |V|. Give an algorithm with running time O(n) that takes a near-tree G with costs on its edges, and returns a minimum spanning tree of G. You may assume that all the edge costs are distinct.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "BFS hasta que encontramos un ciclo, cuando encontramos el ciclo, eliminamos la arista más pesada. Esto lo repetimos 9 veces, hasta que queden n-1 aristas. De esta forma el grafo cumpliría con las siguientes 2 condiciones:\n",
    "\n",
    "- |V| - 1 aristas\n",
    "- Es conexo\n",
    "\n",
    "Las cuales implican que:\n",
    "\n",
    "- No posee ciclos\n",
    "\n",
    "Y por lo tanto sería un arbol, al mantener los mismos |V| sería de tendido y al eliminar siempre la arista de mayor peso de cada ciclo sería un arbol de tendido mínimo."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 22\n",
    "\n",
    "Consider the Minimum Spanning Tree Problem on an undirected graph G=(V,E), with a cost ce ≥0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or a counterexample with explanation.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Contraejemplo:\n",
    "\n",
    "![4_22.png](4_22.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 23\n",
    "\n",
    "Recall the problem of computing a minimum-cost arborescence in a directed graph G = (V , E), with a cost ce ≥ 0 on each edge. Here we will consider the case in which G is a directed acyclic graph—that is, it contains no directed cycles.\n",
    "\n",
    "As in general directed graphs, there can be many distinct minimum- cost solutions. Suppose we are given a directed acyclic graph G = (V , E), and an arborescence A ⊆ E with the guarantee that for every e ∈ A, e belongs to some minimum-cost arborescence in G. Can we conclude that A itself must be a minimum-cost arborescence in G? Give a proof or a counterexample with explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}