DTSA5503-Homework3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "25c9d407350b6e1605b305501df99bb5",
     "grade": false,
     "grade_id": "cell-44e5e9524e1b7eae",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Assigment 3: Greedy Algorithms\n",
    "\n",
    "In this assignment, we will explore greedy algorithms for makespan scheduling. We will see how a greedy algorithm can sometimes provide a solution that is guaranteed to be within some constant factor of the best possible solution. Please fill out the missing answers and the missing code below. Note that the coding part of this assignment should be simple given where we are in this class but the ungraded answers will hopefully be most instructive for this assignment.\n",
    "\n",
    "See https://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf section J1 for more details.\n",
    " \n",
    "  \n",
    "## Problem 1: Makespan Scheduling.\n",
    "\n",
    "Let us consider $n$ jobs that take times $T_1, \\ldots, T_n$ to complete where each $T_i > 0$. We have $m \\geq 2$ processors to process these jobs. Our goal is to assign these jobs to the processor.\n",
    "\n",
    "An assignment is modeled as an array $A: [A_1, \\ldots, A_n]$ wherein each $A_i$ represents the number of the processor to which job $i$ is assigned. Eg., $A_3 = 4$ means that job number $3$ is assigned to processor $4$.\n",
    "Therefore each $A_i \\in \\{ 1, \\ldots, m \\}$.\n",
    "\n",
    "Once the assignment is complete, each processor runs the jobs assigned to it under some order. \n",
    "\n",
    "### Question 1\n",
    "\n",
    "Let $M_j$ be the total time taken by some processor $j$ to complete all the jobs assigned to it.\n",
    "\n",
    "Write down an expression for $M_j$? We will not grade your answer but you may be able to check against the provided solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c69c3df30c035bd3c0ecf2843c8a48a4",
     "grade": true,
     "grade_id": "cell-f5e954c40eabff71",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "Mj = sum(A0 * T0, A1 * T1, Ai * Ti, ... An * Tn) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "07c74011d419f56ec6448b10f72f0d8e",
     "grade": false,
     "grade_id": "cell-290a55dcb068dd1c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### MakeSpan of an Assignment (Def)\n",
    "$$\\newcommand\\mspan{\\sf MakeSpan }$$\n",
    "\n",
    "The makespan of an assignment $A$ denoted $\\mspan(A)$ is the maximum among the total times taken by each processor. Formally, \n",
    "\n",
    "$$\\mspan(A) = \\max_{j=1}^m M_j$$\n",
    "\n",
    "The makespan of an assignment denotes the total time taken to complete all the jobs with the processors running in parallel since it measures the time taken by the processor which takes the longest to complete all its assigned tasks.\n",
    "\n",
    "#### Example\n",
    "\n",
    "Consider jobs with times $[T_1: 2,\\ T_2: 2,\\ T_3: 2,\\ T_4: 2,\\ T_5: 2,\\ T_6: 2,\\  T_7: 3]$ and $m = 3$ processors.\n",
    "\n",
    "Consider the assignment $A: [A_1: 1,\\ A_2: 1,\\ A_3: 2,\\ A_4: 2,\\ A_5: 3,\\ A_6: 3,\\ A_7: 2 ]$.\n",
    "\n",
    "### Question 2 \n",
    "\n",
    "Write down the total times taken by each processor under the given assignment. What is the makespan of this assignment? Is there a better assignment of jobs to processor that can reduce the makespan? If so what is it?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "11482e6ee6c98d63869faf39464a58cf",
     "grade": true,
     "grade_id": "cell-7e6e33a7080a1dc7",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "Take biggest job and give it to least loaded processor. Repeat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "bd6cbc44928db23c77bb46d74ad7caad",
     "grade": false,
     "grade_id": "cell-c82613c900852df3",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem A: Calculate Makespan of an Assignment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d1dcfd2d929657063fd5b72a69496906",
     "grade": false,
     "grade_id": "cell-ef20fed19686736d",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def compute_makespan(times, m, assign):\n",
    "    # times is an array of job times of size n\n",
    "    # m is the number of processors\n",
    "    # assign is an array of size n whose entries are between 0 to m-1 \n",
    "    # indicating the processor number for\n",
    "    # the corresponding job.\n",
    "    # Return: makespan of the assignment\n",
    "    # your code here\n",
    "    t = [0]*m\n",
    "    for i in range(len(times)):\n",
    "        t[assign[i]-1] = t[assign[i]-1] + times[i]\n",
    "    return max(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c2c64dbe1cc055ad0f9ac8e71dce9d0a",
     "grade": true,
     "grade_id": "cell-955e874e2483577f",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 1 ...  passed!\n",
      "Test 2 ...  passed!\n",
      "Tests passed: 10 points!\n"
     ]
    }
   ],
   "source": [
    "## BEGIN TESTS\n",
    "print('Test 1 ... ', end = '')\n",
    "times = [2, 2, 2, 2, 3, 3, 2]\n",
    "assigns = [0, 0, 0, 0, 1, 1, 2]\n",
    "m = 3\n",
    "s = compute_makespan(times, m, assigns)\n",
    "assert s == 8, f'Expected makespan is 8, your code returned: {s}'\n",
    "print(' passed!')\n",
    "\n",
    "print('Test 2 ...', end='')\n",
    "times = [2, 1, 2, 2, 1, 3, 2, 1, 1, 3]\n",
    "assigns = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]\n",
    "m = 3\n",
    "s = compute_makespan(times, m, assigns)\n",
    "assert s == 10, f' Expected makespan is 10, your code returned {s}'\n",
    "print('  passed!')\n",
    "print('Tests passed: 10 points!')\n",
    "\n",
    "## END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a7332125cbf4e33da6aa6e0a65338a05",
     "grade": false,
     "grade_id": "cell-36f6d4ee78e1fbb5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Minimizing Makespan\n",
    "\n",
    "Given a list $T: [T_1, \\ldots, T_n]$ of job times and $m \\geq 2$ processors, we wish to find an assignment that minimizes the overall makespan.\n",
    "\n",
    "\n",
    "### Question 3\n",
    "\n",
    "What is the number of possible assignments for a problem with $n = 1000$ jobs on $m = 10$ processors?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "799d5b59a44407bc35c56911143776b9",
     "grade": true,
     "grade_id": "cell-dcdc597dbfe9f984",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "Number of Combinations = (1000 + 10 - 1) choose (10 - 1)\n",
    "\n",
    "= 1009 choose 9\n",
    "\n",
    "= 1009! / (9! * (1009 - 9)!)\n",
    "\n",
    "Others contend greater than permutations: 10^1000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ff34d453ccc2363cd614621af49c7e2e",
     "grade": false,
     "grade_id": "cell-eee69a385013a57c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "As you will notice from the answer to the previous question, the number of possible assignments to a typical scheduling problem may well exceed the number of atoms in our Galaxy. Going through each and every one of them to find out the one that will minimize the makespan is impractical.  Furthermore, next module will study NP completeness. We will see that some problems including makespan scheduling are somehow inherently harder to solve on a computer. Thus, there are no known efficient solutions that solve for the optimal solution.\n",
    "\n",
    "Therefore, we will (hat tip to the brilliant mathematician/computer scientist Ronald Graham https://en.wikipedia.org/wiki/Ronald_Graham) propose a simple greedy algorithm for makespan minimization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1020a4bdc2cf8e1c16dc4aa21fcfb6fa",
     "grade": false,
     "grade_id": "cell-d7f14bf559d7bf99",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Greedy Makespan Minimization\n",
    "\n",
    "The idea is simple: we go through each job and assign it to the processor that currently has the least load.\n",
    "\n",
    "~~~\n",
    "greedy_min_make_span(T, m):\n",
    "  # T is an array of n numbers, m >= 2\n",
    "  A = [Nil, ... , Nil] # Initialize the assignments to nil (array size n)\n",
    "  M = [ 0, 0, ...., 0] # initialize the current load of each processor to 0 (array size m)\n",
    "  for i = 1 to n\n",
    "    find processor j for which M[j] is the least.\n",
    "    A[i] = j\n",
    "    M[j] = M[j] + T[i]\n",
    " # Assignment achieves a makespan of max(M[1], .. M[m])\n",
    " return A\n",
    "~~~\n",
    "\n",
    "### Question 4\n",
    "\n",
    "What is the running time of the greedy makespan algorithm? What data structure would you use to achieve a running time of $n \\log(m)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4c697f195545d25baa61c4e3411ffb5a",
     "grade": true,
     "grade_id": "cell-c577f0a2362f2c4b",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "Θ(M*A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8c7cd1ec309c8be60f630eb7abe082fb",
     "grade": false,
     "grade_id": "cell-9a7902fc3a168506",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem B: Implement the Greedy Makespan Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3a45d133d983f14b2549673da78082c1",
     "grade": false,
     "grade_id": "cell-742cf55a21d3750c",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def greedy_makespan_min(times, m):\n",
    "    # times is a list of n jobs.\n",
    "    assert len(times) >= 1\n",
    "    assert all(elt >= 0 for elt in times)\n",
    "    assert m >= 2\n",
    "    n = len(times)\n",
    "    # please do not reorder the jobs in times or else tests will fail.\n",
    "    # you can implement a priority queue if you would like.\n",
    "    # use https://docs.python.org/3/library/heapq.html heapq data structure \n",
    "    # Return a tuple of two things: \n",
    "    #    - Assignment list of n numbers from 0 to m-1\n",
    "    #    - The makespan of your assignment\n",
    "    a = [[] for i in range(m)]\n",
    "    b = []\n",
    "    l = [0]*m\n",
    "    t = [0]*m\n",
    "    for i in range(len(times)):\n",
    "        p = l.index(min(l))\n",
    "        a[p].append(i)\n",
    "        b.append(p)\n",
    "        l[p] += times[i]\n",
    "        t[p] += times[i] \n",
    "    for i in range(len(a)):\n",
    "        a[i].pop(0)\n",
    "    return [b,max(t)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a59c0be1cb6e9584ee3233806d7d0c30",
     "grade": true,
     "grade_id": "cell-dee38a85f0c77fa4",
     "locked": true,
     "points": 15,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 1:\n",
      "\t Assignment returned:  [0, 1, 2, 0, 1, 2, 0, 1, 2]\n",
      "\t Claimed makespan:  7\n",
      "Passed\n",
      "Test 2:\n",
      "\t Assignment returned:  [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0]\n",
      "\t Claimed makespan:  9\n",
      "Passed\n",
      "Test 3:\n",
      "\t Assignment returned:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0]\n",
      "\t Claimed makespan:  4\n",
      "Passed\n",
      "All tests passed: 15 points!\n"
     ]
    }
   ],
   "source": [
    "## BEGIN TESTS\n",
    "def do_test(times, m, expected):\n",
    "    (a, makespan) = greedy_makespan_min(times,m )\n",
    "    print('\\t Assignment returned: ', a)\n",
    "    print('\\t Claimed makespan: ', makespan)\n",
    "    assert compute_makespan(times, m, a) == makespan, 'Assignment returned is not consistent with the reported makespan'\n",
    "    assert makespan == expected, f'Expected makespan should be {expected}, your core returned {makespan}'\n",
    "    print('Passed')\n",
    "print('Test 1:')\n",
    "times = [2, 2, 2, 2, 2, 2, 2, 2, 3] \n",
    "m = 3\n",
    "expected = 7\n",
    "do_test(times, m, expected)\n",
    "\n",
    "print('Test 2:')\n",
    "times = [1]*20 + [5]\n",
    "m = 5\n",
    "expected =9\n",
    "do_test(times, m, expected)\n",
    "\n",
    "print('Test 3:')\n",
    "times = [1]*40 + [2]\n",
    "m = 20\n",
    "expected = 4\n",
    "do_test(times, m, expected)\n",
    "print('All tests passed: 15 points!')\n",
    "## END TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "28e283f49b8ed45a6a55730356bd4f9a",
     "grade": false,
     "grade_id": "cell-0a8cd8f791090ea6",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Question 5\n",
    "\n",
    "Construct a set of timings for $n$ jobs with $m \\geq 2 $ processors that shows that greedy solution can be strictly worse than the best solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "84f26157c81f27dcdf46374ffd84e36b",
     "grade": true,
     "grade_id": "cell-b66194b172c7170b",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "m jobs at 5t,\n",
    "\n",
    "m-1 jobs at 20t,\n",
    "\n",
    "2m jobs at 1t."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0ee94dd5f53f66fbb89bc51cd19d70f8",
     "grade": false,
     "grade_id": "cell-0b914bc8970f71d7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Analysis of Greedy Makespan Minimization "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ab1782dfa596ce78007274384bcfa568",
     "grade": false,
     "grade_id": "cell-b026f4318f2366a7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "We will now analyze the greedy algorithm and show the following result.\n",
    "\n",
    "For arbitrary (positive) times $[T_1, \\ldots, T_n]$ and $m\\geq 2$ processors.\n",
    "Let $A_g$ be the assignment returned by the greedy makespan with makespan value $T_g$.\n",
    "Let $A^*$ be the best possible assignment with makespan $T^*$.\n",
    "\n",
    "**Theorem**  $T^* \\leq T_g \\leq \\left( 2 - \\frac{1}{m} \\right) T^*$.\n",
    "\n",
    "The first part that $T^* \\leq T_g$ is obvious. The greedy algorithm returns _a_ solution whereas we\n",
    "claim that $T^*$ is the _best_ solution.\n",
    "\n",
    "This theorem proves an amazing result. Although greedy may not always provide the best solution, \n",
    "it is guaranteed to be no worse than $\\left(2 - \\frac{1}{m}\\right)$ times the best possible solution \n",
    "in the worst case. For instance if $m = 3$, then greedy algorithm finds an answer that is no \n",
    "worse than $1.67$ times the best answer.\n",
    "\n",
    "The advantage of this result is obvious: the greedy algorithm runs in time $\\Theta (n \\log(m))$ whereas the\n",
    "computing the optimal assignment is a very hard problem for which we know of no efficient algorithm in the worst case.\n",
    "\n",
    "To see why this result holds, note the key property that the greedy algorithm satisfies.\n",
    "\n",
    "### Greedy Algorithm Property\n",
    "\n",
    "At any point during the execution of the greedy algorithm: \n",
    "\n",
    "- Suppose $i-1$ out of the $n$ jobs have been assigned, and\n",
    "- If processor $j$ is selected as the one with the smallest total load so far\n",
    "\n",
    "then the total load of processor $j$ must be $\\leq $ the average of the job times across the processors: $T_{avg}:\\ \\frac{1}{m} ( T_1 + \\ldots + T_n)$.\n",
    "\n",
    "### Question 6\n",
    " \n",
    " Prove that the above property holds for the greedy algorithm.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "9ee616cbebc925c077dcd220f5bd15b4",
     "grade": true,
     "grade_id": "cell-5983b75bb8e40779",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "𝑇1+𝑇2+⋯+𝑇𝑛≥𝑀1+𝑀2+⋯+𝑀𝑚≥𝑚𝑀𝑗.\n",
    " \n",
    "So 𝑀𝑗≤1𝑚(𝑇1+⋯+𝑇𝑛)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "9a3f76f4ba3221fbfecb3be096780f7d",
     "grade": false,
     "grade_id": "cell-bfcfed0fcc69feec",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Using the property above, we observe the following: \n",
    "\n",
    "> The makespan of the greedy algorithm can be no more than $\\frac{1}{m} (T_1 + \\ldots + T_n) + T_{max}$ wherein \n",
    "$T_{max}$ is the job that takes the longest to complete.\n",
    "\n",
    "The reason for this is simple, consider the processor $j$ that is responsible for taking the longest time after greedy algorithm has finished making its assignment. When the last job was assigned to this processor by the greedy algorithm, its total load was below the overall average $\\frac{1}{m} (T_1 + \\cdots + T_n)$. However, the when the last job was added to this processor, its total load has to be below $\\frac{1}{m} (T_1 + \\ldots + T_n) + T_{max}$.\n",
    "\n",
    "\n",
    "Now, we make two observations about $T^*$: the makespan of the optimal algorithm.\n",
    " - $T^* \\geq T_{max}$. Some processor has to do the longest time job and the makespan has to include that.\n",
    " - $T^* \\geq \\frac{1}{m} ( T_1 + \\cdots + T_n)$. The maximum has to be greater than or equal to the average.\n",
    " \n",
    "Combining, we have\n",
    "\n",
    "$$T_g \\leq T_{max} + \\frac{1}{m} (T_1 + \\ldots + T_n) \\leq T^* + T^* = 2T^*\\,.$$\n",
    "\n",
    "This proves that the greedy algorithm is no worse than twice the optimal. However, we can improve the analysis by being a bit more careful. \n",
    "\n",
    "__A More Careful Analysis__\n",
    "\n",
    "Once again consider the processor j which causes the makespan for the greedy algorithm. Suppose we are at the point where we will add the very last job assigned to this processor (call this job $T_i$). \n",
    "\n",
    "We will note that we can have a better bound for $M_j$:\n",
    "$$ M_j \\leq \\frac{1}{m} (T_1 + \\ldots + T_{i-1} + T_{i+1} + \\cdots + T_n)\\,.$$\n",
    "I.e., the average need not include the last job $T_i$ itself. Once we note this, we can also show then that the makespan is  bounded by\n",
    "\n",
    "$$T_g \\leq \\frac{1}{m} (T_1 + \\ldots + T_{i-1} + T_{i+1} + \\cdots + T_n) + T_i = \\frac{1}{m} (T_1 + \\cdots + T_m) + \\left( 1 - \\frac{1}{m}\\right) T_i \\leq T_{avg} + \\left( 1 - \\frac{1}{m}\\right) T_{max}$$.\n",
    "\n",
    "This improves the bound to $T_g \\leq T^* + \\left(1 - \\frac{1}{m}\\right)T^* \\leq \\left( 2 - \\frac{1}{m}\\right) T^*$. QED!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "174c75a4cdea87d40844c09288befa50",
     "grade": false,
     "grade_id": "cell-24e103249fa0e135",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Sorting Job Times\n",
    "\n",
    "The above algorithm assumes that jobs are sorted in arbitrary order. It is in fact an _online_ approach where we make a decision on how to allocate a job as it arrives. Let us consider an _offline_ strategy where we sort the jobs in ascending order smallest size job to largest or vice-versa. \n",
    "\n",
    "### Question 7\n",
    "\n",
    "Using the intuition developed so far, would sorting jobs make a difference to how the greedy algorithm performs? If so, which order should jobs be sorted?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "7b6993a1afc9ff08c951b073ee1b7992",
     "grade": true,
     "grade_id": "cell-7b8e004911d335d0",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The book says take the shortest first. But that contradicts high throughput computing (where you slide in jobs between the big ones to keep the CPUs at full load for the highest amount of time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "9a745860bfe6492bd2628f37e2c247b2",
     "grade": false,
     "grade_id": "cell-28bd32e220b053ba",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Answers to manually graded problems\n",
    "\n",
    "### Answer 1\n",
    "There are many ways to express this.\n",
    "\n",
    "$M_j = \\sum_{ i = 1}^{n} T_i \\times [A_i = j] $ wherein the function $[A_i = j]$ equals $1$ if $A_i = j$ and $0$ otherwise. \n",
    "\n",
    "Here is another way to write the same thing.\n",
    "\n",
    "$M_j = \\sum_{ i \\in \\{ 1, \\ldots, n \\} \\cap \\{ i | A_i = j \\}} T_i$\n",
    "\n",
    "\n",
    "### Answer 2\n",
    "\n",
    "The times taken by each processor are $M_1 = 4, M_2 = 7, M_3 = 4$. The makespan is $7$.\n",
    "\n",
    "A better assignment is as follows:\n",
    "\n",
    "$\\hat{A}: [ 1, 1, 1, 2, 2, 2, 3]$ this assignment achieves a makespan of $6$.\n",
    "\n",
    "\n",
    "### Answer 3\n",
    "\n",
    "Each job can be assignment to one of 10 possible choices in terms of processors. The number of assignments is\n",
    "$m^n$ or $10^{1000}$.\n",
    "\n",
    "### Answer 4\n",
    "The running time as written is $\\Theta(nm)$. However, if we maintain a priority queue for $M$ where the priority is given by its current load, then using extract min, we can get the minimum load processor in $\\Theta(1)$. Also, we will need $\\Theta(\\log(m))$ time to bubble down when the load for processor $M[j]$ goes up.\n",
    "\n",
    "### Answer 5\n",
    "\n",
    "Take $n$ jobs of time 1 and one job of time $n$ and schedule it over $m$ processors. The greedy algorithm will have a makespan of roughly $\\frac{n}{m} + n$ whereas the best solution is to distribute the first $n$ jobs over\n",
    "the $m-1$ processors and then have the last job on the remaining processor, yielding a makespan of $n$.\n",
    "\n",
    "#### Answer 6\n",
    "\n",
    "Let us assume that processor $k$'s current total job allocation is $M_k$. Let processor $j$ have the minimum total load so far.\n",
    "\n",
    "We have that $ M_j \\leq M_k$ for all $k \\in \\{ 1, \\ldots, m \\}$. Thus, $M_1 + M_2 + \\cdots + M_m \\geq m M_j$.\n",
    "But what is $M_i$: it is the sum of job times that have been assigned to processor $i$. Therefore, the sum of all job times must exceed the sum of the times for the individual processors since each job is assigned to at most one processor.\n",
    "\n",
    "The LHS is bounded as follows:\n",
    "$$ T_1 + T_2 + \\cdots + T_n \\geq M_1 + M_2 + \\cdots + M_m \\geq m M_j \\,.$$\n",
    "This yields the fact that $M_j \\leq \\frac{1}{m} \\left( T_1 + \\cdots + T_n \\right)$.\n",
    "\n",
    "\n",
    "### Answer 7\n",
    "\n",
    "The jobs should be sorted in descending order for the best performance.  To see why, let us go back to the key property of the greedy algorithm: when it assigns a job to processor j, the total load currently assigned to processor j must be less than the average (total of all job times divided by the number of processors). Thus, let us freeze the algorithm at the point when it assigns a job to the processor j that causes the worst total time (i.e the makespan) to be achieved. Since jobs are sorted in descending order, this job has to be smaller than the largest job $T_{max}$. In fact, a slightly more detailed analysis will show that this job will be less than half the make span of the optimal solution.  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b83948e3f934c0c0445b43a6bef3f486",
     "grade": false,
     "grade_id": "cell-8dbc0d37a931a71b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## That's All Folks!"
   ]
  },
  {
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}