{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>cs1001.py , Tel Aviv University, Fall 2017-2018</center></h1>\n",
    "<img src=\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\" width=50/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recitation 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We talked about binary numbers (with some theory) and base conversions. We have also impletemented an algorithm for base conversion, examined python's memory model and discussed in-place functions. Finally, we have (or will next week) analyzed the efficiency of using extend() vs. creating a new list with another element. \n",
    "\n",
    "#### Takeaways:\n",
    "\n",
    "<ol>\n",
    "<li>Make sure you understand binary numbers and base conversions (including the algorithms for convertion to and from a base b to decimal). It is a very useful tool in computer science</li>\n",
    "  <li>Elements of a global list can be changed from inside a function, if this list is given as a parameter, but the variable name (whether it be the list name or the int name etc.) itself cannot be made to point to a different object in the memory when passed as a function parameter.</li>\n",
    "  <li>Whenever you are not clear of what your program is doing in memory, use [Python tutor](http:\\\\www.pythontutor.com).</li>\n",
    "  <li>If you want to change a list, in-place functions such as append(), extend() and += are more efficient than creating a new list.</li>\n",
    "  <li>Try to analyze the number of operations your function does to see how will its runtime scale as a function of the input (we will elabore on this soon).</li>\n",
    "</ol>\n",
    "\n",
    "#### Python tutor guidelines:\n",
    "Before you click \"Visualize Execution\" button, you may want to use the following settings (can be adjusted via the drop boxes next to the textbox):\n",
    "<ol>\n",
    "  <li> Python 3.6</li>\n",
    "  <li>Show exited frames (Python)</li>\n",
    "  <li>Render all objects on the heap</li>\n",
    "  <li>Draw pointers as arrows [default]</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Code for printing several outputs in one cell (not part of the recitation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Base conversions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://i.ytimg.com/vi/XdZqk8BXPwg/maxresdefault.jpg\" width=400>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using Python functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1100'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'1100'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0x16'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1010"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "4112"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(12)\n",
    "bin(12)[2:]\n",
    "hex(22)\n",
    "int(\"1010\", 2) # first param is the representation in base b and the second is the base b itself\n",
    "int(\"0b1010\", 2)\n",
    "int(\"1010\")\n",
    "int(\"0x1010\", 16)\n",
    "# int(\"0x1010\", 2) # will throw an error: the prefix 0x does not go with base 2\n",
    "# int(1010, 2) # will throw an error: first param has to be a string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: given a natural number n (decimal) and a base b, return a string that represents n in base b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### First attempt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1010'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'10'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'10'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def convert_base(n,b):\n",
    "    assert 2 <= b <= 36\n",
    "    \n",
    "    result = \"\"\n",
    "    while n > 0:\n",
    "        digit = n % b\n",
    "        n = n//b\n",
    "        result = str(digit) + result\n",
    "    return result\n",
    "\n",
    "convert_base(10,2)\n",
    "convert_base(2,2)\n",
    "convert_base(10,16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Here are the issues:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'10'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "convert_base(0,2)\n",
    "convert_base(10,16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Second attempt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'16'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "'0'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def convert_base(n,b):\n",
    "    assert 2 <= b <= 36\n",
    "    \n",
    "    if n ==0: # fix for n = 0\n",
    "        return \"0\"\n",
    "    \n",
    "    alphabet = \"0123456789abcdefghijklmnopqrstuvwxyz\"\n",
    "    result = \"\"\n",
    "    while n > 0:\n",
    "        digit = n % b\n",
    "        n = n//b\n",
    "#         result = str(digit) + result\n",
    "        result = alphabet[digit] + result\n",
    "    return result\n",
    "\n",
    "convert_base(10,16)\n",
    "convert_base(22,16)\n",
    "convert_base(0,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Assersion Error (just for fun):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-8-d8fb5c70d025>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mconvert_base\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m37\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-7-3a734fbc7a54>\u001b[0m in \u001b[0;36mconvert_base\u001b[0;34m(n, b)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mconvert_base\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m     \u001b[1;32massert\u001b[0m \u001b[1;36m2\u001b[0m \u001b[1;33m<=\u001b[0m \u001b[0mb\u001b[0m \u001b[1;33m<=\u001b[0m \u001b[1;36m36\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mn\u001b[0m \u001b[1;33m==\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[1;34m\"0\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "convert_base(1, 37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Memory model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://www.blogcdn.com/www.joystiq.com/media/2012/09/balloons.jpg\" width=400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def change_int (n):\n",
    "    n = 999\n",
    "\n",
    "n = 10\n",
    "change_int(10)\n",
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 999]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add_to_lst(l):\n",
    "    l.append(999)\n",
    "\n",
    "lst = [1,2,3]\n",
    "add_to_lst(lst)\n",
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def change_lst(l):\n",
    "    l = [99,999,999]\n",
    "    \n",
    "lst = [1,2,3]\n",
    "change_lst(lst)\n",
    "lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Program we drew on the board:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#1 basics  #####################################################\n",
    "a = 1000                #1\n",
    "b = \"hello\"             #2\n",
    "a += len(b)             #3\n",
    "c = 2*b[:2]             #4\n",
    "if b!=c:                #5\n",
    "    c = b               #6\n",
    "del c                   #7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Programs examined with [Python tutor](http:\\\\www.pythontutor.com):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#2 lists  #####################################################\n",
    "a = 1000                #1\n",
    "d = [a,2]               #2\n",
    "d[1] = -1               #3\n",
    "a = 1003                #4\n",
    "for x in d:             #5a\n",
    "    x = 7               #5b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#3 funcs  #####################################################\n",
    "a = 1000                #1\n",
    "b = \"hello\"             #2\n",
    "def is_palindrom(a):    #3a\n",
    "    b = a[::-1]         #3b\n",
    "    return a==b         #3c\n",
    "is_pal = is_palindrom   #4\n",
    "x = is_pal(b)           #5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#4 lists+funcs  #####################################################\n",
    "a = 1000                #1\n",
    "d = [a,2]               #2\n",
    "def f(a,d):             #3a\n",
    "    a = 2000            #3b\n",
    "    d[0] = a            #3c\n",
    "    d = []              #3d\n",
    "    return d            #3e\n",
    "x = f(a,d)              #4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Extend(), append(), sort(), and sorted():"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11034760"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#5 – lists operators and methods #####################################################\n",
    "lst = [3,2,1]\n",
    "id(lst)\n",
    "lst = lst+[0]\n",
    "id(lst)\n",
    "lst.append(4) # in-place\n",
    "id(lst)\n",
    "lst.insert(1,5) # in-place\n",
    "id(lst)\n",
    "lst.extend([6,7]) # in-place\n",
    "id(lst)\n",
    "lst += [8] # in-place (invokes extend)\n",
    "id(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10849864"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "10850184"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst.sort()\n",
    "id(lst)\n",
    "lst2 = sorted(lst)\n",
    "id(lst2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis of creating a new list vs. extend():"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://suewhite.com.au/wp-content/uploads/2013/05/Timer-stopwatch-347x300.jpg\" width=400>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### (Will be completed next week for the 10-12 recitation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Measure with n = 10000:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time without extend:  0.19844970849135146\n",
      "time with extend:  0.0023136734905757628\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "n = 10000\n",
    "\n",
    "lst = []\n",
    "t0 = time.clock()\n",
    "for i in range(n):\n",
    "    lst = lst + [i]\n",
    "t1 = time.clock()\n",
    "\n",
    "print(\"time without extend: \", t1 - t0)\n",
    "\n",
    "lst2 = []\n",
    "t0 = time.clock()\n",
    "for i in range(n):\n",
    "    lst2 += [i]\n",
    "t1 = time.clock()\n",
    "\n",
    "print(\"time with extend: \", t1 - t0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Measure with n = 20000:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "time without extend:  0.8519414764165951\n",
      "time with extend:  0.004375096962302649\n"
     ]
    }
   ],
   "source": [
    "n = 20000\n",
    "\n",
    "lst = []\n",
    "t0 = time.clock()\n",
    "for i in range(n):\n",
    "    lst = lst + [i]\n",
    "t1 = time.clock()\n",
    "\n",
    "print(\"time without extend: \", t1 - t0)\n",
    "\n",
    "lst2 = []\n",
    "t0 = time.clock()\n",
    "for i in range(n):\n",
    "    lst2 += [i]\n",
    "t1 = time.clock()\n",
    "\n",
    "print(\"time with extend: \", t1 - t0)"
   ]
  }
 ],
 "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.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}