L0 - python3 and jupyter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setting up your `python` environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will be using `python 3` and `ipython notebook`/`jupyter` extensively in this course. You need to set up the correct `python` environment first. Below are some instructions in a Mac OS X 10.11 environment. You should be able to adapt it to other environments -- try Google if any problem.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Installing `anaconda` and `jupyter`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Download and install the `anaconda` installation package (for `python 3.6`) at https://www.continuum.io/downloads\n",
    "2. Create a `py36` virtual environment by `conda create -n py36 python=3.6 anaconda`. See more at http://conda.pydata.org/docs/using/envs.html\n",
    "3. Activiate `py36` (or put it on your `~/.bashrc`): `source activate py36`\n",
    "4. To install a new package in an environment, switch to it and use `conda install -n PACKAGENAME` or `pip install PACKAGENAME`\n",
    "5. Install `jupyter` by `conda install jupyter`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test you installation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "% python -V\n",
    "Python 3.6.1 :: Anaconda 4.4.0 (x86_64)\n",
    "% ipython -V\n",
    "5.3.0\n",
    "% jupyter notebook\n",
    "```\n",
    "\n",
    "\n",
    "The last command shall open up a new page in your browser. Also check if you click the \"new\" button, there is a \"python 3\" choice under the 'notebooks'. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using `jupyter`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start with simple tutorial: https://jupyter-notebook-beginner-guide.readthedocs.io/en/latest/index.html\n",
    "\n",
    "Press `h` (you may need to press `ESC` first) to learn a few important keyboard shortcuts, e.g., \n",
    "\n",
    "* `SHIFT+RETURN`\n",
    "* `A`, `B`, `X`\n",
    "* `ESC`\n",
    "* `ESC m`: to change the current cell to a `markdown` cell, \n",
    "* selecting multiple lines + `TAB` (indent them) / `Cmd + /` (block comment). \n",
    "* Note that mouse selection = copying to clipboard (sometimes annoying). \n",
    "\n",
    "Read the syntax of `markdown` at http://jupyter-notebook.readthedocs.io/en/latest/examples/Notebook/Working%20With%20Markdown%20Cells.html and try it out by yourself. \n",
    "\n",
    "It also can display maths symbols/equations, e.g., $e^{ix} = cos(x) + i \\cdot sin(x)$.\n",
    "\n",
    "$$ P \\implies Q  \\qquad \\equiv \\qquad P \\lor \\neg Q $$\n",
    "\n",
    "Try out cells with simple python code (or try the following cell in this notebook). \n",
    "\n",
    "**Tips**: \n",
    "\n",
    "* Recommended browser: firefox (Chrome has issues rendering maths fonts/equations)\n",
    "* Your code may run into an infinite loop and you may HAVE TO kill the browser. So use a decent session manager for your browser. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 7, 3, 5, 7, 7, 7, 1, 10, 4]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "n = 10\n",
    "data = [random.randint(1, 10) for _ in range(n)]\n",
    "data # this print out the variable's content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1: Integer square root of an integer \n",
    "\n",
    "You need to write a function, `nsqrt()`, that takes as input an integer `x`, and return the largest integer that does not exceed $\\sqrt{x}$. You need to abide by the following constraints:\n",
    "1. The time complexity of your algorithm should be $O(\\log x)$. \n",
    "2. You cannot use `sqrt()` function. \n",
    "\n",
    "For example, `nsqrt(11) = 3`, and `nsqrt(1369) = 37`. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def nsqrt(x): # do not change the heading of the function\n",
    "    \n",
    "    pass # **replace** this line with your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can test your implementation using the following code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 37\n"
     ]
    }
   ],
   "source": [
    "print(nsqrt(11), nsqrt(1369))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2: Root finding \n",
    "\n",
    "Use [Newton's method](https://en.wikipedia.org/wiki/Newton's_method) to find a root of an equation numerically. Newton's method starts from $x_0$ and iteratively computes $$x_{i+1} = x_i - \\frac{f(x_i)}{f'(x_i)}.$$\n",
    "\n",
    "Let us consider find a $x$ such that $f(x) = x \\ln(x) - 16 = 0$. First, we plot the function and it seems $x$ is close to 8.0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHvNJREFUeJzt3Xd8VfXh//HXh4RACCOEhGFCCHvvEIYV5YcVqdaNSlUU\nB0gdtV8XjrZa9au2Ks5aqVqQKcoScKK2ah2QECBhhchKQiAJmWQn9/P9g+iD+gMZybnn5t738/Hg\nkdzB/bxvSN45fM7nnGOstYiIiP9r4nYAERHxDhW+iEiAUOGLiAQIFb6ISIBQ4YuIBAgVvohIgFDh\ni4gECBW+iEiAUOGLiASIYLcDHC0yMtLGxcW5HUNEpFFJSkrKs9ZGneh5PlX4cXFxJCYmuh1DRKRR\nMcbsPZnnaUpHRCRAqPBFRAKECl9EJECo8EVEAoQKX0QkQKjwRUQChApfRCRAqPBFRFy24Lu9fLkz\n1/FxVPgiIi6x1vLC2p08tDyVJYmZjo/nU0faiogEilqP5dFVW3jrm71cPiyGpy4f6PiYKnwRES+r\nrKnlf5ZsYs3mbKaP7cbMiX0wxjg+rgpfRMSLDlfWcOu8JL5Kz+PBX/Vh2tjuXhtbhS8i4iWHDlcy\ndc56tuwv5plJg7lieIxXx1fhi4h4QUZ+GVPeXEd2UTmzrxvO+L4dvJ5BhS8i4rDtB4qZ8sY6Kqpr\nmX/TSOLjIlzJocIXEXHQut353Dx3PaEhQbxz6xh6d2zlWhYVvoiIQz5MPcCdi5OJaRvK3KkJdI5o\n4WoeFb6IiAPmf7uXP65MZVBMOG/eMIKIsBC3I6nwRUQakrWWWWt38uKnOxnXO4pXrhlGixDfqFrf\nSCEi4gdqaj38YWUqi9ZlMGl4DP972UCaBvnOGWxU+CIiDaCiupbbFyazdttBbhvXnXvO6+2Vo2dP\nheOFb4zZA5QAtUCNtTbe6TFFRLypsKyKm+YmsmFfAY9e1J/rx8S5HemYvLWFP85am+elsUREvGZ/\nYTlT3lzHvkNlvDx5GBcM6uR2pOPSlI6IyGlKO1jClDfWUVpZw9wbExjdvZ3bkX6WN/YmWGCtMSbJ\nGDPNC+OJiDhu3e58rnj1azzW8vb00T5f9uCdLfxfWGuzjDHtgU+MMduttV/88GDdL4FpALGxsV6I\nIyJSPx9tOcAdi5KJCQ9l7o3uH1B1shzfwrfWZtV9zAGWAwk/eXy2tTbeWhsfFRXldBwRkXpZ8N1e\nZsxPol+n1rw7Y0yjKXtwuPCNMWHGmFY/fA6cB6Q6OaaIiBOstcz6JI2Hlqdydq8oFt4y0ieOnj0V\nTk/pdACW161FDQYWWms/dHhMEZEGdeSAqi0sWrePK4bH8KSPHVB1shwtfGvtLmCwk2OIiDiporqW\nOxYl88lW3z2g6mRpWaaIyHEUllVx89xEkvYV8Miv+3HDmV3djlQvKnwRkWPIyC/jhn+uIyO/nJcm\nD+XCQWe4HaneVPgiIj+RmlXE1Dnrqayu5a2bEhjVzffX2J8MFb6IyFG+SMtlxvwk2oQ2ZcGMMfTq\n4N4VqhqaCl9EpM47iRk8sCyFnh1aMWfqCDq0bu52pAalwheRgGet5aXP0nnukzR+0SOSV68dRqvm\nTd2O1eBU+CIS0GpqPTy8IpXF6zO4bGg0T10+iJDgxrfG/mSo8EUkYJVW1nD7wg18viOX28f14O7z\nejXaNfYnQ4UvIgEpt6SSG+esZ8v+Ip64dADXjOzidiTHqfBFJODsyj3M9f9cR15JFf+YEs/4vh3c\njuQVKnwRCShJe/O5eW4iTYxh0bRRDOkc7nYkr1Hhi0jA+DD1AL9bnEynNs2Ze2MCXdqFuR3Jq1T4\nIhIQ5n69h0dWbWFI53BenxJPu5bN3I7kdSp8EfFrHo/l6Q+389oXu/hlvw68ePVQQkOC3I7lChW+\niPityppa7nlnM6s27ee6UV145KL+BDXx32WXJ6LCFxG/VFRezfR5iXy7K5+ZE/swfWw3v15jfzJU\n+CLidzLyy5g6Zz17D5XywtVDuHhItNuRfIIKX0T8ysaMQm6eu57qWsu8m0b6zamNG4IKX0T8xkdb\njiy7jGrVjMU3JNCjfUu3I/kUFb6I+IU3vtrN42u2MjgmnNevjycyAJddnogKX0QatVqP5bHVW5nz\n9R7O79+RWVcNCdhllyeiwheRRqusqoY7FyWzdlsOt5zVlQcm9qVJAC+7PBEVvog0SjnFFdw0N5Et\n+4v488X9mTI6zu1IPk+FLyKNTtrBEqb+cz0FZYF1tsv6UuGLSKPy1c48ZsxPIjQkiCXTRzMguo3b\nkRoNFb6INBpLEjN4cFkK3aNa8ubUEUSHh7odqVFR4YuIz7PW8twnabz0WTpn9YzklWuG0doPLzLu\nNBW+iPi0yppa7nt3Mys37ueq+M48fukAmgb550XGnabCFxGfVVhWxbR5Sazbnc+9E3rz23O6B/wJ\n0OpDhS8iPmnvoVKmzllPZn65ToDWQFT4IuJz1u3OZ/q8RCww/+aRJHSNcDuSX1Dhi4hPWbYhk5lL\nU4hpG8obN4yga2RgXXfWSSp8EfEJHs+RlTgvf57OqG4R/P3a4YS3CHE7ll9R4YuI6yqqa7n7nU2s\n2ZzNlfExPH7JQEKCtRKnoTn+FTXGnG+M2WGMSTfGzHR6PBFpXHJLKrl69re8n5LNzIl9ePryQSp7\nhzi6hW+MCQJeAX4JZALrjTHvWWu3OjmuiDQO2w8Uc9OcRA6VVvLqNcM5f0BHtyP5NaendBKAdGvt\nLgBjzGLgYqDhC/+DmXAgpcFfVkScUVBeRcnBw7zYxNA7uhUt1wfDerdTuajjQJj4lKNDOP3/pmgg\n46jbmXX3/cgYM80Yk2iMSczNzXU4joj4ggPF5ew4UEKzpk0YEN2als20O9EbXP8qW2tnA7MB4uPj\n7Wm/kMO/GUWk/mpqPfx59Vbe2rGXc/t24IWrh9BMZe81Tn+ls4DOR92OqbtPRAJMSUU1ty9M5t9p\nudxyVldmTuxLkK5O5VVOF/56oKcxpitHiv5q4DcOjykiPiYjv4yb5q5nV24pT142kMkJsW5HCkiO\nFr61tsYYczvwERAEvGmt3eLkmCLiWzbsK2DaW4lU1niYe2MCZ/aIdDtSwHJ88sxa+z7wvtPjiIjv\nWbVpP3e/s4mOrZuzeNoIerRv6XakgKa9JSLS4Dwey/Of7uTFT3cyIq4tr10XT0SYTpPgNhW+iDSo\nsqoa7nlnE++nHGDS8Bgev3QAzYKD3I4lqPBFpAHtLyznlrcS2ZpdzEO/6svNZ3XVBUt8iApfRBrE\nkZ2zSVRU1/Lm9SMY16e925HkJ1T4IlJvy5MzuX9pCh1bN2fRLSPp2aGV25HkGFT4InLaPB7LXz/e\nwav/+p5R3SJ49ZrhtNXOWZ+lwheR03K4soa7Fm9k7baD/GZkLI9e1J+mQTqtsS9T4YvIKcvIL+OW\ntxLZmXOYRy/qz5TRXbRzthFQ4YvIKVm/J5/p85KoqfUwZ+oIzuoZ5XYkOUkqfBE5aUvWZ/DQihQ6\nt23B69fH0y1KR842Jip8ETmhWo/lyfe38fpXuzmrZyQvTx5GmxZN3Y4lp0iFLyI/q7iimjsXJfOv\nHbncMCaOhy/oS7B2zjZKKnwROa49eaXc/FYie/JK+d9LB/KbkTqtcWOmwheRY/p3Wi53LNxAUBPD\nvJtGMrp7O7cjST2p8EXkv1hrmf3FLp7+cDu9OrTiH1Pi6RzRwu1Y0gBU+CLyo4rqWu5fupmVG/dz\nwcBO/HXSIFqEqCb8hf4lRQSArMJyps9LZMv+Yu6d0JvfntNdB1P5GRW+iLBudz6/XZBERbWH16fE\nM75vB7cjiQNU+CIBbv63e3nkvS3ERrRg8bR4XYbQj6nwRQJUVY2HR1ZtYeF3+zindxQvXD2UNqE6\nmMqfqfBFAlBuSSW/XZDE+j0FzDinO/ec15ugJpqv93cqfJEAszmzkOnzkigoq+LFyUO5aPAZbkcS\nL1HhiwSQFclZ3L90M5Etm/HurWMYEN3G7UjiRSp8kQBQ67E8/eF2Zn+xi4SuEbx6zTDatWzmdizx\nMhW+iJ8rKK3izsXJfLkzjymju/CHC/vpylQBSoUv4sdSs4q4dX4SOcWVPHXZQK5O0MnPApkKX8RP\nLduQyQPLUogIC2HJraMZ0jnc7UjiMhW+iJ+prvXw+OqtzP1mLyO7RvDKNcOI1Hy9oMIX8Ss5JRXc\ntmAD6/cUcPMvujJzYh9drER+pMIX8RNJewuYMT+Jkooara+XY1LhizRy1lrmf7ePP6/awhnhocy9\nMYG+nVq7HUt8kApfpBGrqK7l4RWpvJuUybjeUTx/1VBdXFyOS4Uv0khlFpQxY/4GUrKKuHN8T+4a\n35MmOh+O/AzHCt8Y8whwC5Bbd9eD1tr3nRpPJJB8tTOPOxZtoKbW8vqUeM7tp/PXy4k5vYU/y1r7\njMNjiASMo6832z2qJa9dN5xuUTp/vZwcTemINBIlFdXMXJrCmpRsLhjYib9cMYiwZvoRlpPn9HfL\nHcaYKUAicLe1tsDh8UT80o4DJcyYn8SeQ6U8MLEP08Z20/Vm5ZTVq/CNMWuBjsd46CHgVeAxwNZ9\nfBa48RivMQ2YBhAbq/N8iPzU8uRMHlyWSlizYBbeMopR3dq5HUkaKWOtdX4QY+KA1dbaAT/3vPj4\neJuYmOh4HpHGoLKmlsdWb2X+t/tI6BrBy5OH0r51c7djiQ8yxiRZa+NP9DwnV+l0stZm1928FEh1\naiwRf5NZUMZtCzawKbOI6WO7ce+E3jpFgtSbk3P4fzHGDOHIlM4eYLqDY4n4jc+353DX2xvxeCyv\nXTecCf2PNWsqcuocK3xr7XVOvbaIP6r1WF5Ym8aLn6XTp2Mr/n7tcOIiw9yOJX5Ea7pEfMChw5Xc\n9fZGvtyZx6ThMTx2yQCaNw1yO5b4GRW+iMuS9hZw24IN5JdV8fTlA7lqhFariTNU+CIusdYy5+s9\nPLFmG53Cm7NsxhgGRLdxO5b4MRW+iAsOV9Ywc+lmVm/O5ty+7Xl20hCd5VIcp8IX8bKt+4u5beEG\n9h4q5b7ze3Pr2O46y6V4hQpfxEustSxct49HV20lPLQpi24ZxUgdNStepMIX8YKSimoeWJbC6s3Z\nnNUzkllXDdGFxcXrVPgiDkvNKuL2hRvYl1/GvRN6M+NsTeGIO1T4Ig754Vqzj63eStsWmsIR96nw\nRRxQUlHNzGUprNmczdheUcy6cjDtNIUjLlPhizSwH6ZwMgrKtQpHfIoKX6SB/DiFs2orEWEhLJ42\nihFxEW7HEvmRCl+kARRXVPNA3eUHz+4VxayrhhARFuJ2LJH/osIXqafNmYXcsSiZzIJy7j+/D9PH\ndtMUjvgkFb7IafJ4LK9/tYu/fLiD9q2aaQpHfJ4KX+Q05JZUcvc7m/giLZcJ/Tvw9OWDCG+hKRzx\nbSp8kVP077Rc7l6ykZKKGh6/ZADXjIzFGE3hiO9T4YucpKoaD898vIPZX+yiV4eWLLh5FL07tnI7\nlshJU+GLnIQ9eaXcuTiZzZlFXDsqlocv6KcrUkmjo8IXOYHlyZk8vDyV4KAm/P3a4Zw/QBcVl8ZJ\nhS9yHIcra/jjilSWJWeREBfBrKuHEB0e6nYskdOmwhc5hs2Zhdy5KJl9+WXcdW5Pbh/Xg+CgJm7H\nEqkXFb7IUWo9ln98uYtnP95BVMtmvD19tNbWi99Q4YvUySos53/e3sh3u/OZOKAjT142UGvrxa+o\n8EWAlRuzeHhFKh6P5ZlJg7l8WLTW1ovfUeFLQCsqr+ZPK1NZsXE/w7u0ZdaVQ4ht18LtWCKOUOFL\nwPp21yHuXrKJA8UV/M8ve/Hbc7prx6z4NRW+BJyqGg+z1qbx939/T5eIFiydMYYhncPdjiXiOBW+\nBJT0nMPc9XYyqVnFTE7ozMMX9COsmX4MJDDoO10CgrWW+d/u5Yn3txHaNIjXrhvOhP46YlYCiwpf\n/F5OcQX3L93M5ztyObtXFH+9YhDtWzd3O5aI16nwxa+9t2k/f1iRSmVNLY/8uh/Xj4nTcksJWCp8\n8Uv5pVX8YWUqazZnM6RzOM9dOZhuUS3djiXiqnqtQTPGTDLGbDHGeIwx8T957AFjTLoxZocxZkL9\nYoqcvLVbD3LerC/4eMsB7p3Qm3dvHa2yF6H+W/ipwGXAa0ffaYzpB1wN9AfOANYaY3pZa2vrOZ7I\ncRVXVPPYqq28k5RJn46tmHdTAn07tXY7lojPqFfhW2u3AceaE70YWGytrQR2G2PSgQTgm/qMJ3I8\nX6fnce+7m8kuKuf2cT24c3xPQoJ1EJXI0Zyaw48Gvj3qdmbdfSINqryqlqc/3M6cr/fQLTKMpTPG\nMDS2rduxRHzSCQvfGLMWONaC5YestSvrG8AYMw2YBhAbG1vfl5MAkrS3gHve2cTuvFKmnhnHfRP6\nEBqiyw6KHM8JC99ae+5pvG4W0Pmo2zF19x3r9WcDswHi4+PtaYwlAaaiupbnPknj9S930alNKAtv\nGcmY7pFuxxLxeU5N6bwHLDTGPMeRnbY9gXUOjSUBZN3ufO5fupndeaVMTojlwV/1oVXzpm7HEmkU\n6lX4xphLgZeAKGCNMWajtXaCtXaLMWYJsBWoAW7TCh2pj9LKGv760Q7mfrOH6PBQFtw8kjN7aKte\n5FTUd5XOcmD5cR57AniiPq8vAvCf9DzuX7qZzIJybhgTx70TeuuEZyKnQT814rOKK6p58v3tLFq3\nj66RYSyZPpqErrq+rMjpUuGLT/p8Rw4PLkvhYHEF08Z24/fn9tIKHJF6UuGLTyksq+Kx1dtYuiGT\nnu1b8jetqxdpMCp88QnWWtakZPPIe1spKKvi9nE9uGN8D5oFa6tepKGo8MV1mQVl/HHlFj7bnsOA\n6NbMmTqCAdFt3I4l4ndU+OKaWo9lztd7ePbjHVgLD1/QlxvGxOlC4iIOUeGLK1KzinhgWQopWUWc\n0zuKxy4eQOeIFm7HEvFrKnzxqrKqGp5fu5M3vtpN2xZNeWnyUC4c1ElXoRLxAhW+eM2/03J5aHkK\nmQXlTE7ozMzz+9KmhU6LIOItKnxxXE5xBY+v2cZ7m/bTLSqMt6eNYmS3dm7HEgk4KnxxTE2th7e+\n2cusT9KorPFw5/ie3Dauu5ZairhEhS+OSNpbwMMrUtmWXczYXlE8elF/ukaGuR1LJKCp8KVB5ZdW\n8dQH21iSmEnH1s352zXDmDigo3bKivgAFb40CI/Hsnh9Bn/5aDuHK2qYPrYbd47vqbNaivgQ/TRK\nvaVkFvHwylQ2ZRSS0DWCxy8ZQK8OrdyOJSI/ocKX03bocCXPfZLGonX7iAgL4bkrB3Pp0GhN34j4\nKBW+nLLqWg/zvtnL82vTKK2qZcroOH7/y160CdWaehFfpsKXU/JFWi5/Xr2V9JzDnNUzkj9e2I+e\nmr4RaRRU+HJSdueV8sSarazdlkOXdi34x5R4zu3bXtM3Io2ICl9+VklFNS9/ns6bX+0mJKgJMyf2\nYeqZcTp4SqQRUuHLMdV6LO8kZvDMx2nkHa7kiuEx3DehN+1bN3c7moicJhW+/BdrLf/akcuTH2wj\n7eBhhsWG88b18QzuHO52NBGpJxW+/Cg1q4gnP9jGf9IP0aVdCx0lK+JnVPhCVmE5z360g+UbswgP\nbcqfft2Pa0Z2ISRYV54S8Scq/ABWXFHN3z7/njf/sxuA6WO7M+Oc7lpPL+KnVPgBqKK6lre+2cOr\n//qewvJqLh0Szd0TehMdHup2NBFxkAo/gFTVeHg7MYOXPt1JTkklY3tFcd+E3gyIbuN2NBHxAhV+\nAKj1WFYkZ/H8p2lk5JczIq4tL/9mGAldI9yOJiJepML3Y9ZaPkw9wLOfpJGec5gB0a15bOoAzu4V\npZU3IgFIhe+HPB7LJ9sO8tJnO0nNKqZH+5a8es0wztcSS5GApsL3Ix6P5YPUA7z02U62Hyghrl0L\nnp00mEuGRhPUREUvEuhU+H6g1mNZvXk/L3+Wzs6cw3SPCuP5q4Zw4aBOBAdpLb2IHKHCb8Rqaj2s\n3LifVz5PZ1deKb06tOSlyUP51cBO2qIXkf+PCr8RKq2s4e31Gbzx1W6yCsvp26k1f792GOf160gT\nFb2IHEe9Ct8YMwl4BOgLJFhrE+vujwO2ATvqnvqttfbW+owlkFNSwdyv9zD/230UlVczIq4tj17U\nn/E6L72InIT6buGnApcBrx3jse+ttUPq+foCfJ97mH98sYtlyVlU13qY0K8j087uxrDYtm5HE5FG\npF6Fb63dBmjr0gEej+XL9Dze+noPn+3IoWlQE64YHsPNv+hKt6iWbscTkUbIyTn8rsaYjUAR8LC1\n9stjPckYMw2YBhAbG+tgnMahuKKapUmZzPtmL7vySolsGcId43owZUwckS2buR1PRBqxExa+MWYt\n0PEYDz1krV15nL+WDcRaaw8ZY4YDK4wx/a21xT99orV2NjAbID4+3p58dP+y82AJc7/Zw7INWZRV\n1TI0NpznrxrCxIEddTlBEWkQJyx8a+25p/qi1tpKoLLu8yRjzPdALyDxlBP6sbKqGlZvzmbJ+gwS\n9xYQEtyEiwafwZTRXRgUoytMiUjDcmRKxxgTBeRba2uNMd2AnsAuJ8ZqbKy1JGcUsmR9Bqs27ae0\nqpZukWHMnNiHScNjaKdpGxFxSH2XZV4KvAREAWuMMRuttROAscCfjTHVgAe41VqbX++0jVhGfhmr\nNu9nRXIWaQcPE9o0iAsGdeKqEZ2J79JWO75FxHH1XaWzHFh+jPuXAkvr89r+IKekgjWbs1m1aT8b\n9hUCMCw2nKcuG8iFg8+gZTMd9yYi3qPGaWBZheV8uu0gH205wDffH8JjoW+n1tx3fm9+PegMOke0\ncDuiiAQoFX49eTyW1P1FrN16kLXbctiafWQhUreoMG4f14NfDz6Dnh1auZxSRMRPCr+0soY/vbeF\ne87rTcc2zR0dy1rLnkNl/Cc9j6+/z+Ob7w9RUFZNEwPxXSJ48Fd9GN+3A911cJSI+Bi/KPztB4r5\nICWbz7bn8LvxPZkUH0OLkIZ5a2VVNaRkFrEps5BNGUVs2FdAdlEFAB1bN2dcn/b8okck5/RuT0RY\nSIOMKSLiBGOt7xzrFB8fbxMTT2+pfnrOYR5clsK6PfmENg1iXJ8o4rtEMLhzOJ0jQolq2ey4K2HK\nqmo4WFxJTnEFmQXlpOceJj3nMN/nHGbPoVI8dV+imLahDO4czuhu7RjTvR1dI8O0ukZEXGeMSbLW\nxp/wef5S+HBkuiVxbwHLNmTxrx05P26JA4QEN6F182CaBQfRLLgJlTUeKmtqKas68udowU0McZFh\n9IhqSa+OrRjSuQ2DYsJ1agMR8UknW/h+MaXzA2MMI+IiGBEXAUB2UTlbsorJKixnf2E5JZU1VFTX\nUlnjoVlQE5qHBBHaNIjIls1o36oZHVo3p1N4c2IjWtBUV4oSET/jV4X/U53ahNKpTajbMUREfII2\nY0VEAoQKX0QkQKjwRUQChApfRCRAqPBFRAKECl9EJECo8EVEAoQKX0QkQPjUqRWMMbnA3tP865FA\nXgPGaQz0ngOD3nNgqM977mKtjTrRk3yq8OvDGJN4MueS8Cd6z4FB7zkweOM9a0pHRCRAqPBFRAKE\nPxX+bLcDuEDvOTDoPQcGx9+z38zhi4jIz/OnLXwREfkZflH4xpjzjTE7jDHpxpiZbudxmjGmszHm\nc2PMVmPMFmPM79zO5A3GmCBjTLIxZrXbWbzFGBNujHnXGLPdGLPNGDPa7UxOM8b8vu77OtUYs8gY\n09ztTA3NGPOmMSbHGJN61H0RxphPjDE76z62behxG33hG2OCgFeAiUA/YLIxpp+7qRxXA9xtre0H\njAJuC4D3DPA7YJvbIbzsBeBDa20fYDB+/v6NMdHAnUC8tXYAEARc7W4qR8wBzv/JfTOBT621PYFP\n6243qEZf+EACkG6t3WWtrQIWAxe7nMlR1tpsa+2Gus9LOFIC0e6mcpYxJga4AHjd7SzeYoxpA4wF\n3gCw1lZZawvdTeUVwUCoMSYYaAHsdzlPg7PWfgHk/+Tui4G5dZ/PBS5p6HH9ofCjgYyjbmfi5+V3\nNGNMHDAU+M7dJI57HrgP8LgdxIu6ArnAP+umsl43xoS5HcpJ1tos4BlgH5ANFFlrP3Y3ldd0sNZm\n131+AOjQ0AP4Q+EHLGNMS2ApcJe1ttjtPE4xxlwI5Fhrk9zO4mXBwDDgVWvtUKAUB/6b70vq5q0v\n5sgvuzOAMGPMte6m8j57ZPlkgy+h9IfCzwI6H3U7pu4+v2aMacqRsl9grV3mdh6HnQlcZIzZw5Ep\nu/9njJnvbiSvyAQyrbU//O/tXY78AvBn5wK7rbW51tpqYBkwxuVM3nLQGNMJoO5jTkMP4A+Fvx7o\naYzpaowJ4cgOnvdczuQoY4zhyLzuNmvtc27ncZq19gFrbYy1No4j/76fWWv9fqvPWnsAyDDG9K67\nazyw1cVI3rAPGGWMaVH3fT4eP99RfZT3gOvrPr8eWNnQAwQ39At6m7W2xhhzO/ARR/bov2mt3eJy\nLKedCVwHpBhjNtbd96C19n0XM4kz7gAW1G3M7AKmupzHUdba74wx7wIbOLIaLRk/POrWGLMIOAeI\nNMZkAn8CngKWGGNu4shZg69s8HF1pK2ISGDwhykdERE5CSp8EZEAocIXEQkQKnwRkQChwhcRCRAq\nfBGRAKHCFxEJECp8EZEA8X/whubkKLv1dwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2576afdc160>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline  \n",
    "\n",
    "import math\n",
    "\n",
    "def f(x):\n",
    "    return x * math.log(x) - 16.0\n",
    "\n",
    "xvals = np.arange(0.01, 10, 0.01)        \n",
    "yvals = np.array([f(x) for x in xvals])\n",
    "plt.plot(xvals, yvals) \n",
    "plt.plot(xvals, 0*xvals)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To find $x$ for the equation, we need to compute the derivative of $f(x)$, i.e., $f'(x)$ first. \n",
    "\n",
    "$$f'(x) = (x \\cdot \\frac{1}{x} + 1 \\cdot \\ln(x)) + 0 = 1 + \\ln(x)$$ \n",
    "\n",
    "We implement it as `fprime(x)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fprime(x):\n",
    "    return 1.0 + math.log(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you need to implement Newton's method below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'''\n",
    "x_0: initial guess\n",
    "EPSILON: stop when abs(x - x_new) < EPSILON\n",
    "MAX_ITER: maximum number of iterations\n",
    "\n",
    "NOTE: you must use the default values of the above parameters, do not change them\n",
    "'''\n",
    "def find_root(f, fprime, x_0=1.0, EPSILON = 1E-7, MAX_ITER = 1000): # do not change the heading of the function\n",
    "    pass # **replace** this line with your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can test your implementation using the following code.\n",
    "\n",
    "Note that we will test your code using a different $f(x)$ (and its corresponding $f'(x)$). You need to perform similar tests by yourself. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i = 0:\t1.0 => 17.0\n",
      "i = 1:\t17.0 => 8.608965126131011\n",
      "i = 2:\t8.608965126131011 => 7.805421527761377\n",
      "i = 3:\t7.805421527761377 => 7.7927448262150705\n",
      "i = 4:\t7.7927448262150705 => 7.792741452820569\n",
      "i = 5:\t7.792741452820569 => 7.792741452820329\n",
      "7.792741452820329\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "x = find_root(f, fprime)\n",
    "print(x)\n",
    "print(f(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3: Enumerating Combinations\n",
    "\n",
    "You need to write a function, `comb(n, k)`, that returns a list consisting of all the combinations of $k$ elements out of a set $\\{1, 2, \\ldots, n\\}$. Your implementation should be using recursions instead of `for` loop (you may use *list comprehension* though).  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 5, 6],\n",
       " [2, 5, 6],\n",
       " [3, 5, 6],\n",
       " [4, 5, 6],\n",
       " [1, 4, 6],\n",
       " [2, 4, 6],\n",
       " [3, 4, 6],\n",
       " [1, 3, 6],\n",
       " [2, 3, 6],\n",
       " [1, 2, 6],\n",
       " [1, 4, 5],\n",
       " [2, 4, 5],\n",
       " [3, 4, 5],\n",
       " [1, 3, 5],\n",
       " [2, 3, 5],\n",
       " [1, 2, 5],\n",
       " [1, 3, 4],\n",
       " [2, 3, 4],\n",
       " [1, 2, 4],\n",
       " [1, 2, 3]]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "comb(6, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}