210991ShlokMishraPart1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.8"
    },
    "colab": {
      "name": "210991ShlokMishraPart1.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/shlokmishra/Introduction-to-Deep-Learning-and-its-Applications/blob/main/210991ShlokMishraPart1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rvFM645NE-D2"
      },
      "source": [
        "# Assignment 1 - Part 1\n",
        "In this assignment, we will go through basic linear algebra, NumPy, and image manipulation using Python to get everyone on the same page.\n",
        "\n",
        "One of the aims of this assignment is to get you to start getting comfortable searching for useful library functions online. So in many of the functions you will implement, you will have to look up helper functions.\n",
        "\n",
        "\\\n",
        "\n",
        "## Instructions\n",
        "* This notebook contain blocks of code, you are required to complete those blocks(where required)\n",
        "* You are required to copy this notebook (\"copy to drive\" above) and complete the code.(DO NOT CHANGE THE NAME OF THE FUNCTIONS)\n",
        "\n",
        "\\\n",
        "\\\n",
        "Also, I'd like to acknowledge the Stanford CS131. This assignment is highly based on the assignments from that course."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UhSVK4RoK9q5"
      },
      "source": [
        "First Let's import some dependencies"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cCKqyfhIE-EQ"
      },
      "source": [
        "# Imports the print function from newer versions of python\n",
        "from __future__ import print_function\n",
        "\n",
        "# Setup\n",
        "\n",
        "# The Random module implements pseudo-random number generators\n",
        "import random \n",
        "\n",
        "# Numpy is the main package for scientific computing with Python. \n",
        "# This will be one of our most used libraries in this project\n",
        "import numpy as np\n",
        "\n",
        "# The Time library helps us time code runtimes\n",
        "import time\n",
        "\n",
        "\n",
        "# Some more magic so that the notebook will reload external python modules;\n",
        "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
        "%load_ext autoreload\n",
        "%autoreload 2\n",
        "%reload_ext autoreload"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "collapsed": true,
        "id": "QLtp15rqE-EU"
      },
      "source": [
        "# Part 1: Linear Algebra and NumPy Review\n",
        "In this section, we will review linear algebra and learn how to use vectors and matrices in python using numpy."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E8HDYpc0E-EV"
      },
      "source": [
        "## Part 1.1 (5 points)\n",
        "First, let's test whether you can define the following matrices and vectors using numpy. Look up `np.array()` for help. In the next code block, define $M$ as a $(4, 3)$ matrix, $a$ as a $(1, 3)$ row vector and $b$ as a $(3, 1)$ column vector:\n",
        "\n",
        "$$M = \\begin{bmatrix}\n",
        "1 & 2 & 3 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "7 & 8 & 9 \\\\\n",
        "10 & 11 & 12 \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "$$a = \\begin{bmatrix}\n",
        "1 & 1 & 0\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "$$b = \\begin{bmatrix}\n",
        "-1 \\\\ 2 \\\\ 5\n",
        "\\end{bmatrix}  \n",
        "$$ "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mETk2NCME-EX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9afc778e-b1ef-4719-ea3b-b0109cdb4ca1"
      },
      "source": [
        "### YOUR CODE HERE\n",
        "M = np.arange(1, 13).reshape(4,3)\n",
        "a = np.array([1,1,0]).reshape(1,3)\n",
        "b = np.array([-1,2,5]).reshape(3,1)\n",
        "\n",
        "### END CODE HERE\n",
        "print(\"M = \\n\", None)\n",
        "print(\"The size of M is: \", None)\n",
        "print()\n",
        "print(\"a = \", None)\n",
        "print(\"The size of a is: \", None)\n",
        "print()\n",
        "print(\"b = \", None)\n",
        "print(\"The size of b is: \", None)"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "M = \n",
            " None\n",
            "The size of M is:  None\n",
            "\n",
            "a =  None\n",
            "The size of a is:  None\n",
            "\n",
            "b =  None\n",
            "The size of b is:  None\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rSta4NheE-EZ"
      },
      "source": [
        "## Part 1.2 (5 points)\n",
        "Implement the `dot_product()` method below and check that it returns the correct answer for $a^Tb$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C5ZRjCE2MVOU"
      },
      "source": [
        "def dot_product(a, b):\n",
        "    \"\"\"Implement dot product between the two vectors: a and b.\n",
        "    (optional): While you can solve this using for loops, we recommend\n",
        "    that you look up `np.dot()` online and use that instead.\n",
        "    Args:\n",
        "        a: numpy array of shape (x, n)\n",
        "        b: numpy array of shape (n, x)\n",
        "    Returns:\n",
        "        out: numpy array of shape (x, x) (scalar if x = 1)\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    out = np.dot(a,b)\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pbLIS5vIE-Ea",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "38639ffa-2ff1-4771-955f-b8f85f43027a"
      },
      "source": [
        "# Now, let's test out this dot product. Your answer should be [[1]].\n",
        "aDotB = dot_product(a, b)\n",
        "print(aDotB)\n",
        "\n",
        "print(\"The size is: \", aDotB.shape)"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1]]\n",
            "The size is:  (1, 1)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0rGfcRU1E-Eb"
      },
      "source": [
        "## Part 1.3 (5 points)\n",
        "Implement the `complicated_matrix_function()` method and use it to compute $(ab)Ma^T$\n",
        "\n",
        "IMPORTANT NOTE: The `complicated_matrix_function()` method expects all inputs to be two dimensional numpy arrays, as opposed to 1-D arrays.  This is an important distinction, because 2-D arrays can be transposed, while 1-D arrays cannot.\n",
        "\n",
        "To transpose a 2-D array, you can use the syntax `array.T` "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dglQmbuLNOk6"
      },
      "source": [
        "def complicated_matrix_function(M, a, b):\n",
        "    \"\"\"Implement (a * b) * (M * a.T).\n",
        "    (optional): Use the `dot_product(a, b)` function you wrote above\n",
        "    as a helper function.\n",
        "    Args:\n",
        "        M: numpy matrix of shape (x, n).\n",
        "        a: numpy array of shape (1, n).\n",
        "        b: numpy array of shape (n, 1).\n",
        "    Returns:\n",
        "        out: numpy matrix of shape (x, 1).\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    out = dot_product(a,b) * dot_product(M,a.T)\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "da_uQQLhE-Ec",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "41ba54b8-3efe-4610-94b5-6b0a33e3c833"
      },
      "source": [
        "# Your answer should be $[[3], [9], [15], [21]]$ of shape(4, 1).\n",
        "ans = complicated_matrix_function(M, a, b)\n",
        "print(ans)\n",
        "print()\n",
        "print(\"The size is: \", ans.shape)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[ 3]\n",
            " [ 9]\n",
            " [15]\n",
            " [21]]\n",
            "\n",
            "The size is:  (4, 1)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6CWXxSSOE-Ed",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "769f2e68-80e6-44bd-ee06-54bc772a3be0"
      },
      "source": [
        "M_2 = np.array(range(4)).reshape((2,2))\n",
        "a_2 = np.array([[1,1]])\n",
        "b_2 = np.array([[10, 10]]).T\n",
        "print(M_2.shape)\n",
        "print(a_2.shape)\n",
        "print(b_2.shape)\n",
        "print()\n",
        "\n",
        "# Your answer should be $[[20], [100]]$ of shape(2, 1).\n",
        "ans = complicated_matrix_function(M_2, a_2, b_2)\n",
        "print(ans)\n",
        "print()\n",
        "print(\"The size is: \", ans.shape)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(2, 2)\n",
            "(1, 2)\n",
            "(2, 1)\n",
            "\n",
            "[[ 20]\n",
            " [100]]\n",
            "\n",
            "The size is:  (2, 1)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4fHLxLl4E-Ee"
      },
      "source": [
        "## Part 1.4 (10 points) [Optional/Bonus]\n",
        "Implement `eigen_decomp()` and `get_eigen_values_and_vectors()` methods. In this method, perform eigenvalue decomposition on the following matrix and return the largest k eigen values and corresponding eigen vectors (k is specified in the method calls below).\n",
        "\n",
        "$$M = \\begin{bmatrix}\n",
        "1 & 2 & 3 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "7 & 8 & 9 \\end{bmatrix}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RfaCSoRMOIc8"
      },
      "source": [
        "def eigen_decomp(M):\n",
        "    \"\"\"Implement eigenvalue decomposition.\n",
        "    (optional): You might find the `np.linalg.eig` function useful.\n",
        "    Args:\n",
        "        matrix: numpy matrix of shape (m, n)\n",
        "    Returns:\n",
        "        w: numpy array of shape (m, m) such that the column v[:,i] is the eigenvector corresponding to the eigenvalue w[i].\n",
        "        v: Matrix where every column is an eigenvector.\n",
        "    \"\"\"\n",
        "    w = None\n",
        "    v = None\n",
        "    ### YOUR CODE HERE\n",
        "    w, v= np.linalg.eig(M)\n",
        "    ### END YOUR CODE\n",
        "    return w, v"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YB120rb4ONBH"
      },
      "source": [
        "def get_eigen_values_and_vectors(M, k):\n",
        "    \"\"\"Return top k eigenvalues and eigenvectors of matrix M. By top k\n",
        "    here we mean the eigenvalues with the top ABSOLUTE values (lookup\n",
        "    np.argsort for a hint on how to do so.)\n",
        "    (optional): Use the `eigen_decomp(M)` function you wrote above\n",
        "    as a helper function\n",
        "    Args:\n",
        "        M: numpy matrix of shape (m, m).\n",
        "        k: number of eigen values and respective vectors to return.\n",
        "    Returns:\n",
        "        eigenvalues: list of length k containing the top k eigenvalues\n",
        "        eigenvectors: list of length k containing the top k eigenvectors\n",
        "            of shape (m,)\n",
        "    \"\"\"\n",
        "    eigenvalues = []\n",
        "    eigenvectors = []\n",
        "    ### YOUR CODE HERE\n",
        "    values, vectors = eigen_decomp(M)\n",
        "    order_arr = np.flip(np.argsort(np.absolute(values)))\n",
        "\n",
        "    eigenvaues = list(values[order_arr[0: k]])\n",
        "    eigenvectors = [list(vectors[:, i]) for i in order_arr[0: k]]\n",
        "    ### END YOUR CODE\n",
        "    return eigenvalues, eigenvectors"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t0_GkrJwE-Ee",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 235
        },
        "outputId": "da8bc61e-ec87-4ab6-c510-bcf21945c2b7"
      },
      "source": [
        "# Let's define M.\n",
        "M = np.array([[1,2,3],[4,5,6],[7,8,9]])\n",
        "\n",
        "# Now let's grab the first eigenvalue and first eigenvector.\n",
        "# You should get back a single eigenvalue and a single eigenvector.\n",
        "val, vec = get_eigen_values_and_vectors(M[:,:3], 1)\n",
        "print(\"First eigenvalue =\", val[0])\n",
        "print()\n",
        "print(\"First eigenvector =\", vec[0])\n",
        "print()\n",
        "assert len(vec) == 1\n",
        "\n",
        "# Now, let's get the first two eigenvalues and eigenvectors.\n",
        "# You should get back a list of two eigenvalues and a list of two eigenvector arrays.\n",
        "val, vec = get_eigen_values_and_vectors(M[:,:3], 2)\n",
        "print(\"Eigenvalues =\", val)\n",
        "print()\n",
        "print(\"Eigenvectors =\", vec)\n",
        "assert len(vec) == 2"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "error",
          "ename": "IndexError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-11-895ad57d52b2>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;31m# You should get back a single eigenvalue and a single eigenvector.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mval\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvec\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_eigen_values_and_vectors\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mM\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"First eigenvalue =\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mval\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"First eigenvector =\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvec\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mIndexError\u001b[0m: list index out of range"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Yeh-V5x1PYz5"
      },
      "source": [
        "## Part 1.5 (10 points)\n",
        "In this section, you'll implement a gaussian elimination.\n",
        "\n",
        "The algorithm to to reduce a matrix to rref using gaussian elimination contains 2 parts, First reducing the matrix to partial reduced form, then back substituting to calculate the rref. First algorithm can be summed up as:\n",
        "1. Partial pivoting: Find the kth pivot by swapping rows, to move the entry with the largest absolute value to the pivot position. This imparts computational stability to the algorithm.\n",
        "2. For each row below the pivot, calculate the factor f which makes the kth entry zero, and for every element in the row subtract the fth multiple of the corresponding element in the kth row.\n",
        "3. Repeat above steps for each unknown. We will be left with a partial r.e.f. matrix.\n",
        "\n",
        "$$\\begin{bmatrix}\n",
        "1 & 2 & 3 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "7 & 8 & 9 \\end{bmatrix}\n",
        "=>\n",
        "\\begin{bmatrix}\n",
        "7 & 8 & 9 \\\\\n",
        "4 & 5 & 6 \\\\\n",
        "1 & 2 & 3 \\end{bmatrix}\n",
        "=>\n",
        "\\begin{bmatrix}\n",
        "7 & 8 & 9 \\\\\n",
        "0 & 0.42 & 0.85 \\\\\n",
        "0 & 0.85 & 1.71 \\end{bmatrix}\n",
        "=>\n",
        "\\begin{bmatrix}\n",
        "7 & 8 & 9 \\\\\n",
        "0 & 0.85 & 1.71 \\\\\n",
        "0 & 0.45 & 0.85 \\end{bmatrix}\n",
        "=>\n",
        "\\begin{bmatrix}\n",
        "7 & 8 & 9 \\\\\n",
        "0 & 0.42 & 0.85 \\\\\n",
        "0 & 0 & -0.05 \\end{bmatrix}\n",
        "$$\n",
        "Second algorithm:\n",
        "1. Take a pivot from the last row.\n",
        "2. For each row above the pivot, calculate the factor f which makes the kth entry zero, and for every element in the row subtract the fth multiple of the corresponding element in the kth row\n",
        "3. Repeat the above step untill the matrix is in rref\n",
        "$$\\begin{bmatrix}\n",
        "7 & 8 & 0 \\\\\n",
        "0 & 0.42 & 0 \\\\\n",
        "0 & 0 & -0.05 \\end{bmatrix}\n",
        "=>\n",
        "\\begin{bmatrix}\n",
        "7 & 0 & 0 \\\\\n",
        "0 & 0.42 & 0 \\\\\n",
        "0 & 0 & -0.05 \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Steps for implementation:\n",
        "1. Complete the function `swap_rows()`\n",
        "2. Complete the function `apply_row()`\n",
        "3. Complete `forward()` and `backward()`\n",
        "4. Finally implement `rref()` using the `forward()` and `backward()`\n",
        "\n",
        "Note: You can skip this part if you want."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qUFujiFAPYz6"
      },
      "source": [
        "def swap_rows(M):\n",
        "    \"\"\"Implement row swapping to make the largest element in the pivotial column to be the first row.\n",
        "    Args:\n",
        "        matrix: numpy matrix of shape (m, n)\n",
        "    Returns:\n",
        "        Ms: matrix with swapped row\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    pass\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S8lbAUSWWpyO"
      },
      "source": [
        "def apply_rows(M):\n",
        "    \"\"\"For each row below the pivot, calculate the factor f which makes the kth\n",
        "    entry zero, and for every element in the row subtract the fth multiple of the\n",
        "    corresponding element in the kth row.\n",
        "    Args:\n",
        "        matrix: numpy matrix of shape (m, n)\n",
        "    Returns:\n",
        "        Ms: matrix with all other entries of the pivotal col zero\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    pass\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GnE_-JLxPYz7"
      },
      "source": [
        "def forward(M):\n",
        "    \"\"\"Return a partial ref using the algo described above\n",
        "    Args:\n",
        "        M: numpy matrix of shape (m, n).\n",
        "    Returns:\n",
        "        Ms: ref of M\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    pass\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wb7pPGP4XmJu"
      },
      "source": [
        "def backward(M):\n",
        "    \"\"\"Return a rref using the algo described above\n",
        "    Args:\n",
        "        M: numpy matrix of shape (m, n).\n",
        "    Returns:\n",
        "        Ms: rref of M\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    pass\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XLq81xzXYR85"
      },
      "source": [
        "def rref(M):\n",
        "    \"\"\"Return a rref using the algo descrbed above\n",
        "    Args:\n",
        "        M: numpy matrix of shape (m, n).\n",
        "    Returns:\n",
        "        Ms: ref of M\n",
        "    \"\"\"\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    pass\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Eiz6EbsWPYz8"
      },
      "source": [
        "# Let's define M.\n",
        "M = np.array([[1,2,3],[4,5,6],[7,8,9]])\n",
        "\n",
        "# Now let's calculate it's rref.\n",
        "# Note that your code may be evaluated on other test cases as well\n",
        "Mrref = rref(M)\n",
        "print(Mrref)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G46pyDzAE-Ef"
      },
      "source": [
        "## Part 1.6 (10 points)\n",
        "\n",
        "To wrap up our overview of NumPy, let's implement something fun &mdash; a helper function for computing the Euclidean distance between two $n$-dimensional points!\n",
        "\n",
        "In the 2-dimensional case, computing the Euclidean distance reduces to solving the Pythagorean theorem $c = \\sqrt{a^2 + b^2}$. where, given two points $(x_1, y_1)$ and $(x_2, y_2)$, $a = x_1 - x_2$ and $b = y_1 - y_2$.\n",
        "\n",
        "\n",
        "More generally, given two $n$-dimensional vectors, the Euclidean distance can be computed by:\n",
        "\n",
        "1. Performing an elementwise subtraction between the two vectors, to get $n$ difference values.\n",
        "2. Squaring each of the $n$ difference values, and summing the squares.\n",
        "4. Taking the square root of our sum.\n",
        "\n",
        "Alternatively, the Euclidean distance between length-$n$ vectors $u$ and $v$ can be written as:\n",
        "\n",
        "$\n",
        "\\quad\\textbf{distance}(u, v) = \\sqrt{\\sum_{i=1}^n (u_i - v_i)^2}\n",
        "$\n",
        "\n",
        "\n",
        "Try implementing this function: first using native Python with a `for` loop in the `euclidean_distance_native()` function, then in NumPy **without any loops** in the `euclidean_distance_numpy()` function.\n",
        "We've added some `assert`  statements here to help you check functionality (if it prints nothing, then your implementation is correct)!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5xvHopPqO29C"
      },
      "source": [
        "def euclidean_distance_native(u, v):\n",
        "    \"\"\"Computes the Euclidean distance between two vectors, represented as Python\n",
        "    lists.\n",
        "    Args:\n",
        "        u (List[float]): A vector, represented as a list of floats.\n",
        "        v (List[float]): A vector, represented as a list of floats.\n",
        "    Returns:\n",
        "        float: Euclidean distance between `u` and `v`.\n",
        "    \"\"\"\n",
        "    # First, run some checks:\n",
        "    assert isinstance(u, list)\n",
        "    assert isinstance(v, list)\n",
        "    assert len(u) == len(v)\n",
        "\n",
        "    # Compute the distance!\n",
        "    # Notes:\n",
        "    #  1) Try breaking this problem down: first, we want to get\n",
        "    #     the difference between corresponding elements in our\n",
        "    #     input arrays. Then, we want to square these differences.\n",
        "    #     Finally, we want to sum the squares and square root the\n",
        "    #     sum.\n",
        "    out = None\n",
        "    ### YOUR CODE HERE\n",
        "    import math\n",
        "    out = 0\n",
        "    for x in range(len(u)):\n",
        "      out += (u[x] - v[x]) ** 2\n",
        "\n",
        "    out = math.sqrt(out)\n",
        "    ### END YOUR CODE\n",
        "    return out"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wvLuK8MuO3LH"
      },
      "source": [
        "def euclidean_distance_numpy(u, v):\n",
        "    \"\"\"Computes the Euclidean distance between two vectors, represented as NumPy\n",
        "    arrays.\n",
        "    Args:\n",
        "        u (np.ndarray): A vector, represented as a NumPy array.\n",
        "        v (np.ndarray): A vector, represented as a NumPy array.\n",
        "    Returns:\n",
        "        float: Euclidean distance between `u` and `v`.\n",
        "    \"\"\"\n",
        "    # First, run some checks:\n",
        "    assert isinstance(u, np.ndarray)\n",
        "    assert isinstance(v, np.ndarray)\n",
        "    assert u.shape == v.shape\n",
        "\n",
        "    # Compute the distance!\n",
        "    # Note:\n",
        "    #  1) You shouldn't need any loops\n",
        "    #  2) Some functions you can Google that might be useful:\n",
        "    #         np.sqrt(), np.sum()\n",
        "    #  3) Try breaking this problem down: first, we want to get\n",
        "    #     the difference between corresponding elements in our\n",
        "    #     input arrays. Then, we want to square these differences.\n",
        "    #     Finally, we want to sum the squares and square root the\n",
        "    #     sum.\n",
        "\n",
        "    ### YOUR CODE HERE\n",
        "    a = np.sqrt(np.sum((u-v) ** 2))\n",
        "    ### END YOUR CODE\n",
        "    return a"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wu9MimVJE-Eg"
      },
      "source": [
        "## Testing native Python function\n",
        "assert euclidean_distance_native([7.0], [6.0]) == 1.0\n",
        "assert euclidean_distance_native([7.0, 0.0], [3.0, 3.0]) == 5.0\n",
        "assert euclidean_distance_native([7.0, 0.0, 0.0], [3.0, 0.0, 3.0]) == 5.0"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kJDk88g1E-Ej"
      },
      "source": [
        "## Testing NumPy function\n",
        "assert euclidean_distance_numpy(\n",
        "    np.array([7.0]),\n",
        "    np.array([6.0])\n",
        ") == 1.0\n",
        "assert euclidean_distance_numpy(\n",
        "    np.array([7.0, 0.0]),\n",
        "    np.array([3.0, 3.0])\n",
        ") == 5.0\n",
        "assert euclidean_distance_numpy(\n",
        "    np.array([7.0, 0.0, 0.0]),\n",
        "    np.array([3.0, 0.0, 3.0])\n",
        ") == 5.0"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "n = 1000\n",
        "\n",
        "# Create some length-n lists and/or n-dimensional arrays\n",
        "a = [0.0] * n\n",
        "b = [10.0] * n\n",
        "a_array = np.array(a)\n",
        "b_array = np.array(b)\n",
        "\n",
        "# Compute runtime for native implementation\n",
        "start_time = time.time()\n",
        "for i in range(10000):\n",
        "    euclidean_distance_native(a, b)\n",
        "print(\"Native:\", (time.time() - start_time), \"seconds\")\n",
        "\n",
        "# Compute runtime for numpy implementation\n",
        "# Start by grabbing the current time in seconds\n",
        "start_time = time.time()\n",
        "for i in range(10000):\n",
        "    euclidean_distance_numpy(a_array, b_array)\n",
        "print(\"NumPy:\", (time.time() - start_time), \"seconds\")"
      ],
      "metadata": {
        "id": "E7Z38WwHhoNl",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "40b7c9aa-a4dd-41e4-e6f4-f20504b5b043"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Native: 1.6055262088775635 seconds\n",
            "NumPy: 0.12644457817077637 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Mjik4mQXE-Ek"
      },
      "source": [
        "Next, let's take a look at how these two implementations compare in terms of runtime:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t4e6MfhHE-Em"
      },
      "source": [
        "As you can see, doing vectorized calculations (i.e. no for loops) with NumPy results in significantly faster computations! "
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Congrats You've come to the end of this notebook. If you solved everything above, impressive. If not, you might need to read/think a bit more. You can always ask doubts. Also, Note that you should submit it even if you cannot solve everything. We might evaluate these using a script later."
      ],
      "metadata": {
        "id": "XvFE0Q5bhx6-"
      }
    }
  ]
}