Prereq.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__How many multiplications and additions do you need to perform a matrix multiplication between a (n, k) and (k, m) matrix? Explain.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A single row and a column have k multiplications and n-1 additions. Hence, total no. of multiplications would be k * n * m and additions would be n-1 * n * m."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Write Python code to multiply the above two matrices. Solve using list of lists and then use numpy. Compare the timing of both solutions. Which one is faster? Why?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[8 6 4]\n",
      " [6 5 2]\n",
      " [4 1 1]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "n=3; m=4; k=3;\n",
    "A=np.random.randint(10,size=(n,k))\n",
    "B=np.random.randint(10,size=(k,m))\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[42, 110, 64, 32], [23, 87, 48, 16], [10, 37, 22, 8]]\n"
     ]
    }
   ],
   "source": [
    "#list of lists method\n",
    "res=[[None]*m, [None]*m, [None]*m]#using *n updates all rows (undesirable)\n",
    "for x in range (0,n):\n",
    "    for y in range (0,m):\n",
    "        ele=0\n",
    "        for z in range (0,k):\n",
    "            ele+=A[x,z]*B[z,y]\n",
    "        res[x][y]=ele\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 42 110  64  32]\n",
      " [ 23  87  48  16]\n",
      " [ 10  37  22   8]]\n"
     ]
    }
   ],
   "source": [
    "np_res=np.dot(A,B)\n",
    "print(np_res)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Surprisingly the numpy dot method is slower. Probably considering each element as complex numbers and hence leading to an increase in multiplication and addition operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Finding the highest element in a list requires one pass of the array. Finding the second highest element requires 2 passes of the the array. Using this method, what is the time complexity of finding the median of the array? Can you suggest a better method? Can you implement both these methods in Python and compare against numpy.median routine in terms of time?__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If n is the no. of elements in an array/list, to find the maximum element, n elements would need to be iterated over i.e. O(n). To get the 2nd maximum element, another n-1 iterations would be required i.e. O(n-1). Hence, in order to obtain the median, n*...(n+1)/2 in case n is odd and n*..(n/2)+1 in case n is even iterations are required."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "l1=[1, 7, 2, 3, 4] #assuming all positive and non repeating\n",
    "n=len(l1)\n",
    "max=19999\n",
    "for i in range (0,(n+1)//2):\n",
    "    maxPrev=max#very high number initially\n",
    "    max=l1[0]\n",
    "    for j in range (1,n):\n",
    "        maxi=l1[j]\n",
    "        if maxi>max and maxi<maxPrev:\n",
    "            max=maxi\n",
    "\n",
    "print(max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "li=[1,7,2,3,4]\n",
    "#maxi=[li[-1]] #only if n is odd \n",
    "min=li[-1]\n",
    "for i in range(0,n-1,2):\n",
    "    if li[i]>=li[i+1]:\n",
    "        ele=li[i]\n",
    "        #maxi.append(li[i])\n",
    "    else:\n",
    "        ele=li[i+1]\n",
    "        #maxi.append(li[i+1])\n",
    "    if ele<min:\n",
    "        min=ele\n",
    "#min=maxi[0]\n",
    "#for i in range (1,(n+1)//2):\n",
    "    #ele=maxi[i]\n",
    "    #if ele<min:\n",
    "        #min=ele\n",
    "print(min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n"
     ]
    }
   ],
   "source": [
    "li=[1,7,2,3,4]\n",
    "med=np.median(li)\n",
    "print(med)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__What is the gradient of the following function with respect to x and y?__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient with respect to x = $$2xy+y^3cos(x)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient with respect to y = $$ x^2+3y^2sin(x)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Use JAX to confirm the gradient evaluated by your method matches the analytical solution corresponding to a few random values of x and y__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.021980009997619385\n",
      "0.02198001\n"
     ]
    }
   ],
   "source": [
    "import jax\n",
    "import jax.numpy as jnp\n",
    "x=0.1; y=0.2;\n",
    "def f(x,y):\n",
    "    return x**2*y+y**3*jnp.sin(x)\n",
    "grad_fy=jax.grad(f,argnums=1)\n",
    "grad_fx=jax.grad(f,argnums=0)\n",
    "valx_jax=grad_fx(x,y)\n",
    "valx=2*x*y+y**3*np.cos(x)\n",
    "valy=x**2+3*y**2*np.sin(x)\n",
    "valy_jax=grad_fy(x,y)\n",
    "print(valy)\n",
    "print(valy_jax)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Use sympy to confirm that you obtain the same gradient analytically.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matrix([[2*x*y + y**3*cos(x), x**2 + 3*y**2*sin(x)]])\n"
     ]
    }
   ],
   "source": [
    "import sympy as sym\n",
    "#from sympy.abc import x, y\n",
    "x,y=sym.symbols('x,y')\n",
    "exp=x**2*y+y**3*sym.sin(x)\n",
    "v=list(sym.ordered(exp.free_symbols))\n",
    "gradient=lambda f,v: sym.Matrix([f]).jacobian(v)\n",
    "print(gradient(exp,v))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.1 64-bit",
   "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.9.1"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "f5b775166e527c2c4c8c7a313eadde439897f6893f91e429bbc029ec9a09e8d5"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}