distribute_hw3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Algorithms: Fibonacci\n",
    "\n",
    "Another form of recursion is tree recursion. Consider computing a fibonacci sequence, in which each number is the sum of the previous two, with the first two taken to be 0 and 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursive Fibonacci. \n",
    "\n",
    "\n",
    "We write Fibonacci recursively with the first two numbers as base cases.\n",
    "\n",
    "![](https://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-13.gif)\n",
    "\n",
    "(from SICP)\n",
    "\n",
    "Signature: `def fib_recursive(n)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "8\n",
      "144\n",
      "317811\n",
      "2178309\n"
     ]
    }
   ],
   "source": [
    "def fib_recursive(n):\n",
    "    if n == 1:\n",
    "        return 0\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    return fib_recursive(n-1) + fib_recursive(n-2)\n",
    "\n",
    "for i in [1, 2, 7, 13, 29, 33]:\n",
    "    print(fib_recursive(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1. \n",
    "\n",
    "What are the space and time complexities of this implementation? Hint: think aboutthe number of items in a binary tree and its depth."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Time complexities:**  \n",
    "$$T(n) = T(n-1) + T(n-2)$$\n",
    "using *mathematical induction*, we can easily get,  \n",
    "$$T(n) = \\frac{\\sqrt{5}}{5}[(\\frac{1+\\sqrt{5}}{2})^{n}-(\\frac{1-\\sqrt{5}}{2})^{n}] $$  \n",
    "So, the time complexities is $(\\Phi^{n})$, $\\Phi$ is the Golden Ratio($\\Phi\\approx1.618$).  \n",
    "Or, we can simpliy think the time complexities is $(2^{n})$\n",
    "\n",
    "**Space complexities:**  \n",
    "The recursion take n stacks, so the space complexity is ${O(n)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dynamic Programming and Iteration\n",
    "\n",
    "From Skiena\n",
    ">..**dynamic programming**, which typically removes one element from the problem, solves the smaller problem, and then uses the solution to this smaller problem to add back the element in the proper way. **Divide-and-conquer** instead splits the problem in (say) halves, solves each half, then stitches the pieces back together to form a full solution.\n",
    "\n",
    ">Dynamic programming is a technique for efficiently implementing a recursive algorithm by storing partial results. The trick is seeing whether the naive recursive algorithm computes the same subproblems over and over and over again. If so, storing the answer for each subproblems in a table to look up instead of recompute can lead to an efficient algorithm. Start with a recursive algorithm or definition. Only once we have a correct recursive algorithm do we worry about speeding it up by using a results matrix. Dynamic programming is generally the right method for optimization problems on combinatorial objects that have an inherent left to right order among components. Left-to-right objects includes: character strings, rooted trees, polygons, and integer sequences."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2.\n",
    "\n",
    "Here is an implementation of Fibonacci using dynamic programming: they key is to notice that the recurrence we used can be put into an iterative form and just stored in an ever increasing array. What is the space and time complexity here? What if you were somehow able to save the array outside of the function when u calculate `fib(M)` and subsequently had to calculate `fib(N)`, where $N>M$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib_iterative(n):\n",
    "    fibs=[]\n",
    "    fibs.append(0)\n",
    "    fibs.append(1)\n",
    "    for i in range(2, n):\n",
    "         fibs.append(fibs[i-1]+fibs[i-2])\n",
    "    return fibs[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "8\n",
      "144\n",
      "317811\n",
      "2178309\n"
     ]
    }
   ],
   "source": [
    "for i in [1, 2, 7,13,29,33]:\n",
    "    print(fib_iterative(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Time complexities:**  \n",
    "The time complexities is ${O(n)}$. Because tt's memorized search and each loop is ${O(1)}$.   \n",
    "\n",
    "**Space complexities:**  \n",
    "The space complexity is ${O(n)}$, because we keep a *n* long arry."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursive Fibonacci with cacheing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3. \n",
    "\n",
    "Use `cache` and `call_counter` as decorators on `fib_recursive` and print the fibonacci numbers for 7,13,29, 33. What order should these decorators be called to make sure `call_counter` gets the actual number of calls to `fib_recursive`?\n",
    "\n",
    "We've written the `cache` decorator for you. You have to write the `call_counter` decorator which takes the function as argument and using a `count_dictionary` whose keys are function names, counts the number of times the function is called."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cache(f):\n",
    "    \"\"\"a single argument function whose values may be cached\"\"\"\n",
    "    cache = {}\n",
    "    def memoized_func(x):\n",
    "        if x not in cache:\n",
    "            cache[x] = f(x)\n",
    "        return cache[x]\n",
    "    memoized_func.__name__ = f.__name__\n",
    "    return memoized_func"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def call_counter(count_dictionary):\n",
    "    def call_counter_decorator(func):\n",
    "        def inner(*args, **kwargs):\n",
    "            name = func.__name__\n",
    "            #your code here\n",
    "            if name in count_dictionary:\n",
    "                count_dictionary[name] += 1\n",
    "            else:\n",
    "                count_dictionary[name] = 1\n",
    "            return func(*args, **kwargs)\n",
    "        return inner\n",
    "    return call_counter_decorator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0 1\n",
      "2 1 2\n",
      "7 8 7\n",
      "13 144 13\n",
      "29 317811 29\n",
      "33 2178309 33\n"
     ]
    }
   ],
   "source": [
    "ccounter={}\n",
    "@cache\n",
    "@call_counter(ccounter)\n",
    "\n",
    "def fib_recursive(n):\n",
    "    if n == 1:\n",
    "        return 0\n",
    "    if n == 2:\n",
    "        return 1\n",
    "    return fib_recursive(n-1) + fib_recursive(n-2)\n",
    "\n",
    "for i in [1, 2, 7,13,29,33]:\n",
    "    print(i, fib_recursive(i), ccounter['fib_recursive'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The right order is:  \n",
    "@cache  \n",
    "@call_counter(ccounter)  \n",
    "\n",
    "We should call decorator *call_counter(ccounter)* first, and then *cache()*, so that decorator *call_counter(counter)* could caculate the actual number of loops of fib_recurisve and *cache()* could store it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4.\n",
    "\n",
    "What is the time and space complexity of the the memoized Fibonacci? HINT: assume evaluation happens left to right on sub-expressions, so that `fib_recursive(n-1)` side of the tree is evaluated first, and thus the tree is evaluated depth first, from left to right. What kind of pruning happens in the tree?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The time complexity** of the memorized Fibonacci is ${O(n)}$, because we only need caculate *fib_recursive(n-1)* once. In other words, every node in the recursion tree is visited only once.  \n",
    "**The space complexity** of the memorized Fibonacci is ${O(n)}$, because we also have to store n values.\n",
    "\n",
    "Actually, the memorized Fibonacci solution is just the same as Dynamic Programming solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q5.\n",
    "\n",
    "Do you really need to store the entire array in the dynamic programming implementation? Isnt it enough to have only saved the previous two Fibonacci numbers? Implement such an algorithm in `fib_iterative2(n)`. What is its space and time complexity? How is the time complexity different from that of the previous iterative attempt?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here\n",
    "def fib_iterative2(n):\n",
    "    fib_last_1 = 0\n",
    "    fib_last_2 = 1\n",
    "    if n == 1:\n",
    "        return fib_last_1\n",
    "    if n == 2:\n",
    "        return fib_last_2\n",
    "    for i in range(2, n):\n",
    "        fib_n = fib_last_1 + fib_last_2\n",
    "        fib_last_1, fib_last_2 = fib_last_2, fib_n\n",
    "    return fib_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "8\n",
      "144\n",
      "317811\n",
      "2178309\n"
     ]
    }
   ],
   "source": [
    "#your code here\n",
    "for i in [1, 2, 7,13,29,33]:\n",
    "    print(fib_iterative2(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't need to store the entire arry in the DP implementation, because we only need the former two values when we caculate each Fibonacci number.  \n",
    "**The time complexity** is still ${O(n)}$, because we also need to calculate n times.  \n",
    "**The space complexity** is a constant complexity ${O(1)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q6.\n",
    "\n",
    "Write an algorithm for insertion sort.\n",
    "\n",
    "![](https://camo.githubusercontent.com/8f6fedc10da579f13b22b949f6ad29255b6d721f/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f302f30662f496e73657274696f6e2d736f72742d6578616d706c652d33303070782e676966)\n",
    "\n",
    "(from wikipedia)\n",
    "\n",
    "The algorithm is also illustrated here: http://cs.armstrong.edu/liang/animation/web/InsertionSort.html and may be described thus:\n",
    "\n",
    "Insertion sort is a method for sorting that starts with a single element (thus forming a trivially sorted list) and then incrementally inserts the remaining elements so that the list stays sorted.\n",
    "\n",
    "Talk about the best, worst and average complexity of insertion sort. Use the A=[5,2,1,3,8,6,9] to show your code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#your code here\n",
    "def insert_sort(nums):\n",
    "    for i in range(1, len(nums)):\n",
    "        for j in range(i, 0, -1):\n",
    "            if nums[j] < nums[j - 1]:\n",
    "                nums[j], nums[j - 1] = nums[j - 1], nums[j];\n",
    "            else:\n",
    "                break\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*your answer here*\n",
    "insertion_sort([5,2,1,3,8,6,9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5, 6, 8, 9]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insert_sort([5,2,1,3,8,6,9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Best complexity:**\n",
    "The best time complexity is ${O(n)}$, when this array is already sorted. For each loop, *\"nums[j] < nums[j - 1]\"* will \"break;\", so we only need to iterate through the original array.\n",
    "\n",
    "**Worst complexity:**\n",
    "The worst time complexity is ${O(n^{2})}$, when this array in reverse order. Then, we need to compare and swap each number in the second loop *\"for j in range(i, 0, -1):\"*. So,  \n",
    "$$T(n) = 1 + 2 + ... + (n - 1) = \\frac{n(n-1)}{2}$$\n",
    "thus, the worst time complexity is ${O(n^{2})}$.\n",
    "\n",
    "**Average complexity:**  \n",
    "The average time complexity is ${O(n^{2})}$. "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}