Python presentation

adoption.jpg

bear.jpg

gigawats.jpg

jackie.jpg

much_wow.jpg

not_bad.jpg

pros_cons.jpg

python.jpg

recitation1.ipynb

recitation2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS1001.py\n",
    "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n",
    "# Recitation 2 - 7-11.3.2013\n",
    "## Last update: 24.4.2013 - added XKCD comic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting input from the user\n",
    "You can get input from the user by calling the `input` function:\n",
    "\n",
    "```\n",
    "m = int(input(\"enter a positive integer to apply Collatz algorithm: \"))\n",
    "```\n",
    "\n",
    "Note that `input` returns a *string* and therefore you are responsible to convert it to the appopriate type."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Collatz Conjecture\n",
    "\n",
    "The [Collatz Conjecture](http://en.wikipedia.org/wiki/Collatz_conjecture) (also known as the *3n+1* conjecture) is the conjecture that the following process is finite for every natural number:\n",
    "> If the number $n$ is even divide it by two ($n/2$), if it is odd multiply it by 3 and add 1 ($3n+1$). Repeat this process untill you get the number 1.\n",
    "\n",
    "### Implementation\n",
    "We start with the \"Half Or Triple Plus One\" process:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1\n",
      "100 is OK\n"
     ]
    }
   ],
   "source": [
    "m = 100 # integer to apply the conjecture on\n",
    "\n",
    "n = m\n",
    "while n != 1:\n",
    "    print(n, end=\", \")\n",
    "    \n",
    "    if n % 2 == 0:\n",
    "        n = n // 2\n",
    "    else:\n",
    "        n = 3 * n + 1\n",
    "        \n",
    "print(1) # 1 was not printed\n",
    "print(m, \"is OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we add another loop that will run the conjecture check on a range of numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 is OK\n",
      "2 is OK\n",
      "3 is OK\n",
      "4 is OK\n",
      "5 is OK\n",
      "6 is OK\n",
      "7 is OK\n",
      "8 is OK\n",
      "9 is OK\n",
      "10 is OK\n"
     ]
    }
   ],
   "source": [
    "limit = 10\n",
    "m = 1\n",
    "while m <= limit:\n",
    "    n = m\n",
    "    \n",
    "    while n != 1:\n",
    "        if n % 2 == 0:\n",
    "            n = n // 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "            \n",
    "    print(m, \"is OK\")\n",
    "    m += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a loop goes over a simple range it is easier to use the `range` function with a `for` loop - and more robust against bugs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111 109 107 105 103 101 99 "
     ]
    }
   ],
   "source": [
    "for m in range(111, 98, -2):\n",
    "    print(m, end=\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 is OK\n",
      "100 is OK\n",
      "101 is OK\n",
      "102 is OK\n",
      "103 is OK\n",
      "104 is OK\n",
      "105 is OK\n",
      "106 is OK\n",
      "107 is OK\n",
      "108 is OK\n",
      "109 is OK\n",
      "110 is OK\n"
     ]
    }
   ],
   "source": [
    "start, stop = 99, 110\n",
    "for m in range(start, stop + 1):\n",
    "    n = m\n",
    "    while n != 1:\n",
    "        if n % 2 == 0:\n",
    "            n = n // 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "            \n",
    "    print(m, \"is OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![XKCD](http://imgs.xkcd.com/comics/collatz_conjecture.png)](http://xkcd.com/710/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lists\n",
    "\n",
    "Lists are sequences of values. \n",
    "\n",
    "Lists can contain a mix of types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 5.14, 'hello', True, [5], <class 'range'>] <class 'list'>\n"
     ]
    }
   ],
   "source": [
    "mixed_list = [3, 5.14, \"hello\", True, [5], range]\n",
    "print(mixed_list, type(mixed_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists are indexable, starting at 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Negative indices are counted from the tail:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "range"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[-2] == mixed_list[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists can be sliced:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5.14, 'hello']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[1:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5.14, 'hello', True, [5], range]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14, 'hello', True]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[:-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[:1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list[7:8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-16-d8a75e7ae27c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mmixed_list\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m7\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "mixed_list[7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists can be concatenated:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14, 'hello', True, [5], range, 1, 2, 3]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list + [1, 2, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But this doesn't change the list, but creates a new list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14, 'hello', True, [5], range]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14, 'hello', True, [5], range, 1, 2, 3]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list = mixed_list + [1, 2, 3]\n",
    "mixed_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some functions can be used on lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 3, 2, 56]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = [10, 3, 2, 56]\n",
    "numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "71"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unsupported operand type(s) for +: 'int' and 'str'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-25-a479ce694266>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0msum\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'hello'\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m'world'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: unsupported operand type(s) for +: 'int' and 'str'"
     ]
    }
   ],
   "source": [
    "sum(['hello','world'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(['hi','hello'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 10, 56]\n",
      "[10, 3, 2, 56]\n",
      "None\n",
      "[2, 3, 10, 56]\n"
     ]
    }
   ],
   "source": [
    "print(sorted(numbers))\n",
    "print(numbers)\n",
    "print(numbers.sort())\n",
    "print(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists are iterable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5.14, 'hello', True, [5], range, 1, 2, 3]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixed_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello\n"
     ]
    }
   ],
   "source": [
    "for item in mixed_list:\n",
    "    if type(item) == str:\n",
    "        print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "hello\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(mixed_list)):\n",
    "    print(i)\n",
    "    if type(mixed_list[i]) == str:\n",
    "        print(mixed_list[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "i = 0 # important!\n",
    "while i < len(mixed_list) and type(mixed_list[i]) != int:\n",
    "    if type(mixed_list[i]) == str:\n",
    "        print(mixed_list[i])\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A list of numbers can be created using *list comprehension*.\n",
    "The syntax is:\n",
    "```\n",
    "[**statement** for **variable** in **iterable** if **condition**] \n",
    "```\n",
    "The `if **condition**` part is optional, the statement and the condition can use variable.\n",
    "\n",
    "Create a list of the squares of numbers between 1 and 10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x ** 2 for x in range(1, 11)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a list of the square roots of odd numbers between 1 and 20:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0,\n",
       " 1.7320508075688772,\n",
       " 2.23606797749979,\n",
       " 2.6457513110645907,\n",
       " 3.0,\n",
       " 3.3166247903554,\n",
       " 3.605551275463989,\n",
       " 3.872983346207417,\n",
       " 4.123105625617661,\n",
       " 4.358898943540674]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x ** 0.5 for x in range(1, 21) if x % 2 == 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = []\n",
    "l += [1]\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grades problem\n",
    "\n",
    "Given a list of grades, count how many are above the average."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "grades = [33, 55,45,87,88,95,34,76,87,56,45,98,87,89,45,67,45,67,76,73,33,87,12,100,77,89,92]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15 grades are above the average 68.07407407407408\n"
     ]
    }
   ],
   "source": [
    "avg = sum(grades)/len(grades)\n",
    "above = 0\n",
    "for gr in grades:\n",
    "    if gr > avg:\n",
    "        above += 1\n",
    "        \n",
    "print(above, \"grades are above the average\", avg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using *list comprehension*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15 grades are above the average 68.07407407407408\n"
     ]
    }
   ],
   "source": [
    "avg = sum(grades)/len(grades)\n",
    "above = len([gr for gr in grades if gr > avg])\n",
    "        \n",
    "print(above, \"grades are above the average\", avg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you see the equivalence?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`\n",
    "for gr in grades:\n",
    "    if gr > avg:\n",
    "        above += 1\n",
    "`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`[gr for gr in grades if gr > avg]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions\n",
    "\n",
    "### Maximum and minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def max2(a,b):\n",
    "    if a >= b:\n",
    "        return a\n",
    "    else:\n",
    "        return b\n",
    "\n",
    "def min2(a,b):\n",
    "    if a <= b:\n",
    "        return a\n",
    "    else:\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "print(max2(5,10))\n",
    "print(min2(5,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def max3(a,b,c):\n",
    "    if a >= b and a >= c:\n",
    "        return a\n",
    "    elif b >= a and b >= c:\n",
    "        return b\n",
    "    else:\n",
    "        return c\n",
    "\n",
    "def max3v2(a,b,c):\n",
    "    max_ab = max2(a,b)\n",
    "    return max2(max_ab,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "print(max3(5,10,10))\n",
    "print(max3v2(5,10,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %timeit max3(100,45,67)\n",
    "# %timeit max3(45,67,100)\n",
    "# %timeit max3v2(100,45,67)\n",
    "# %timeit max3v2(45,67,100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Which should be faster, `max3` or `max3v2`?\n",
    "* How would you implement `max4`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Perfect numbers\n",
    "\n",
    "A perfect number is a number that is equal to the sum of its divisors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def divisors(n):\n",
    "    '''\n",
    "    divisors(integer) -> list of integers\n",
    "    Return the proper divisors of n (numbers less than n that divide evenly into n).\n",
    "    '''\n",
    "    return [div for div in range(1,n) if n % div == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function is_perfect in module __main__:\n",
      "\n",
      "is_perfect(n)\n",
      "    is_perfect(integer) -> bool\n",
      "    Return True iff n equals the sum of its divisors\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def is_perfect(n):\n",
    "    '''\n",
    "    is_perfect(integer) -> bool\n",
    "    Return True iff n equals the sum of its divisors\n",
    "    '''\n",
    "    if n == sum(divisors(n)):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "help(is_perfect)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Notes\n",
    "\n",
    "* Functions that return a boolean are named with `is_` as a prefix.\n",
    "* Use `'''` after the function definition to create function documentation\n",
    "* in `is_perfect` we can return the condition value instead of using the `if-else` clause:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_perfect(n):\n",
    "    '''\n",
    "    is_perfect(integer) -> bool\n",
    "    Return True iff n equals the sum of its divisors\n",
    "    '''\n",
    "    return n == sum(divisors(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "perfect numbers in range(1,1000)\n",
      "\n",
      "[6, 28, 496]\n"
     ]
    }
   ],
   "source": [
    "print(\"perfect numbers in range(1,1000)\\n\")\n",
    "print([n for n in range(1,1001) if is_perfect(n)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Complexity\n",
    "\n",
    "We can write another version of `divisors` that is more efficient by iterating only on numbers between 1 and $\\frac{n}{2}$, but this function is more complex and bugs are crawling in it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def divisors2(n):\n",
    "    divs = []\n",
    "    for m in range(2,round(n * 0.5)):#1 and n**0.5 will be handled separately. why?\n",
    "        if n % m == 0:\n",
    "            divs += [m, n // m]\n",
    "    divs += [1] # 1 surely divides n\n",
    "    return divs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[2, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "print(divisors(6))\n",
    "print(divisors2(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 883 µs per loop\n",
      "100 loops, best of 3: 436 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 100 divisors(10**4)\n",
    "%timeit -n 100 divisors2(10**4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fin\n",
    "This notebook is part of the [Extended introduction to computer science](http://tau-cs1001-py.wikidot.com/) course at Tel-Aviv University.\n",
    "\n",
    "The notebook was written using Python 3.2 and IPython 0.13.1.\n",
    "\n",
    "The code is available at <https://raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb>.\n",
    "\n",
    "The notebook can be viewed online at <http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb>.\n",
    "\n",
    "The notebooks is also available as a PDF at <https://github.com/yoavram/CS1001.py/blob/master/recitation2.pdf?raw=true>.\n",
    "\n",
    "This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}

thanks.jpg

try.jpg

wat.jpg

waterfall.jpg

Workshop.ipynb

watson.png

whoa.jpg

wow.jpeg

xkcd.png