0.self-evaluation/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 your 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": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 9, 2, 2, 4, 6, 9, 3, 10, 7]"
      ]
     },
     "execution_count": 1,
     "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": {
    "collapsed": true
   },
   "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": {
    "collapsed": true
   },
   "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": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEACAYAAACwB81wAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGkBJREFUeJzt3XmUVNXVxuHfRtQYCEYNYtSIEgGR0Y6icUhaARFwAEfk\nS9RINFmgcUxEESFmcFiamCgaNaioOMQhChigIVAqKDLPgkgDYgygDAKK2HTv749TSAcbmu4ablXd\n91mrFlXVXXW3Jby9+9xzzzF3R0RECl+dqAsQEZHsUOCLiMSEAl9EJCYU+CIiMaHAFxGJCQW+iEhM\npCXwzWyIma0yszmVntvPzErMbJGZjTGzfdNxLBERqZ10dfiPA513eK4fMM7dmwPjgZvTdCwREakF\nS9eFV2bWGBjh7m2SjxcCP3b3VWZ2EJBw96PScjAREamxTI7hH+juqwDcfSXQMIPHEhGRauikrYhI\nTNTN4HuvMrNGlYZ0Vlf1TWamxXxERGrB3a0m35/ODt+St22GA5cl718KvLqzF7q7bu4MHDgw8hpy\n5abPQp+FPotd32ojXdMynwHeApqZ2Qdm9jPgTqCTmS0COiYfi4hIRNIypOPuvXbypY7peH8REUmd\nTtrmkOLi4qhLyBn6LLbTZ7GdPovUpG0efq0LMPOoaxARyTdmhkd40lZERHKYAl9EJCYU+CIiMaHA\nFxGJCQW+iEhMKPBFRGJCgS8iEhMKfBGRmFDgi4jEhAJfRCQmFPgiIjGhwBcRiQkFvohITCjwRURi\nQoEvIhITmdzEXERE0swdHnigdq9V4IuI5IlPPoGf/QxWrard6zWkIyKSB8aPh3btoEULmDixdu+h\nDl9EJIeVlcHAgfDEE+F2+um1fy8FvohIjlq6FC6+GPbbD2bNggMPTO39NKQjIpKDnn0Wjj8eLroI\nXnst9bAHdfgiIjll0ya4+mqYNAlGj4aiovS9tzp8EZEcMWNGCHiz7ffTSYEvIhKxigr485+hc2f4\n7W/hscegfv30H0dDOiIiEVq9Gi67DNauhXfegSZNMncsdfgiIhEZOxaOOSbMr3/zzcyGPWShwzez\nZcCnQAVQ5u7tM31MEZFc9uWXcOut8Mwz8NRTcNpp2TluNoZ0KoBid1+XhWOJiOS0998Pc+sPOijM\nrf/Od7J37GwM6ViWjiMiktOefhp++EO45BIYPjy7YQ/Z6fAdGGNmDjzi7o9m4ZgiIjlj40bo2xem\nToVx46Bt22jqyEbnfaK7Hwt0Bfqa2clZOKaISE6YOjWcmN17b5g2Lbqwhyx0+O6+Mvnnx2b2T6A9\n8D9rvQ0aNOir+8XFxRQXF2e6LBGRjCovh3vugXvvDevXX3hhau+XSCRIJBIpvYe5e2pV7OrNzb4J\n1HH3TWZWDygBfuvuJZW+xzNZg4hItq1YEcbpy8vDLJzGjdN/DDPD3a0mr8n0kE4jYKKZzQQmAyMq\nh72ISKF58UX4wQ+gUyeYMCEzYV9bGe3wd6sAdfgiUgA2boRrrgkXUA0bBu0zfMVRLnb4IiIFb8qU\n7YuezZyZ+bCvLa2lIyJSS+XlcOed8Ne/wuDBcP75UVe0awp8EZFaWL4cfvpTqFsXpk+HQw+NuqLq\naUhHRKSGnnsOjjsOzjwzLICWD2EP6vBFRHbbhg1w1VVhGeNRo8JsnHyiDl9EZDe8/XZYxvib3wy7\nUeVb2IM6fBGRXdq6Ff7wB3joIfjb36B796grqj0FvojITixdCj/5CdSrF7r6gw+OuqLUaEhHRKQK\nTz8d5tOfdx6MHp3/YQ/q8EVE/sf69WEp45kzwwycdu2irih91OGLiCRNmBCWL95vv7CUcSGFPajD\nFxFhyxbo3x+efRaGDIEzzoi6osxQ4ItIrM2ZE07MNm0Ks2dnf9vBbNKQjojEUkVF2KCkQwe44Yaw\nrHEhhz2owxeRGFq+HC67LMyxnzIFjjgi6oqyQx2+iMSGe5huedxxYZw+kYhP2IM6fBGJibVr4Ze/\nhPnzYcyYsLF43KjDF5GCN3ZsmG55yCFhKeM4hj2owxeRArZ5M/TrBy+/DI8/Dh07Rl1RtNThi0hB\n2rai5apVYbpl3MMeFPgiUmDKy+GOO8JJ2VtvDZuV7L9/1FXlBg3piEjBKC2FSy6BvfYKSyMcdljU\nFeUWdfgikvfc4bHH4Pjj4dxzYdw4hX1V1OGLSF5buRKuuAJWrIDx46F166gryl3q8EUkb73wQljR\nsm3bcMWswn7X1OGLSN5ZuzZsJj59Orz6ahjKkeqpwxeRvDJqFLRpAw0bhk1KFPa7Tx2+iOSFjRvD\nqpYlJfDUU3DqqVFXlH/U4YtIznvjjTBOX14e1q9X2NdOxgPfzM4ws4Vm9p6Z3ZTp44lI4fjii9DV\n9+wJf/lL2I2qQYOoq8pfGQ18M6sDPAB0BloCF5vZUZk8pogUhmnToKgoTLecMwfOOivqivJfpjv8\n9sBid1/u7mXAc8A5GT6miOSxsjIYNAi6doUBA+D55wt/J6psyfRJ20OAFZUef0j4ISAi8jULFoSl\nERo2hFmz4OCDo66osGQ68K2K5/xr31Rc6dsOB2K0A42I7CA5dHPIo9GWkXOWAstSe4tMB/6HQOUV\nLQ4FPtrxmzzxtZ8BIhITpaVhf1mAJ56AJk2irCZ/mFXVT+9apsfwpwJHmlljM9sL6AkMz/AxRSQP\nVFTAAw9A+/ZwzjkwYYLCPtMy2uG7e7mZXQWUEH64DHH3dzN5TBHJfaWl0Lt3mHY5aRI0bx51RfGQ\n8Xn47j7a3Zu7e1N3vzPTxxOR3FVRAYMHh66+WzeYOFFhn01aWkFEsmLp0tDVf/55CPqjdEVO1mlp\nBRHJqIoKeOih0NV36RKGcBT20VCHLyIZs2xZ6Oo/+yysh9OiRdQVxZs6fBFJO3f429/guOOgc+cw\nhKOwj546fBFJq+XLQ1e/cSO8/jocfXTUFck26vBFJC3c4eGH4dhjoWPHMFavsM8t6vBFJGUffAA/\n/zmsWweJBLRsGXVFUhV1+CJSa+7w6KPwgx+ETUneflthn8vU4YtIrSxbBldeGTYUnzABWrWKuiKp\njjp8EamRigq4//4wA6dDB5g8WWGfL9Thi8huW7QojNW7a1mEfKQOX0SqtXUr3HUXnHwyXHRRuIhK\nYZ9/1OGLyC7Nng2XXw777w9Tp8Lhh0ddkdSWOnwRqdKWLXDbbdCpE/TtCyUlCvt8pw5fRL7mnXdC\nV9+0qfaWLSQKfBH5yuefw4AB8MwzcN99cOGFUIud9CRHaUhHRICw7k3btrByJcydG07OKuwLizp8\nkZjbsAFuuglGjoQHH4Szzoq6IskUdfgiMTZqFLRuHaZdzp2rsC906vBFYmj1arjuurD2zWOPhStm\npfCpwxeJEXcYOjR09QcfHLp6hX18qMMXiYklS+CXv4Q1a8JQTlFR1BVJtqnDFylwW7fC3XfD8ceH\n7QanTFHYx5U6fJECNn16WOysYcMQ9E2aRF2RREkdvkgB+uwzuOEG6NYNrr8exoxR2IsCX6TglJSE\nk7KrV4eTsj/9qS6gkkBDOiIF4uOPQzc/aRI89FAYrxepTB2+SJ5zh6eeCl19o0ahq1fYS1Uy1uGb\n2UDgCmB18qlb3H10po4nEkelpWGq5SefwGuvhc3ERXYm0x3+n9y9KHlT2IukyZdfwh13QPv20LFj\nmIGjsJfqZHoMX6eKRNLszTdDV3/EETBtmjYlkd2X6Q6/r5nNMrO/m9m+GT6WSEFbswZ694ZeveD2\n22HECIW91ExKHb6ZjQUaVX4KcKA/8CBwu7u7mf0e+BPQu6r3GTRo0Ff3i4uLKS4uTqUskYLiDk8+\nGZYwvugimD8fGjSIuirJtkQiQSKRSOk9zN3TU82uDmLWGBjh7m2q+JpnowaRfLRwYRi+2bQJHn5Y\n4/SynZnh7jUaNs/YkI6ZHVTp4bnAvEwdS6TQbN4ctho85RQ477ywx6zCXlKVyZO2d5tZO6ACWAb8\nIoPHEikYY8dCnz7Qrl3YQPyQQ6KuSApFVoZ0dlmAhnREgLCX7PXXh01JBg+Grl2jrkhyWU4N6YjI\n7qmoCEshtG4NjRuHk7IKe8kEraUjEqEZM8LwTd26MGECtGoVdUVSyNThi0Rg3Tq46qrQyV9xBbzx\nhsJeMk+BL5JFFRVhT9mjj4bycliwIFxMVUf/EiULNKQjkiVz5oThmy1bYPhwOO64qCuSuFFfIZJh\nn34K114LnTrBJZfA5MkKe4mGAl8kQ9xh2DBo0SJsOTh/Plx5JeyxR9SVSVxpSEckA+bNg759w5II\nL78MJ5wQdUUi6vBF0mrjRrjxRjjttLDQ2ZQpCnvJHQp8kTRwh+efD8M3a9aEDr9PHw3fSG7RkI5I\niubNg2uuCdsMPv88nHRS1BWJVE0dvkgtrVsHv/pVGL7p0QOmT1fYS25T4IvUUHk5PPIIHHUUlJWF\ni6euuiosjyCSy/RXVKQGJk2Cq6+GevVg9Gg45pioKxLZfQp8kd3wn//Ab34T1ry5+27o2ROsRgvT\nikRPQzoiu/DFF/DHP0LbtnDEEWHLwYsvVthLflKHL1IFdxgxAq67Dtq0CfPpmzSJuiqR1CjwRXaw\ncGFY+2b58rAxyemnR12RSHpoSEckaf16uOGGsHF4585hdUuFvRQSBb7E3tatYQ/Z5s1hw4ZwIdV1\n18Gee0ZdmUh6aUhHYm3UqNDVf/e7UFISTs6KFCoFvsTS/Pkh6EtL4Z574KyzNPNGCp+GdCRWPv44\nLGpWXAxnnBGGb84+W2Ev8aDAl1jYsgXuvTfsJVu37vaZOHvtFXVlItmjIR0paO7wyivw61+HtW/e\nfDP8KRJHCnwpWDNnhtk2a9aE+fSdOkVdkUi0NKQjBeeDD+DSS6FLl7AMwsyZCnsRUOBLAVm/Hm66\nKaxgedhh8N578ItfaNlikW1SCnwzO9/M5plZuZkV7fC1m81ssZm9a2a6XlEyZssWuO8+aNYM1q4N\nV8j+7nfQoEHUlYnkllR7n7lAD+Dhyk+aWQvgQqAFcCgwzsyauruneDyRr1RUwD/+AbfcEmbfjB8P\nrVpFXZVI7kop8N19EYDZ12YxnwM85+5bgWVmthhoD7yTyvFEtkkkwswbdxgyBE49NeqKRHJfpkY3\nDwHervT4P8nnRFIyf34Yp1+wIKxTf+GFUEdnokR2S7WBb2ZjgUaVnwIc6O/uI3b2siqe2+lwzqBB\ng766X1xcTHFxcXVlScx89BHcdhsMHw433wwvvQR77x11VSLZk0gkSCQSKb2HpWNY3cwmADe4+4zk\n436Au/tdycejgYHu/rUhHTPT0L7s1Lp1cNddYdPwK66Afv1gv/2irkokemaGu9doUZB0/jJc+cDD\ngZ5mtpeZHQEcCUxJ47GkwH32WRiyadYsXDg1e3YIfoW9SO2lOi2zu5mtAE4ARprZKAB3XwD8A1gA\n/AvoozZedseXX8IDD8CRR4aQnzQJHn0Uvve9qCsTyX9pGdJJqQAN6QhQXg7DhsHAgWGtmz/8AYqK\nqn+dSFzVZkhH1yBKpNzh1Vfh1lth331h6FD40Y+irkqkMCnwJTLjx4eLpjZvhjvvhG7dtC69SCYp\n8CXrJk+GAQNg6VK4/Xbo2VNz6UWyQf/MJGumToWuXcPFUuefD+++C716KexFskX/1CTjZswIe8b2\n6AFnngmLF4dVLPfcM+rKROJFgS8ZM2sWdO8eQv700+H998N+srpCViQaCnxJu3nzwpBNly5hs/Al\nS+Dqq+Eb34i6MpF4U+BL2rz7bjgB27EjnHBC6OivvRb22SfqykQEFPiSBnPnhq0Ef/zjsNvU++/D\njTdCvXpRVyYilSnwpdamTQsnYjt1CkG/ZElYurh+/agrE5GqKPClxt56K4zPd+8eNh4pLYXf/Aa+\n9a2oKxORXdGFV7Jb3GHCBPj978MFU/36wSuvaMaNSD5R4MsuucOoUSHo16wJSyH06qU59CL5SIEv\nVSovh3/+E+64IyxZ3L8/XHAB7LFH1JWJSG0p8OV/bN4MTz4J99wDBxwQVrE85xwtfyBSCBT4AoSt\nBB98EO6/H449FoYMgVNO0eqVIoVEfVvMrVgB118P3/9+WONm3DgYOTKsSa+wFyksCvyYmjcPLr0U\n2rYNwT57NjzxBLRqFXVlIpIpCvwYcQ8dfLduYfmD5s3DxVL33qs9Y0XiQGP4MbB5c9gv9r77wuNr\nr4WXXtJiZiJxo8AvYB99FE7EPvIItG8fAr9DB43Ni8SVhnQK0PTp8JOfQMuWYfbNm2+GE7EdOyrs\nReJMgV8gysrghRfCVMoePcLJ2NJSGDw4jNWLiGhIJ899+CE8+mi4NW0aNho591yoq/+zIrIDdfh5\naNtsm/POgzZtwho3JSXw+uthg3CFvYhURdGQR9atg6FD4aGHwiqVffqEufNallhEdocCP8e5h/Xn\nhwyBl1+Grl3D/ZNO0glYEakZBX6OWrUqLGI2ZEgI/d69YdEiaNQo6spEJF+lNIZvZueb2TwzKzez\nokrPNzazz81sRvL2YOqlFr6tW8P0yR49wsyaBQvg73+HhQvDjlIKexFJRaod/lygB/BwFV97392L\nqnhedrBwYejmhw4NSxz07h3uN2gQdWUiUkhSCnx3XwRgVuVoskaYd2HVKnjuOXj66TC1slevMNOm\nZcuoKxORQpXJMfzDzWw6sAEY4O4TM3isvLBpU9gH9umnYfLksLHIH/8Ip52mnaREJPOqDXwzGwtU\nHj02wIH+7j5iJy/7CDjM3dclx/ZfMbOj3X1TyhXnmS1bQuf+/PNhfP7kk8OyxC+9BPXqRV2diMRJ\ntYHv7p1q+qbuXgasS96fYWZLgGbAjKq+f9CgQV/dLy4upri4uKaHzCmbN8OYMfDii/Daa+HiqAsu\ngD/9CQ48MOrqRCQfJRIJEolESu9h7p5yIWY2AbjR3acnH38HWOvuFWbWBHgdaO3u66t4raejhqh9\n/jmMGhVCftQoKCqC888PyxwcdFDU1YlIoTEz3L1G50pTCnwz6w7cD3wHWA/McvcuZnYucDtQBpQD\nt7n7v3byHnkb+CtWhA5+5Eh4442wBPEFF4RplerkRSSTsh746ZBPgV9RAVOmhIAfOTLMrunSBc48\nEzp3hm9/O+oKRSQuFPhp5h6WGP73v8NiZRMmhIufzjwz3E44QQuViUg0FPhpsGIFTJy4PeS3bAkb\nh3ToEG7a+1VEcoECv4bKymD27LA42VtvwaRJIeBPPHF7wLdooUXKRCT35G3gn322M2AAHHts5o6z\ncSPMmQOzZm2/LVgATZqElSdPPDHcvv99BbyI5L7aBH5OjECfckqY3bL33tCpUwjgli2hWbPw3O74\n8ktYuTJs3P3f/8KSJbB4Mbz3Xvhz7Vpo1QratYNjjoHLL4fWraF+/cz+t4mI5Iqc6PDdnYqK0HWX\nlMDUqTB/fgjt+vWhYUPYf/9wgnSPPcLtiy/CUgWffQaffgobNoQTqt/9brg1aRK2/Nt2+973tHyB\niBSOvB3S2VkNFRVhl6ePPw5/bt0K5eXhts8+YWmC+vXDqpIHHAB1tGGjiMREwQW+iIhUrTaBr55Y\nRCQmFPgiIjGhwBcRiQkFvohITCjwRURiQoEvIhITCnwRkZhQ4IuIxIQCX0QkJhT4IiIxocAXEYkJ\nBb6ISEwo8EVEYkKBLyISEwp8EZGYUOCLiMSEAl9EJCYU+CIiMaHAFxGJCQW+iEhMpBT4Zna3mb1r\nZrPM7CUza1Dpazeb2eLk109PvVQREUlFqh1+CdDS3dsBi4GbAczsaOBCoAXQBXjQzGq0u3ocJRKJ\nqEvIGfosttNnsZ0+i9SkFPjuPs7dK5IPJwOHJu+fDTzn7lvdfRnhh0H7VI4VB/rLvJ0+i+30WWyn\nzyI16RzDvxz4V/L+IcCKSl/7T/I5ERGJSN3qvsHMxgKNKj8FONDf3Uckv6c/UObuz1b6nh15irWK\niEgKzD21HDazS4ErgdPcfUvyuX6Au/tdycejgYHu/k4Vr9cPAhGRWnD3Gp0bTSnwzewM4F7gR+6+\nptLzRwPDgOMJQzljgaae6k8XERGptWqHdKpxP7AXMDY5CWeyu/dx9wVm9g9gAVAG9FHYi4hEK+Uh\nHRERyQ+RXmlrZmeY2UIze8/MboqyliiZ2aFmNt7MFpjZXDP7VdQ1Rc3M6pjZDDMbHnUtUTKzfc3s\nheQFjPPN7Pioa4qKmV1nZvPMbI6ZDTOzvaKuKVvMbIiZrTKzOZWe28/MSsxskZmNMbN9q3ufyALf\nzOoADwCdgZbAxWZ2VFT1RGwrcL27Hw38EOgb489im2sIQ4Jx9xfgX+7eAmgLvBtxPZEws4OBq4Ei\nd29DGI7uGW1VWfU4ISsr6weMc/fmwHiSF77uSpQdfntgsbsvd/cy4DngnAjriYy7r3T3Wcn7mwj/\nqGN73YKZHQp0Bf4edS1RMrNvAae4++MAyQsZN0RcVpT2AOqZWV3gm8BHEdeTNe4+EVi3w9PnAEOT\n94cC3at7nygDf8eLsz4kxiG3jZkdDrQDvjaFNUb+DPwaXbvRBPjEzB5PDm89Ymb7RF1UFNz9I8KM\nwA8IF3Kud/dx0VYVuQPdfRWEphFoWN0Logx8XZy1AzOrD7wIXJPs9GPHzLoBq5K/8RhV/z2Ji7pA\nETDY3YuAzwm/xseOmX2b0NE2Bg4G6ptZr2iryj9RBv6HwGGVHh9KjH5F21Hy19QXgafc/dWo64nQ\nScDZZlYKPAucamZPRlxTVD4EVrj7tOTjFwk/AOKoI1Dq7mvdvRx4GTgx4pqitsrMGgGY2UHA6upe\nEGXgTwWONLPGybPtPYE4z8h4DFjg7n+JupAoufst7n6Yuzch/J0Y7+6XRF1XFJK/rq8ws2bJpzoQ\n3xPZHwAnmNk3kivvdiB+J7B3/I13OHBZ8v6lQLWNYqoXXtWau5eb2VWEJZbrAEPcPW7/AwEws5OA\n/wPmmtlMwtDWLe4+OtrKJAf8ChhmZnsCpcDPIq4nEu4+xcxeBGYSLuacCTwSbVXZY2bPAMXAAWb2\nATAQuBN4wcwuJ/xAvKDa99GFVyIi8aAtDkVEYkKBLyISEwp8EZGYUOCLiMSEAl9EJCYU+CIiMaHA\nFxGJCQW+iEhM/D8dvbYBmW/u2gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10a9d1898>"
      ]
     },
     "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": {
    "collapsed": true
   },
   "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": {
    "collapsed": true
   },
   "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": {
    "collapsed": true
   },
   "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": {
    "collapsed": true
   },
   "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": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# use this cell\n"
   ]
  },
  {
   "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": 1
}