recitation5.ipynb

{
 "metadata": {
  "name": "recitation5"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# CS1001.py\n",
      "\n",
      "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n",
      "\n",
      "# Recitation 5 - 11-15.4.2013\n",
      "\n",
      "## Last update: 15.4.2013"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# OOP - Object-Oriented Programming\n",
      "## `Point` class\n",
      "\n",
      "We will write a class for a point in a two dimensional Euclidian space ($\\mathbb{R}^2$).\n",
      "\n",
      "We start with the class definition (`def`) and the constructor (`__init__`) which defines the creation of a new class instance.\n",
      "\n",
      "Note:\n",
      "\n",
      "* The first argument to class methods (class functions) is always `self`, a reference to the instance.\n",
      "* The other arguments to `__init__` have a default values 0.\n",
      "* We *assert* that the `__init__` arguments are numbers."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    \n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = Point(1,2)\n",
      "print(\"point\", p.x, p.y)\n",
      "origin = Point()\n",
      "print(\"origin\", origin.x, origin.y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point 1.0 2.0\n",
        "origin 0.0 0.0\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Notice that when we send a `Point` to the console we get:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "<__main__.Point at 0x8519fd0>"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Which is not useful, so we will define how `Point` is represented in the console using `__repr__`. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    \n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "Point(1.0, 2.0)"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next up we define a method to add two points. Addition is by elements - $(x_1, y_1) + (x_2, y_2) = (x_1+x_2, y_1+y_2)$.\n",
      "\n",
      "We also allow to add an `int`, in which case we add the point to a another point with both coordinates equal to the argument value."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\"\n",
      "    \n",
      "    def add(self, other):\n",
      "        assert isinstance(other, (int, Point))\n",
      "        if isinstance(other, Point):\n",
      "            return Point(self.x + other.x , self.y + other.y)\n",
      "        else: # other is int, taken as (int, int)\n",
      "            return Point(self.x + other , self.y + other)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,1).add(Point(2,2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "Point(3.0, 3.0)"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,1).add(2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 53,
       "text": [
        "Point(3.0, 3.0)"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A nicer way to do it is to *overload* the addition operator + by defining the addition method name to a name Python reserves for addition - `__add__` (those are double underscores):"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\"\n",
      "    \n",
      "    def __add__(self, other):\n",
      "        assert isinstance(other, (int, Point))\n",
      "        if isinstance(other, Point):\n",
      "            return Point(self.x + other.x , self.y + other.y)\n",
      "        else: # other is int, taken as (int, int)\n",
      "            return Point(self.x + other , self.y + other)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,1) + Point(2,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 55,
       "text": [
        "Point(3.0, 3.0)"
       ]
      }
     ],
     "prompt_number": 55
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,1) + 2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 56,
       "text": [
        "Point(3.0, 3.0)"
       ]
      }
     ],
     "prompt_number": 56
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We want to be a able to compare `Point`s:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,2) == Point(2,1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,2) == Point(1,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = Point()\n",
      "p == p"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,2) > Point(2,1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "TypeError",
       "evalue": "unorderable types: Point() < Point()",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-11-5ba2a5d37eb0>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mPoint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m<\u001b[0m \u001b[0mPoint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
        "\u001b[1;31mTypeError\u001b[0m: unorderable types: Point() < Point()"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So `==` checks by identity and `>` is not defined. Let us overload both these operators:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\"\n",
      "    def __add__(self, other):\n",
      "        assert isinstance(other, (int, Point))\n",
      "        if isinstance(other, Point):\n",
      "            return Point(self.x + other.x , self.y + other.y)\n",
      "        else: # other is int, taken as (int, int)\n",
      "            return Point(self.x + other , self.y + other)\n",
      "    \n",
      "    def __eq__(self, other):\n",
      "        return (self.x, self.y) == (other.x, other.y)\n",
      "    \n",
      "    def __gt__(self, other):\n",
      "        return (self.x > other.x and self.y > other.y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "First we check if two points are equal:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,0) == Point(1,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,0) == Point(1,0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Then if one is *strictly* smaller than the other:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(1,0) > Point(1,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point(5,6) > Point(1,2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 22,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The addition operator + returns a **new instance**. \n",
      "\n",
      "Next we will write a method that instead of returning a new instance, changes the current instance:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\"\n",
      "    def __eq__(self, other):\n",
      "        return (self.x, self.y) == (other.x, other.y)\n",
      "    def __gt__(self, other):\n",
      "        return (self.x > other.x and self.y > other.y)\n",
      "    def __add__(self, other):\n",
      "        assert isinstance(other, (int, Point))\n",
      "        if isinstance(other, Point):\n",
      "            return Point(self.x + other.x , self.y + other.y)\n",
      "        else: # other is int, taken as (int, int)\n",
      "            return Point(self.x + other , self.y + other)\n",
      "    \n",
      "    def increment(self, other): \n",
      "        '''this method changes self (add \"inplace\")'''\n",
      "        assert isinstance(other,Point)\n",
      "        self.x += other.x\n",
      "        self.y += other.y"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = Point(6.5, 7)\n",
      "p + Point(1,2)\n",
      "print(p)\n",
      "p.increment(Point(1,2))\n",
      "print(p)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Point(6.5, 7.0)\n",
        "Point(7.5, 9.0)\n"
       ]
      }
     ],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We now write a method that given many points, checks if the current point is more extreme than the other points.\n",
      "\n",
      "Note that the argument `*points` means that more than one argument may be given."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Point():\n",
      "    \"\"\"Holds on a point (x,y) in the plane\"\"\"\n",
      "    def __init__(self, x=0, y=0):\n",
      "        assert isinstance(x, (int, float)) and isinstance(y, (int, float))\n",
      "        self.x = float(x)\n",
      "        self.y = float(y)\n",
      "    def __repr__(self):\n",
      "        return \"Point(\" + str(self.x) + \", \" + str(self.y) + \")\"\n",
      "    def __eq__(self, other):\n",
      "        return (self.x, self.y) == (other.x, other.y)\n",
      "    def __lt__(self, other):\n",
      "        return (self.x < other.x and self.y < other.y)\n",
      "    def __add__(self, other):\n",
      "        assert isinstance(other, (int, Point))\n",
      "        if isinstance(other, Point):\n",
      "            return Point(self.x + other.x , self.y + other.y)\n",
      "        else: # other is int, taken as (int, int)\n",
      "            return Point(self.x + other , self.y + other)\n",
      "    def increment(self, other): \n",
      "        '''this method changes self (add \"inplace\")'''\n",
      "        assert isinstance(other,Point)\n",
      "        self.x += other.x\n",
      "        self.y += other.y\n",
      "    \n",
      "    def is_extreme(self, *points):\n",
      "        for point in points:\n",
      "            if not self > point:\n",
      "                return False\n",
      "        return True"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = Point(5, 6)\n",
      "p.is_extreme(Point(1,1))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p.is_extreme(Point(1,1), Point(2,5), Point(6,2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 47,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can also use the method via the class instead of the instance, and give the instance of interest (the one that we want to know if it is the extreme) as the first argument `self`. Much like this, we can either do `'hi'.upper()` or `str.upper('hi')`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Point.is_extreme(Point(7,8), Point(1,1), Point(4,5), Point(2,3))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 49,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## `Rectangle` class\n",
      "\n",
      "We will implement two classes for rectangles, and compare the two implementations.\n",
      "\n",
      "### First implementation - two points\n",
      "\n",
      "The first implementation defines a rectangle by its lower left and upper right vertices."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Rectangle1():\n",
      "    \"\"\"\n",
      "    Holds a parallel-axes rectangle by storing two points\n",
      "    lower left vertex - llv\n",
      "    upper right vertex - urv\n",
      "    \"\"\"\n",
      "    def __init__(self, lower_left_vertex, upper_right_vertex):\n",
      "        assert isinstance(lower_left_vertex, Point)\n",
      "        assert isinstance(upper_right_vertex, Point)\n",
      "        assert lower_left_vertex < upper_right_vertex \n",
      "        self.llv = lower_left_vertex\n",
      "        self.urv = upper_right_vertex\n",
      "        \n",
      "    def __repr__(self):\n",
      "        representation = \"Rectangle with lower left {0} and upper right {1}\"\n",
      "        return representation.format(self.llv, self.urv)\n",
      "\n",
      "    def dimensions(self):\n",
      "        height = self.urv.y - self.llv.y\n",
      "        width = self.urv.x - self.llv.x\n",
      "        return height, width\n",
      "    \n",
      "    def area(self):\n",
      "        height, width = self.dimensions()\n",
      "        area = height * width\n",
      "        return area\n",
      "    \n",
      "    def transpose(self):\n",
      "        \"\"\"\n",
      "        Reflection with regard to the line passing through lower left vertex with angle 315 (-45) degrees\n",
      "        \"\"\"\n",
      "        height, width = self.dimensions()\n",
      "        self.urv = self.llv\n",
      "        self.llv = Point(self.urv.x - height, self.urv.y - width)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 71
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rec = Rectangle1(Point(), Point(2,1))\n",
      "print(rec)\n",
      "print(\"Area:\", rec.area())\n",
      "print(\"Dimensions:\", rec.dimensions())\n",
      "rec.transpose()\n",
      "print(\"Transposed:\", rec)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Rectangle with lower left Point(0.0, 0.0) and upper right Point(2.0, 1.0)\n",
        "Area: 2.0\n",
        "Dimensions: (1.0, 2.0)\n",
        "Transposed: Rectangle with lower left Point(-1.0, -2.0) and upper right Point(0.0, 0.0)\n"
       ]
      }
     ],
     "prompt_number": 66
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Second implementation - point and dimensions\n",
      "\n",
      "The second implementation defines a rectangle by the lower left point, the height and the width.\n",
      "\n",
      "We define the exact same methods as in `Rectangle1`, with the same input and output, but  different inner representation / implementation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Rectangle2():\n",
      "    \"\"\"\n",
      "    Holds a parallel-axes rectangle by storing lower left point, height and width\n",
      "    \"\"\"\n",
      "    def __init__(self, point, height, width):\n",
      "        assert isinstance(point, Point)\n",
      "        assert isinstance(height, (int,float))\n",
      "        assert isinstance(width, (int,float))\n",
      "        assert height > 0\n",
      "        assert width > 0        \n",
      "        self.point = point\n",
      "        self.height = float(height)\n",
      "        self.width = float(width)\n",
      "        \n",
      "    def __repr__(self):\n",
      "        representation = \"Rectangle with lower left {0} and upper right {1}\"\n",
      "        return representation.format(self.point, Point(self.point.x + self.width, self.point.y + self.height))\n",
      "    \n",
      "    def dimensions(self):\n",
      "        return self.height, self.width\n",
      "\n",
      "    def area(self):\n",
      "        area = self.height * self.width\n",
      "        return area\n",
      "\n",
      "    def transpose(self):\n",
      "        self.point = Point(self.point.x - self.height , self.point.y - self.width)\n",
      "        self.height, self.width = self.width, self.height"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 76
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rec = Rectangle2(Point(), 1, 2)\n",
      "print(rec)\n",
      "print(\"Area:\", rec.area())\n",
      "print(\"Dimensions:\", rec.dimensions())\n",
      "rec.transpose()\n",
      "print(\"Transposed:\", rec)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Rectangle with lower left Point(0.0, 0.0) and upper right Point(2.0, 1.0)\n",
        "Area: 2.0\n",
        "Dimensions: (1.0, 2.0)\n",
        "Transposed: Rectangle with lower left Point(-1.0, -2.0) and upper right Point(0.0, 0.0)\n"
       ]
      }
     ],
     "prompt_number": 77
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Recursion\n",
      "\n",
      "We will see two recusive functions that calculate the maximum value in a list.\n",
      "\n",
      "In the first function the recursive step removes the first element in the list.\n",
      "\n",
      "In the second function, the recursive step breaks the list into two lists:\n",
      "\n",
      "Try to count the number of function calls each function requires and the amount of memory used."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "View here or directly at <a href=\"http://pythontutor.com/visualize.html#code=def+max1(collection)%3A%0A++++if+len(collection)+%3D%3D+1%3A%0A++++++++return+collection%5B0%5D%0A++++return+max(collection%5B0%5D,+max1(collection%5B1%3A%5D))%0A%0Amax1(%5B1,2,5,4%5D)&mode=display&cumulative=true&heapPrimitives=false&drawParentPointers=false&textReferences=false&py=3&curInstr=0)\">Python Tutor</a>\n",
      "\n",
      "<iframe width=\"100%\" height=\"600\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+max1(collection)%3A%0A++++if+len(collection)+%3D%3D+1%3A%0A++++++++return+collection%5B0%5D%0A++++return+max(collection%5B0%5D,+max1(collection%5B1%3A%5D))%0A%0Amax1(%5B1,2,5,4%5D)&cumulative=true&heapPrimitives=false&drawParentPointers=false&textReferences=false&py=3&curInstr=0\"> </iframe>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The number of function calls is $O(n)$ but the amount of memory used is $n + n - 1 + n - 2 + ... + 1 = \\sum_{k=1}^{n}{k} = O(n^2)$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "View here or at <a href=\"http://pythontutor.com/visualize.html#code=def+max2(collection)%3A%0A++++if+len(collection)+%3C%3D+2%3A%0A++++++++return+max(collection)%0A++++middle+%3D+len(collection)+//+2%0A++++left+%3D+max2(collection%5B%3Amiddle%5D)%0A++++right+%3D+max2(collection%5Bmiddle%3A%5D)%0A++++return+max(left,+right)%0A%0Amax2(%5B1,2,5,4%5D)&mode=display&cumulative=true&heapPrimitives=false&drawParentPointers=false&textReferences=false&py=3&curInstr=0\">Python Tutor</a>\n",
      "\n",
      "<iframe width=\"100%\" height=\"500\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=def+max2(collection)%3A%0A++++if+len(collection)+%3C%3D+2%3A%0A++++++++return+max(collection)%0A++++middle+%3D+len(collection)+//+2%0A++++left+%3D+max2(collection%5B%3Amiddle%5D)%0A++++right+%3D+max2(collection%5Bmiddle%3A%5D)%0A++++return+max(left,+right)%0A%0Amax2(%5B1,2,5,4%5D)&cumulative=true&heapPrimitives=false&drawParentPointers=false&textReferences=false&py=3&curInstr=0\"> </iframe>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The number of function calls is again $O(n)$ but here the amount of memory used *simultaneously* is only $n + \\frac{n}{2} + \\frac{n}{4} + ... + 1 = n\\sum_{k=0}^{n}{\\frac{1}{2^n}} = 2n = O(n)$."
     ]
    },
    {
     "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/recitation5.ipynb>.\n",
      "\n",
      "The notebook can be viewed online at <http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation5.ipynb>.\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": {}
  }
 ]
}