Exams/Midterm-Sample-Revised-Solutions.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:38ccf124fea75a9eca9a371387747caf500ee650534a4d03411a8f18257f549b"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Instructions\n",
      "----\n",
      "\n",
      "This is a \"closed book\" examination - in particular, you are not to use any resources outside of this notebook (except possibly pen and paper). You may consult help from within the notebook using ? but not any online references. You should turn wireless off or set your laptop in \"Airplane\" mode prior to taking the exam. \n",
      "\n",
      "You have 1 hour and 45 minutes to complete the exam."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import os\n",
      "import sys\n",
      "import glob\n",
      "import matplotlib.pyplot as plt\n",
      "import numpy as np\n",
      "import pandas as pd\n",
      "%matplotlib inline\n",
      "plt.style.use('ggplot')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "np.set_printoptions(formatter={'float': '{: 0.3f}'.format})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%load_ext rpy2.ipython"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 1 (10 points)**. \n",
      "\n",
      "Euclid's algorithm for finding the greatest common divisor of two numbers is\n",
      "\n",
      "```python\n",
      "gcd(a, 0) = a\n",
      "gcd(a, b) = gcd(b, a modulo b)\n",
      "```\n",
      "\n",
      "1. Write a function to find the greatest common divisor in Python (4 poinst)\n",
      "2. What is the greatest common divisor of 17384 and 1928? (1 point)\n",
      "3. Write a function to calculate the least common multiple (4 points)\n",
      "4. What is the least common multiple of 17384 and 1928? (1 point)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gcd(a, b):\n",
      "    \"\"\"Greatest common divisor.\"\"\"\n",
      "    if b == 0:\n",
      "        return a\n",
      "    else:\n",
      "        return gcd(b, a % b)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "gcd(17384, 1928?)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def lcm(a, b):\n",
      "    \"\"\"Least common multiple.\"\"\"\"\n",
      "    return (a*b)/gcd(a, b)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "lcm(17384, 1928?)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 2 (10 points)**. \n",
      "\n",
      "Consider the following matrix $A$ with dimensions (4,6), to be interpreted as 4 rows of the measurements of 6 features.\n",
      "```python\n",
      "np.array([[5, 5, 2, 6, 2, 0],\n",
      "          [8, 6, 7, 8, 9, 7],\n",
      "          [9, 5, 0, 4, 6, 8],\n",
      "          [8, 7, 9, 3, 6, 1]])\n",
      "```\n",
      "\n",
      "1. Add 1 to the first row, 2 to the second row, 3 to the third row and 4 to the fourth row using a vector `v = np.array([1,2,3,4])` and broadcasting. (2 points)\n",
      "2. Normalize A so that its row means are all 0 and call it A1. (2 points)\n",
      "3. What are the singular values of A1? (2 points)\n",
      "4. What are the eigenvalues of the covariance matrix of A1? (2 points)\n",
      "5. Find the least squares solution vector $x$ if $Ax = y$ where `y = np.array([1,2,3,4]).T` (2 points)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "A = np.array([[5, 5, 2, 6, 2, 0],\n",
      "          [8, 6, 7, 8, 9, 7],\n",
      "          [9, 5, 0, 4, 6, 8],\n",
      "          [8, 7, 9, 3, 6, 1]])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "v = np.array([1,2,3,4])\n",
      "A + v[:, None]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "A1 = A - A.mean(1)[:, None]\n",
      "A1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import scipy.linalg as la\n",
      "la.svd(A1)[1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "np.real_if_close(la.eig(np.cov(A1))[0])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "y = np.array([1,2,3,4]).T\n",
      "x = la.lstsq(A, y)[0]\n",
      "print x\n",
      "print A.dot(x)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 3 (10 points)**.\n",
      "\n",
      "1. Prove that $e^{x^2 + y^2}$ is a convex function. (5 points)\n",
      "2. Using `scipy.optimize`, find the values of $x$ and $y$ that minimize $e^{x^2 + y^2}$ in the unconstrained case and in the presence of the constraint that $x + y = 3$. Use (1,1) as a starting guess (5 points)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If you do the algebra, you will find that the eigenvalues of the Hessian are\n",
      "\n",
      "$$\n",
      "2 e^{x^2 + y^2}\n",
      "$$\n",
      "and \n",
      "$$\n",
      "2 e^{x^2 + y^2} (1 + 2 x^2 + 2 y^2)\n",
      "$$\n",
      "\n",
      "Since both eigenvlaues are positive, the fucntion is convex."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import scipy.optimize as opt\n",
      "\n",
      "def f(x):\n",
      "    return np.exp(x[0]**2 + x[1]**2)\n",
      "\n",
      "opt.minimize(f, [1,1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 28,
       "text": [
        "   status: 0\n",
        "  success: True\n",
        "     njev: 10\n",
        "     nfev: 40\n",
        " hess_inv: array([[ 0.74995545, -0.25004455],\n",
        "       [-0.25004455,  0.74995545]])\n",
        "      fun: 1.0000000000000018\n",
        "        x: array([ -2.94824895e-08,  -2.94824895e-08])\n",
        "  message: 'Optimization terminated successfully.'\n",
        "      jac: array([ -4.47034836e-08,  -4.47034836e-08])"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cons = {'type': 'eq', 'fun': lambda x: x[0] + x[1] - 3}\n",
      "opt.minimize(f, [1,1], constraints=cons)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 29,
       "text": [
        "  status: 0\n",
        " success: True\n",
        "    njev: 9\n",
        "    nfev: 44\n",
        "     fun: 90.017131300560507\n",
        "       x: array([ 1.49999954,  1.50000046])\n",
        " message: 'Optimization terminated successfully.'\n",
        "     jac: array([ 270.05131435,  270.05148602,    0.        ])\n",
        "     nit: 9"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 4 (10 points)**.\n",
      "\n",
      "A milkmaid is at point A and needs to get to point B. However, she also needs to fill a pail of water from the river en route from A to B. The equation of the river's path is shown in the figure below. What is the minimum distance she has to travel to do this?\n",
      "\n",
      "1. Solve using `scipy.optimize` and constrained minimization.\n",
      "2. Solve without using `scipy.optimize`. Hint: Use Lagrange \n",
      "\n",
      "![Milkmaid problem](milkmaid.png)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import scipy.linalg as la\n",
      "\n",
      "def f(x, A, B):\n",
      "    return la.norm(x-A) + la.norm(x-B)\n",
      "\n",
      "x0 = np.array([4, 4])\n",
      "A = np.array([2,8])\n",
      "B = np.array([8,4])\n",
      "cons = {'type': 'eq', 'fun': lambda x: x[1] - 10.0/(1 + x[0])}\n",
      "\n",
      "opt.minimize(f, x0, args=(A, B), constraints=cons)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "  status: 0\n",
        " success: True\n",
        "    njev: 31\n",
        "    nfev: 163\n",
        "     fun: 10.792179145264615\n",
        "       x: array([ 4.3987084 ,  1.85229488])\n",
        " message: 'Optimization terminated successfully.'\n",
        "     jac: array([-0.49537456, -1.44379985,  0.        ])\n",
        "     nit: 31"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Using Lagrange multipliers, you can minimize the norm of $\\nabla h$ using `scipy.optimize` without any constraints, where\n",
      "\n",
      "$$\n",
      "h(x, y, \\lambda) = \\sqrt{(x-2)^2 + (y-8)^2} + \\sqrt{(x-8)^2 + (y-4)^2}\n",
      "+ \\lambda(y - \\frac{10}{1+x})\n",
      "$$\n",
      "\n",
      "and $(x, y)$ is interpreted as a point on the river.\n",
      "\n",
      "Internally, constrained optimization mehtods may translate a constrained problem into unconstraiend optimization using this approach."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 5 (10 points)**. \n",
      "\n",
      "Find the minimum of the following quadratic function on $\\mathbb{R}^4$ \n",
      "\n",
      "$$f(x) = x^TAx +b^Tx +c$$\n",
      "where\n",
      "$$A = \\left(\\begin{matrix}13&5&0&0\\\\5&7&0&0\\\\0&0&20&-7\\\\0&0&-7&12\\end{matrix}\\right), b = \\left(\\begin{matrix}1\\\\1\\\\1\\\\1\\end{matrix}\\right) \\textrm {and } c = 2$$\n",
      "\n",
      "and $x$ is a column vector.\n",
      "\n",
      "a. Using scipy.optimize (4 points)\n",
      "\n",
      "b. Using a matrix decomposition method (library functions - no need to code your own).  Note: for full credit you should exploit matrix structure. (4 points)\n",
      "\n",
      "c. Find the minimum under the constraint $||x||^2 = 1$ (i.e. on the unit sphere in $\\mathbb{R}^4$). (2 points)\n",
      "\n",
      "**Note: Do not be overly concerned if your values for $x$ at the minimum do not match exactly **\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def func(x, A, b, c):\n",
      "    return x.T.dot(A.dot(x)) + b.T.dot(x) + c\n",
      "\n",
      "A = np.reshape([13,5,0,0,5,7,0,0,0,0,20,-7,0,0,-7,12], (4,4))\n",
      "b = np.ones((4,1))\n",
      "c = 2\n",
      "\n",
      "x0 = np.zeros((4,1))\n",
      "sol = opt.minimize(func, x0, args=(A, b, c))\n",
      "sol"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# la.solve(A, -b/2)\n",
      "la.cho_solve(la.cho_factor(A), -b/2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cons = {'type': 'eq', 'fun': lambda x: la.norm(x) - 1}\n",
      "opt.minimize(func, x0, args=(A, b, c), constraints=cons)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Question 6 (10 points)**.\n",
      "\n",
      "Given the set of vectors\n",
      "\n",
      "```\n",
      "v1 = np.array([1,2,3])\n",
      "v2 = np.array([2,4,7])\n",
      "v3 = np.array([1,0,1])\n",
      "```\n",
      "\n",
      "1. Calculate the pairwise Euclidean distance matrix using nested for loops. (2 points)\n",
      "2. Calculate the pairwise Euclidean distance matrix using numpy broadcasting. (3 points)\n",
      "3. Find an orthogonal basis for the space spanned by these vectors without using any functions from `numpy.linag` or `scipy.linalg` (5 points)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "v1 = np.array([1,2,3])\n",
      "v2 = np.array([2,4,7])\n",
      "v3 = np.array([1,0,1])\n",
      "\n",
      "def dist(u, v):\n",
      "    w = u - v\n",
      "    return np.sqrt(np.sum(w**2))\n",
      "\n",
      "D = np.array([[dist(u1, u2) for u1 in [v1, v2, v3]] for u2 in [v1, v2, v3]])\n",
      "D"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 48,
       "text": [
        "array([[ 0.        ,  4.58257569,  2.82842712],\n",
        "       [ 4.58257569,  0.        ,  7.28010989],\n",
        "       [ 2.82842712,  7.28010989,  0.        ]])"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "vs = np.column_stack([v1, v2, v3])\n",
      "np.sqrt(np.sum((vs[:,None, :] - vs[:,:,None])**2,0))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 50,
       "text": [
        "array([[ 0.        ,  4.58257569,  2.82842712],\n",
        "       [ 4.58257569,  0.        ,  7.28010989],\n",
        "       [ 2.82842712,  7.28010989,  0.        ]])"
       ]
      }
     ],
     "prompt_number": 50
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}