DTSA_5501_Homework3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0bda1d3ef9687bb65bc14a56c24df052",
     "grade": false,
     "grade_id": "cell-21fe58f9d26514ca",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Assignment 3 \n",
    "\n",
    "## Problem 1: Design a Correct Partition Algorithm\n",
    "\n",
    "You are given code below for an incorrect partition algorithm that fails to partition arrays wrongly or cause out of bounds access in arrays.  The comments include the invariants the algorithm wishes to maintain and will help you debug.\n",
    "\n",
    "Your goal is to write test cases that demonstrate that the partitioning will fail in various ways.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "25aea318409659a93e8142198c7dcdb6",
     "grade": false,
     "grade_id": "cell-0debc539ee455c8d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def swap(a, i, j):\n",
    "    assert 0 <= i < len(a), f'accessing index {i} beyond end of array {len(a)}'\n",
    "    assert 0 <= j < len(a), f'accessing index {j} beyond end of array {len(a)}'\n",
    "    a[i], a[j] = a[j], a[i]\n",
    "\n",
    "def tryPartition(a):\n",
    "    # implementation of Lomuto partitioning algorithm\n",
    "    n = len(a)\n",
    "    pivot = a[n-1] # choose last element as the pivot.\n",
    "    i,j = 0,0 # initialize i and j both to be 0\n",
    "    for j in range(n-1): # j = 0 to n-2 (inclusive)\n",
    "        # Invariant: a[0] .. a[i] are <= pivot\n",
    "        #            a[i+1]...a[j-1] are > pivot\n",
    "        if a[j] <= pivot: \n",
    "            swap(a, i+1, j)\n",
    "            i = i + 1\n",
    "    swap(a, i+1, n-1) # place pivot in its correct place.\n",
    "    return i+1 # return the index where we placed the pivot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ed12e625c008773974cf80a34964b5ec",
     "grade": false,
     "grade_id": "cell-f5e5ddbbae4ed87c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "First write a function that will return True if an array is correctly partitioned at index `k`. I.e, all elements at indices `< k` are all `<= a[k]` and all elements indices `> k` are all `> a[k]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "251707c02123afdd8e190ea35b07faf1",
     "grade": false,
     "grade_id": "cell-0e3595d188545bc8",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def testIfPartitioned(a, k):\n",
    "    # TODO : test if all elements at indices < k are all <= a[k]\n",
    "    #         and all elements at indices > k are all > a[k]\n",
    "    # return TRUE if the array is correctly partitioned around a[k] and return FALSE otherwise\n",
    "    assert 0 <= k < len(a)\n",
    "    #print(a[k])\n",
    "    for i in range(0,k-1):\n",
    "            if a[i] <= a[k]:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "    for i in range(k+1,len(a)):\n",
    "            if a[i] > a[k]:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "    return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d97849365bca117834d047b818c5b0f0",
     "grade": true,
     "grade_id": "cell-9bbed3588a211427",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Passed all tests (10 points)\n"
     ]
    }
   ],
   "source": [
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 14, 10, 23],5) == True, ' Test # 1 failed.'\n",
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 14, 11, 23],4) == False, ' Test # 2 failed.'\n",
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 14, 23, 21],0) == True, ' Test # 3 failed.'\n",
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 14, 22, 23],9) == True, ' Test # 4 failed.'\n",
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 14, 8, 23],5) == False, ' Test # 5 failed.'\n",
    "assert testIfPartitioned([-1, 5, 2, 3, 4, 8, 9, 13, 9, -11],5) == False, ' Test # 6 failed.'\n",
    "assert testIfPartitioned([4, 4, 4, 4, 4, 8, 9, 13, 9, 11],4) == True, ' Test # 7 failed.'\n",
    "print('Passed all tests (10 points)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "048709275297da79377c8b4ad5ca462e",
     "grade": false,
     "grade_id": "cell-7b4f2e1aeeee1373",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Write an array called a1 that will be incorrectly partitioned by the tryPartition algorithm above\n",
    "# Your input when run on tryPartition algorithm should raise an out of bounds array access exception\n",
    "# in the swap function or fail to partition correctly. \n",
    "\n",
    "## Define an array a1 below of length > 0 that will be incorrectly partitioned by tryPartition algorithm.\n",
    "## We will test whether your solution works in the subsequent cells.\n",
    "\n",
    "a1 = [0,7,7,7,7,7,7,7,7,7]\n",
    "assert( len(a1) > 0)\n",
    "\n",
    "# Write an array called a2 that will be incorrectly partitioned by the tryPartition algorithm above\n",
    "# Your input when run on tryPartition algorithm should raise an out of bounds array access exception\n",
    "# in the swap function or fail to partition correctly. \n",
    "# a2 must be different from a1\n",
    " \n",
    "a2 = [3,3,3,3,3,3]\n",
    "assert( len(a2) > 0)\n",
    "assert (a1 != a2)\n",
    "\n",
    "\n",
    "# Write an array called a3 that will be incorrectly partitioned by the tryPartition algorithm above\n",
    "# Your input when run on tryPartition algorithm should raise an out of bounds array access exception\n",
    "# in the swap function or fail to partition correctly. \n",
    "# a3 must be different from a1, a2\n",
    "\n",
    "a3 = [12,12,22,2,7,2,22,12]\n",
    "assert( len(a3) > 0)\n",
    "assert (a3 != a2)\n",
    "assert (a3 != a1)\n",
    "\n",
    "def dummyFunction():\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9e898a699440a1bb73e956339c18dabd",
     "grade": true,
     "grade_id": "cell-b893840d1eabfef0",
     "locked": true,
     "points": 5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Assertion failed accessing index 10 beyond end of array 10 - this is fine since you were asked to break the code.\n",
      "Assertion failed accessing index 6 beyond end of array 6 - this is fine since you were asked to break the code.\n",
      "Assertion failed accessing index 8 beyond end of array 8 - this is fine since you were asked to break the code.\n",
      "Passed 5 points!\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    j1 = tryPartition(a1)\n",
    "    assert not testIfPartitioned(a1, j1)\n",
    "    print('Partitioning was unsuccessful - this is what you were asked to break the code')\n",
    "except Exception as e: \n",
    "    print(f'Assertion failed {e} - this is fine since you were asked to break the code.')\n",
    "    \n",
    "try:\n",
    "    j2 = tryPartition(a2)\n",
    "    assert not testIfPartitioned(a2, j2)\n",
    "except Exception as e: \n",
    "    print(f'Assertion failed {e} - this is fine since you were asked to break the code.')\n",
    "    \n",
    "\n",
    "try:\n",
    "    j3 = tryPartition(a3)\n",
    "    assert not testIfPartitioned(a3, j3)\n",
    "except Exception as e: \n",
    "    print(f'Assertion failed {e} - this is fine since you were asked to break the code.')\n",
    "    \n",
    "dummyFunction()\n",
    "\n",
    "print('Passed 5 points!')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e3371d4627bb7ca284345238c6ea9886",
     "grade": false,
     "grade_id": "cell-074a527ab9550d6b",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Array:  [0, 7, 7, 7, 7, 7, 7, 7, 7, 7]\n",
      "[0, 7, 7, 7, 7, 7, 7, 7, 7, 7] Pivot Index: 8  Pivot Value: 7 \r\n",
      "\n",
      " Original Array:  [3, 3, 3, 3, 3, 3]\n",
      "[3, 3, 3, 3, 3, 3] Pivot Index: 4  Pivot Value: 3 \r\n",
      "\n",
      " Original Array:  [12, 2, 7, 2, 12, 12, 22, 22]\n",
      "[12, 2, 7, 2, 12, 12, 22, 22] Pivot Index: 6  Pivot Value: 22 \r\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Troubleshoot the function and test on a1, a2, and a3\n",
    "# First pass we'll do this the hard way. \n",
    "def tryPartition2(a):\n",
    "    # implementation of Lomuto partitioning algorithm\n",
    "    n = len(a)\n",
    "    #print(n)\n",
    "    pivot = a[n-1] # choose last element as the pivot.\n",
    "    i,j = 0,0 # initialize i and j both to be 0\n",
    "    for j in range(n-2): # j = 0 to n-2 (inclusive)\n",
    "        # Invariant: a[0] .. a[i] are <= pivot\n",
    "        #            a[i+1]...a[j-1] are > pivot\n",
    "        if a[j] <= pivot: \n",
    "            swap(a, i, j)\n",
    "            i += 1\n",
    "            \n",
    "    print(a, \"Pivot Index:\", i, \" Pivot Value:\", a[n-1] , \"\\r\")\n",
    "    swap(a, i, n-1) # place pivot in its correct place.\n",
    "    return i # return the index where we placed the pivot\n",
    "\n",
    "# Second pass we'll do this the easy way. \n",
    "# Only thing that changes is the initialization of i = -1\n",
    "def tryPartition3(a):\n",
    "    # implementation of Lomuto partitioning algorithm\n",
    "    n = len(a)\n",
    "    pivot = a[n-1] # choose last element as the pivot.\n",
    "    i,j = -1,0 # initialize i and j both to be 0\n",
    "    for j in range(n-1): # j = 0 to n-2 (inclusive)\n",
    "        # Invariant: a[0] .. a[i] are <= pivot\n",
    "        #            a[i+1]...a[j-1] are > pivot\n",
    "        if a[j] <= pivot: \n",
    "            swap(a, i+1, j)\n",
    "            i = i + 1\n",
    "    \n",
    "    print(a, \"Pivot Index:\", i, \" Pivot Value:\", a[n-1] , \"\\r\")\n",
    "    swap(a, i+1, n-1) # place pivot in its correct place.\n",
    "    return i+1 # return the index where we placed the pivot\n",
    "print(\"Original Array: \",a1)\n",
    "tryPartition2(a1)\n",
    "print(\"\\n Original Array: \",a2)\n",
    "tryPartition2(a2)\n",
    "\n",
    "print(\"\\n Original Array: \",a3)\n",
    "tryPartition3(a3)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a0312cba96925e98da92ef18c3023cb2",
     "grade": false,
     "grade_id": "cell-86b9eccd182b633f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Debug the function\n",
    "\n",
    "Point out where the bug is and what the fix is for the tryPartition function. Note that the answer below is not graded."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c7fa8043aadfcd12b0f4b4bf7fb24d99",
     "grade": true,
     "grade_id": "cell-450850f6c2af5c97",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "First pass is the hard way:\n",
    "\n",
    "This line:\n",
    "\n",
    "    swap(a, i+1, j)\n",
    "\n",
    "Should be:\n",
    "    \n",
    "    swap(a, i, j)\n",
    "    \n",
    "Final swap should be i and n-1 (not i+1 and n-1)\n",
    "\n",
    "Return i as index location, not i+1\n",
    "\n",
    "Second pass is the easy way:\n",
    "\n",
    "Just initialize i as -1 to correct for the 0 index in python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4c7d3f415785a36102330fb1e24c4985",
     "grade": false,
     "grade_id": "cell-980bdca4c01d41ef",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 2. Rapid Sorting of Arrays with Bounded Number of Elements.\n",
    "\n",
    "Thus far, we have presented sorting algorithms that are comparison-based. Ie., they make no assumptions about the elements in the array just that we have a `<=` comparison operator. We now ask you to develop a rapid sorting algorithm for an array of size $n$ when it is given to you that all elements in the array are between $1, \\ldots, k$ for a given $k$. Eg., consider an array with n = 100000 elements wherein all elements are between 1,..., k = 100.\n",
    "\n",
    "\n",
    "Develop a sorting algorithm using partition that runs in $\\Theta(n \\times k)$ time for such arrays. __Hint__ You can choose your pivots in a simple manner each time. \n",
    "\n",
    "### Part A\n",
    "\n",
    "Describe your algorithm as pseudocode and argue why it runs in time $\\Theta(n \\times k)$. This part will not be graded but is intended for your own edification."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "be618e556c470d62cc6a364cceafb56a",
     "grade": true,
     "grade_id": "cell-8df6ac83ee3184cd",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "for i in range k:\n",
    "    \n",
    "    pivot on the values, and increment i to determine index after each swap.\n",
    "    Have to run through the values (n length) in order (k times) but we are never touching right of index (i).\n",
    "    Therefore, \n",
    "        average case: is far less than Θ(n*k) because as i creeps across, array n to compare is being reduced.  \n",
    "        worst case: (all elts are k, or 100 here), we run through them each time and i never increments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1cd8b9842421475faeaf77b306bc45ac",
     "grade": false,
     "grade_id": "cell-83bd721a249c586a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Part B \n",
    "Complete the implementation of a function `boundedSort(a, k)` by completing the `simplePatition` function. Given an array `a` and a fixed `pivot` element, it should partition the array \"in-place\" so that all elements `<= pivot` are on one side of the array and elements `> pivot` on the other.  You should not create a new array in your code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1f48577604926382d27f624100096eda",
     "grade": false,
     "grade_id": "cell-6df8a59d82deaa25",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "def swap(a, i, j):\n",
    "    assert 0 <= i < len(a), f'accessing index {i} beyond end of array {len(a)}'\n",
    "    assert 0 <= j < len(a), f'accessing index {j} beyond end of array {len(a)}'\n",
    "    a[i], a[j] = a[j], a[i]\n",
    "\n",
    "def simplePartition(a, pivot):\n",
    "    ## To do: partition the array a according to pivot.\n",
    "    # Your array must be partitioned into two regions - <= pivot followed by elements > pivot\n",
    "    ## If an element at the beginning of the array is already <= pivot in the beginning of the array, it should not\n",
    "    ## be moved by the algorithm.\n",
    "    n = len(a) \n",
    "    i,j = -1,0\n",
    "    for j in range(n):\n",
    "        if a[j] <= pivot:\n",
    "            swap(a,i+1,j)\n",
    "            i +=1   \n",
    "def boundedSort(a, k):\n",
    "    for j in range(1, k):\n",
    "        simplePartition(a, j)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "07668380018a8024a6e0f1d7132eca67",
     "grade": true,
     "grade_id": "cell-5e544036bd8af86f",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 6, 1, 5, 4, 1, 1, 2, 3, 3, 1, 3, 5, 2, 2, 4]\n",
      "[1, 1, 1, 1, 1, 4, 6, 3, 2, 3, 3, 5, 3, 5, 2, 2, 4]\n",
      "[1, 1, 1, 1, 1, 2, 2, 2, 4, 3, 3, 5, 3, 5, 6, 3, 4]\n",
      "[1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 5, 4]\n",
      "[1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 6, 5, 5]\n",
      "[1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6]\n",
      "Passed all tests : 10 points!\n"
     ]
    }
   ],
   "source": [
    "a = [1, 3, 6, 1, 5, 4, 1, 1, 2, 3, 3, 1, 3, 5, 2, 2, 4]\n",
    "print(a)\n",
    "simplePartition(a, 1)\n",
    "print(a)\n",
    "assert(a[:5] == [1,1,1,1,1]), 'Simple partition test 1 failed'\n",
    "\n",
    "simplePartition(a, 2)\n",
    "print(a)\n",
    "assert(a[:5] == [1,1,1,1,1]), 'Simple partition test 2(A) failed'\n",
    "assert(a[5:8] == [2,2,2]), 'Simple Partition test 2(B) failed'\n",
    "\n",
    "\n",
    "simplePartition(a, 3)\n",
    "print(a)\n",
    "assert(a[:5] == [1,1,1,1,1]), 'Simple partition test 3(A) failed'\n",
    "assert(a[5:8] == [2,2,2]), 'Simple Partition test 3(B) failed'\n",
    "assert(a[8:12] == [3,3,3,3]), 'Simple Partition test 3(C) failed'\n",
    "\n",
    "simplePartition(a, 4)\n",
    "print(a)\n",
    "assert(a[:5] == [1,1,1,1,1]), 'Simple partition test 4(A) failed'\n",
    "assert(a[5:8] == [2,2,2]), 'Simple Partition test 4(B) failed'\n",
    "assert(a[8:12] == [3,3,3,3]), 'Simple Partition test 4(C) failed'\n",
    "assert(a[12:14]==[4,4]), 'Simple Partition test 4(D) failed'\n",
    "\n",
    "simplePartition(a, 5)\n",
    "print(a)\n",
    "assert(a == [1]*5+[2]*3+[3]*4+[4]*2+[5]*2+[6]), 'Simple Parition test 5 failed'\n",
    "\n",
    "print('Passed all tests : 10 points!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "af5764e23535a90042a4d2eae1399533",
     "grade": false,
     "grade_id": "cell-288fa6c7efea8621",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 3: Design a Universal Family Hash Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1517870ce960593e4e17c4f60f79152f",
     "grade": false,
     "grade_id": "cell-b37a72be16ed1aa4",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Suppose we are interested in hashing $n$ bit keys into $m$ bit hash values to hash into a table of size\n",
    "$2^m$. We view our key  as a bit vector of $n$ bits in binary. Eg., for $n = 4$, the key $14 = \\left(\\begin{array}{c} 1\\\\ 1\\\\ 1\\\\ 0 \\end{array} \\right)$.\n",
    "\n",
    "The hash family is defined by random boolean matrices $H$ with $m$ rows and $n$ columns. To compute the hash function, we perform a matrix multiplication. Eg., with $m = 3$ and $n= 4$, we can have a matrix $H$ such as\n",
    "\n",
    "$$ H = \\left[ \\begin{array}{cccc} 0 & 1 & 0 & 1 \\\\\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "1 & 0 & 1 & 1 \\\\\n",
    "\\end{array} \\right]$$.\n",
    "\n",
    "\n",
    "The value of the hash function $H(14)$ is now obtained by multiplying\n",
    "\n",
    "$$ \\left[ \\begin{array}{cccc} 0 & 1 & 0 & 1 \\\\\n",
    "1 & 0 & 0 & 0 \\\\\n",
    "1 & 0 & 1 & 1 \\\\\n",
    "\\end{array} \\right] \\times \\left( \\begin{array}{c} \n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "0\n",
    "\\end{array} \\right) $$\n",
    "\n",
    "The matrix multiplication is carried out using AND for multiplication and XOR instead of addition. For the example above, we compute the value of hash function as\n",
    "\n",
    "$$\\left( \\begin{array}{c} \n",
    " 0 \\cdot 1 + 1 \\cdot 1 + 0 \\cdot 1 + 1 \\cdot 0 \\\\\n",
    " 1 \\cdot 1 + 0 \\cdot 1 + 0 \\cdot 1 + 0 \\cdot 0 \\\\\n",
    " 1 \\cdot 1 + 0 \\cdot 1 + 1 \\cdot 1 + 1 \\cdot 0 \\\\\n",
    " \\end{array} \\right) = \\left( \\begin{array}{c} 1 \\\\ 1 \\\\ 0 \\end{array} \\right)$$\n",
    "\n",
    "(A) For a given matrix $H$ and two  keys $x, y$ that differ only in their $i^{th}$ bits, provide a condition for\n",
    "$Hx = Hy$ holding. (**Hint** It may help to play with examples where you have two numbers $x, y$ that just differ at a particular bit position. Figure out which entries in the matrix are multiplied with these bits that differ).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8c3d65f8037a1bde538fe08bba8152ee",
     "grade": true,
     "grade_id": "cell-c3a88ce4fd6f93c8",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d67a5c9c061598bfeb7a4b584daf27c1",
     "grade": false,
     "grade_id": "cell-31a946a30f8333d9",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "\n",
    "(B) Prove that the probability that two keys $x, y$ such that $x \\not= y$ collide under the random choice of a matrix $x, y$ is at most $\\frac{1}{2^m}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a50117b8840bd8f3ffa545de5cc35318",
     "grade": true,
     "grade_id": "cell-7d56ccdf9924a6e2",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "697f3c4a15b96784bb811130974e7e7d",
     "grade": false,
     "grade_id": "cell-85c7cffad8d9a09f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from random import random\n",
    "\n",
    "def dot_product(lst_a, lst_b):\n",
    "    and_list = [elt_a * elt_b for (elt_a, elt_b) in zip(lst_a, lst_b)]\n",
    "    return 0 if sum(and_list)% 2 == 0 else 1\n",
    "\n",
    "# encode a matrix as a list of lists with each row as a list.\n",
    "# for instance, the example above is written as the matrix\n",
    "# H = [[0,1,0,1],[1,0,0,0],[1,0,1,1]]\n",
    "# encode column vectors simply as a list of elements.\n",
    "# you can use the dot_product function provided to you.\n",
    "def matrix_multiplication(H, lst):\n",
    "    hasher = []\n",
    "    for i in H:\n",
    "        hasher.append(dot_product(i,lst))\n",
    "    return hasher\n",
    "    \n",
    "\n",
    "# Generate a random m \\times n matrix\n",
    "# see the comment next to matrix_multiplication for how your matrix must be returned.\n",
    "def return_random_hash_function(m, n):\n",
    "    # return a random hash function wherein each entry is chosen as 1 with probability >= 1/2 and 0 with probability < 1/2\n",
    "    rethash = []\n",
    "    for i in range(m):\n",
    "        fhash = []\n",
    "        for i in range(n):\n",
    "            if random() > .4:\n",
    "                fhash.append(1)\n",
    "            else:\n",
    "                fhash.append(0)\n",
    "        rethash.append(fhash)\n",
    "    return rethash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "46a6647d44a81e7c9c0bd546b453f86c",
     "grade": true,
     "grade_id": "cell-bd850b7eafce8a18",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "c1= [1, 1, 0]\n",
      "c2= [1, 0]\n",
      "c3= [1, 0]\n",
      "H= [[1, 1, 0, 0], [1, 1, 1, 1], [1, 0, 1, 1], [1, 0, 0, 1], [1, 1, 1, 1]]\n",
      "H2= [[0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 0], [1, 0, 1], [1, 0, 0]]\n",
      "Tests passed: 10 points!\n"
     ]
    }
   ],
   "source": [
    "A1 = [[0,1,0,1],[1,0,0,0],[1,0,1,1]]\n",
    "b1 = [1,1,1,0]\n",
    "c1 = matrix_multiplication(A1, b1)\n",
    "print('c1=', c1)\n",
    "assert c1 == [1,1,0] , 'Test 1 failed'\n",
    "\n",
    "A2 = [ [1,1],[0,1]]\n",
    "b2 = [1,0]\n",
    "c2 = matrix_multiplication(A2, b2)\n",
    "print('c2=', c2)\n",
    "assert c2 == [1, 0], 'Test 2 failed'\n",
    "\n",
    "A3 = [ [1,1,1,0],[0,1,1,0]]\n",
    "b3 =  [1, 0,0,1]\n",
    "c3 = matrix_multiplication(A3, b3)\n",
    "print('c3=', c3)\n",
    "assert c3 == [1, 0], 'Test 3 failed'\n",
    "\n",
    "H = return_random_hash_function(5,4)\n",
    "print('H=', H)\n",
    "assert len(H) == 5, 'Test 5 failed'\n",
    "assert all(len(row) == 4 for row in H), 'Test 6 failed'\n",
    "assert all(elt == 0 or elt == 1 for row in H for elt in row ),  'Test 7 failed'\n",
    "\n",
    "H2 = return_random_hash_function(6,3)\n",
    "print('H2=', H2)\n",
    "assert len(H2) == 6, 'Test 8 failed'\n",
    "assert all(len(row) == 3 for row in H2),  'Test 9 failed'\n",
    "assert all(elt == 0 or elt == 1 for row in H2 for elt in row ), 'Test 10 failed'\n",
    "print('Tests passed: 10 points!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "606ca2bf4aae7305f98653bae2d5416e",
     "grade": false,
     "grade_id": "cell-ec64185176df98de",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Manually Graded Answers\n",
    "\n",
    "### Problem 1\n",
    "\n",
    "The bug is in the initialization of i in the algorithm. It must be i =-1 rather than i = 0. Due to this, either the first element of the array is never considered during the partition or there could be an access to i+1 that is out of array bounds.\n",
    "\n",
    "### Problem 2 A \n",
    "\n",
    "~~~\n",
    "for k = 1 to n\n",
    "   j = partition array a with k as pivot\n",
    "~~~   \n",
    "The running time is $\\Theta(n \\times k)$.\n",
    "\n",
    "### Problem 3 A \n",
    "Since  $x,y$ differe only in their $i^{th}$ bits, we can assume $x_i = 0$ and $y_i = 1$.\n",
    "Therefore, $H x  + H_i = Hy$ wherein, $+$ refers to entrywise XOR and $H_i$ is the $i^{th}$ column of $H$.\n",
    "Thus, $Hx = Hy$ if and only if $H_i$ has all zeros.  This happens with probability $\\frac{1}{2^m}$.\n",
    "\n",
    "### Problem 3 B \n",
    "Let us assume that $x$ and $y$ differ in $k$ out of $n$ positions. We know that $Hx = Hy$ if and only\n",
    "if $Hx + Hy = 0$ where $+$ is XOR and $0$ is the vector of all zeros. But $Hx + Hy = H (x + y)$ since AND distributes over XOR.\n",
    "\n",
    "Whenever $x$ and $y$ agree in the $i^{th}$ entries, we have the $i^{th}$ entry of $(x+y)$ is zero.\n",
    "Therefore, $H(x+y)$ is just the XOR sum of $k$ columns of $H$ corresponding to positions where $x$ and $y$ differ. \n",
    "\n",
    "Thus, one of the columns must equal the sum of the remaining $k-1$ columns. Let us fix these $k-1$ columns as given and the last column as randomly chosen. The probability that each of the $m$ entries of the last column matches the sum of the first $k-1$ column is $\\frac{1}{2^m}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "eaf49ae87ad64832fba5b84cd35dc5f3",
     "grade": false,
     "grade_id": "cell-33b850d6becf61b7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## That's all folks"
   ]
  }
 ],
 "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": 4
}