Skip to content

Instantly share code, notes, and snippets.

@yeesian

yeesian/cs1010s_review.ipynb

Created November 19, 2013 18:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yeesian/7549762 to your computer and use it in GitHub Desktop.
Save yeesian/7549762 to your computer and use it in GitHub Desktop.
Download ZIP
CS1010S (2nd half) Review
Display the source blob
Display the rendered blob
Raw
cs1010s_review.ipynb
{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"CS1010S Review\n",
"===\n",
"\n",
"We'll be reviewing the following chapters:\n",
"\n",
"1. Sequences \n",
" - data types (Tuples, Lists, etc)\n",
" - unary operations (search, sort)\n",
" - binary operations (add, concat, etc)\n",
"\n",
"2. Revisiting Higher Order Functions\n",
" - map/filter/enum/zip/etc\n",
"\n",
"3. Generic Operators\n",
" - dispatch on type\n",
" - data-directed programming\n",
" - message-passing\n",
"\n",
"4. Object-Oriented Programming\n",
" - Variable Scope\n",
" - Inheritance\n",
" - Polymorphism\n",
"\n",
"5. Memoization and Dynamic Programming"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Sequences\n",
"===\n",
"\n",
"A quick recap on `tuple` and `list` and `strings`:\n",
"\n",
"1) [**Initialization**] They are recognized in the same way, one using smooth brackets `()`, and the other using square brackets `[]`, and the last using quotations `''` or `\"\"`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a = (1,2,3,4,8,4,5,7) # a\n",
"b = list(a) # [1,2,3,4,8,4,5,7]"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"2) [**Indexing**] They are indexed the same way, using square brackets, and colons `:` for *slicing*.\n",
"\n",
"**Remarks:** Speaking of slicing, it is `O(n)` in time and space complexity (see reason [here](http://stackoverflow.com/questions/13203601/big-o-of-list-slicing))"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(a[4]) # => 8\n",
"print(b[4]) # => 8\n",
"print(a[3:]) # => (4,8,4,5,7)\n",
"print(b[3:]) # => [4,8,4,5,7]"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"8\n",
"8\n",
"(4, 8, 4, 5, 7)\n",
"[4, 8, 4, 5, 7]\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"3) [**Mutability**] However, a list is *mutable*, whereas a tuple is *immutable*. This means you can change an element within a list at will, but you cannot change any values within a tuple[1]\n",
"\n",
"**Remark:** But you can always create new tuples"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a[3] = 4"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"ename": "TypeError",
"evalue": "'tuple' object does not support item assignment",
"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-4-d840230b1ac3>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0ma\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m4\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
]
}
],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(a) # a => (1, 2, 3, 4, 8, 4, 5, 7)\n",
"b[3] = -1 # was originally [1, 2, 3, 4, 8, 4, 5, 7]\n",
"print(b) # but has become [1, 2, 3, *-1*, 8, 4, 5, 7]"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"4) [**Operations**] that you will commonly perform:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def list_operations(data_type):\n",
" print('---')\n",
" print(type(data_type))\n",
" print('---')\n",
" print(tuple(filter(lambda method: method[0] != '_' and method[:2] != '__', dir(data_type))))\n",
"\n",
"list_operations([]) # do you know what each one does? Do you know how to use them?\n",
"print('\\n')\n",
"list_operations((1,)) # observe how it supports fewer operations. Why?\n",
"print('\\n')\n",
"list_operations('') # you'll probably only remember (i) split, (ii) join, (iii) count, etc"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"---\n",
"<type 'list'>\n",
"---\n",
"('append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort')\n",
"\n",
"\n",
"---\n",
"<type 'tuple'>\n",
"---\n",
"('count', 'index')\n",
"\n",
"\n",
"---\n",
"<type 'str'>\n",
"---\n",
"('capitalize', 'center', 'count', 'decode', 'encode', 'endswith', 'expandtabs', 'find', 'format', 'index', 'isalnum', 'isalpha', 'isdigit', 'islower', 'isspace', 'istitle', 'isupper', 'join', 'ljust', 'lower', 'lstrip', 'partition', 'replace', 'rfind', 'rindex', 'rjust', 'rpartition', 'rsplit', 'rstrip', 'split', 'splitlines', 'startswith', 'strip', 'swapcase', 'title', 'translate', 'upper', 'zfill')\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Example usage:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print(type(a))\n",
"print(a)\n",
"print(a.count(4)) # counts the number of occurrences"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"<type 'tuple'>\n",
"(1, 2, 3, 4, 8, 4, 5, 7)\n",
"2\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a.count(4)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 7,
"text": [
"2"
]
}
],
"prompt_number": 7
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Revisiting Higher Order Functions\n",
"===\n",
"Sometimes (most times!) the list of operations supported by `list` and `str` will not be sufficient. Add the following functions to your \"toolkit\", you'll probably find them handy in most situations:"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" zip(a,b) => [(a0,b0), (a1,b1),...]\n",
" \n",
" map(f,a) => [f(a0), f(a1), ...]\n",
" \n",
" filter(f,a) => [ai | f(ai) is True]\n",
" \n",
" enumerate(a) => [(0,a0), (1,a1), ...]\n",
" \n",
" reduce(f,a) => f(a0,f(a1,,f(...,f(an-1,an))))\n",
" \n",
"These are functions that y'all are expected to be able to code up for yourselves, so if you don't already know how..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Self-defined functions\n",
"---\n",
"There'll be many instances in which the built-in functions mentioned earlier are insufficient for your needs, and you find yourself craving for more. Here's a handful (defined on sequences) that you might find helpful:\n",
"\n",
" Elementwise Operations\n",
" ---\n",
" add(s,t,u,...) => [s0+t0+u0+.., s1+t1+u1+.., ...]\n",
" mul(s,t,u,...) => [s0*t0*u0+.., s1*t1*u1+.., ...]\n",
" transpose(s) => [[s0],[s1],...] where s used to be [s0,s1,...]\n",
" \n",
" Generic Operations\n",
" ---\n",
" apply(f,s,t,u,...) => [f(s0,t0,u0,..), f(s1,t1,u1,..), ...] # Will map(f,zip(s,t,u,...) work here?\n",
"\n",
"where s,t,u are sequences (str, list, tuple, whatever). You'll probably find it useful if you need to perform operations on matrices/vectors"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Generic Operators\n",
"===\n",
"Now's probably a good time to talk about generic operators. Our motivation:\n",
"\n",
" work on data that could take on multiple forms (polymorphic data)\n",
"\n",
"Let's recap the following:\n",
"\n",
"- dispatch on type\n",
"- data-directed programming\n",
"- message-passing"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Dispatch on type\n",
"---\n",
"\n",
"- providing generic operators based on checking the data type and calling the appropriate function.\n",
"\n",
"Problems:\n",
"\n",
"- Generic operators need to know all the types available.\n",
"- Adding a new type means changing all operators to dispatch correctly.\n",
"- Does not resolve name conflict"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Data-Directed Programming\n",
"---\n",
"\n",
"- look at tag on data and find the correct operation from table\n",
"- Address problem of naming conflicts\n",
"- Allows easy extension: just add more entries to the table!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Recall Mission 12? Where we had a *mental model* of `_operation_table`:\n",
"\n",
"**tags** | ('generic') | ('complex','complex') | ('rational','rational') | ... |\n",
" ------------ | :-------------------: | :-------------------: | :---------------------: |\n",
"**operation** | | ||\n",
"'add' | |add(x,y)| add(x,y)|\n",
"'mul' | |mul(x,y)| mul(x,y)|\n",
"'negate' | negate(x) | ||\n",
"'is_zero' | is_zero(x)| ||\n",
"'is_equal' | |is_equal(x,y)| is_equal(x,y)|\n",
"... | | ||\n",
"\n",
"In creating generic operators, we were really selecting the appropriate lower-level function based on operation and type, as summarized in table above.\n",
"\n",
"So in `get(op, args)`: we first look up the appropriate `op` (operation) in the left side-bar, before we use the *tags* (in the top/header row) to find the appropriate function to use.\n",
"\n",
"What advantages does data-directed programming have over dispatching on type?\n",
"\n",
"- Consider the effect of adding a new type or new operation. Any code changes?\n",
"- Any name conflicts?\n",
"- Who should maintain table?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Message Passing\n",
"---\n",
"\n",
"- Previous strategies viewed `functions` as \u201cintelligent\u201d: they dispatch according to type of data.\n",
"- In message passing, it is the `data` that is \u201cintelligent\u201d: they know how to act on themselves."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import math\n",
"\n",
"def make_from_real_imag(x, y): # Example\n",
" def make_from_real_imag_helper(op):\n",
" if op == 'real_part':\n",
" return x\n",
" elif op == 'imag_part':\n",
" return y \n",
" elif op == 'magnitude':\n",
" return math.hypot(x, y)\n",
" elif op == 'angle':\n",
" return math.atan(y / x)\n",
" else:\n",
" raise Exception(\"Unknown op -- make_from_real_imag\" + op) \n",
" return make_from_real_imag_helper"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 46
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Message Passing (continued)\n",
"---\n",
"This idea of \u201cpassing a message\u201d to the data and letting the data do the job is the basis of *object-oriented programming*.\n",
"\n",
"- Functions are actions that objects perform\n",
"- Objects \u201ctalk\u201d to other objects by passing messages\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Object-Oriented Programming\n",
"---\n",
"Major Concepts:\n",
"\n",
"- Classes and instances\n",
"- Methods and message passing\n",
"- Inheritance\n",
"- Polymorphism"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Classes and instances\n",
"---\n",
"\n",
"- is_instance() vs type()"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Vehicle(object):\n",
" def __init__(self):\n",
" NotImplemented\n",
"\n",
"class Truck(Vehicle):\n",
" def __init__(self):\n",
" NotImplemented\n",
"\n",
"print(isinstance(Vehicle(), Vehicle)) # returns True\n",
"print(type(Vehicle()) == Vehicle) # returns True\n",
"print(isinstance(Truck(), Vehicle)) # returns True\n",
"print(type(Truck()) == Vehicle) # returns False\n",
"print(type(Truck()) == Truck) # returns True"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"True\n",
"True\n",
"True\n",
"False\n",
"True\n"
]
}
],
"prompt_number": 43
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- class vs instance"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a = Truck() # a is the instance, Truck() is the class"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 44
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Methods and Message-Passing\n",
"---\n",
"\n",
"Consider the following message-passing function:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def make_rect(x,y):\n",
" def helper(msg):\n",
" if msg == \"get_real\":\n",
" return x\n",
" elif msg == \"get_imag\":\n",
" return y\n",
" elif msg == \"angle\":\n",
" return math.atan(y/x)\n",
" elif msg == \"magnitude\":\n",
" return math.sqrt(x*x+y*y)\n",
" else:\n",
" raise Exception(\"Invalid method!\")\n",
" return helper"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 45
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"What would the corresponding class look like? (Can you see the correspondence?)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Rect:\n",
" def __init__(self,x,y):\n",
" self.x = x\n",
" self.y = y\n",
" def get_real():\n",
" return x\n",
" def get_imag():\n",
" return y\n",
" def angle():\n",
" return math.atan(y/x)\n",
" def magnitude():\n",
" return math.sqrt(x*x+y*y)"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Inheritance\n",
"---\n",
"We begin with the example:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class NamedObject(object):\n",
" def __init__ (self, name):\n",
" self.name = name\n",
"class MobileObject(NamedObject):\n",
" def __init__ (self, name, location):\n",
" self.name = name # do you notice repeated code?\n",
" self.location = location"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 48
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"- What happens if a new directive states that all names must be in lowercase? Do we have to manually change all the declarations in all the methods in the class hierarchy?\n",
" Doesn\u2019t sound very reusable right?\n",
"- We need a way to access the next higher class in the class hierarchy \u2013 the `super()` method"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class NamedObject(object): # NamedObject is a superclass of MobileObject\n",
" def __init__ (self, name):\n",
" self.name = name\n",
"class MobileObject(NamedObject): # MobileObject is-a subclass of NamedObject\n",
" def __init__ (self, name, location):\n",
" super().__init__(name) # compare with the previous implementation\n",
" self.location = location"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 49
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"**Remark 1:** If you haven't already done so, it's probably a good idea to look through Missions 14 to 16 (or get a friend to explain to you)\n",
"\n",
"**Remark 2:** Learn how to draw all of your inheritance diagrams (in the tutorials and missions) - what (i) attributes, and (ii) methods are"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Polymorphism\n",
"---\n",
"\n",
"- Object-oriented programming provides a convenient means for handling polymorphic functions (overloading)\n",
"- Functions that take different types of arguments: the same message can be sent to different types of objects and handled by different methods that perform the proper actions based on the object class (overriding)\n",
"\n",
"Let's illusrate this by example(s). Suppose we had the following classes:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Speaker(object):\n",
" def say(self, stuff):\n",
" print(stuff)\n",
" \n",
"ah_beng = Speaker()\n",
"ah_beng.say(\"Hello World\")\n",
"#ah_beng.dance()\n",
" \n",
"class Lecturer(Speaker):\n",
" def lecture(self, stuff):\n",
" self.say(stuff)\n",
" self.say(\"You should be taking notes\")\n",
" \n",
"seth = Lecturer()\n",
"seth.lecture(\"Java is easy\")\n",
"seth.say(\"You have a quiz today\")"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Hello World\n",
"Java is easy\n",
"You should be taking notes\n",
"You have a quiz today\n"
]
}
],
"prompt_number": 54
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"And now we have a few more classes `Arrogant Lectuer` and `Singer`, and the polymorphic class `SingingArrogantLecturer`:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class ArrogantLecturer(Lecturer):\n",
" def __init__(self, favourite_phrase):\n",
" print('here!')\n",
" self.favourite_phrase = favourite_phrase\n",
" def say(self, stuff):\n",
" super(Lecturer,self).say(stuff + self.favourite_phrase)\n",
"\n",
"ben = ArrogantLecturer(\" ... How cool is that?\")\n",
"ben.say(\"We'd have a re-midterm tomorrow\")\n",
"ben.lecture(\"Python is cool\")"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"here!\n",
"We'd have a re-midterm tomorrow ... How cool is that?\n",
"Python is cool ... How cool is that?\n",
"You should be taking notes ... How cool is that?\n"
]
}
],
"prompt_number": 68
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Singer(object):\n",
" #def say(self, stuff):\n",
" #print(\"tra-la-la -- \" + stuff)\n",
" def sing(self):\n",
" print(\"tra-la-la\")\n",
" \n",
"class SingingArrogantLecturer(ArrogantLecturer, Singer):\n",
" def __init__(self, favourite_phrase):\n",
" super().__init__(favourite_phrase)\n",
"\n",
"print(\"======\")\n",
"ben = SingingArrogantLecturer(\" ... How cool is that\")\n",
"ben.say(\"We'd have a re-midterm tommorrow\")\n",
"ben.lecture(\"Python is cool\")\n",
"ben.sing()"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Memoization\n",
"===\n",
"A *memoized* function\n",
"\n",
"- Maintains a table in which values of previous calls are stored \n",
"- Use the arguments that produced the values as keys\n",
"\n",
"When the memoized function is called\n",
"\n",
"- check table to see if the value exists:\n",
"- If so, return value.\n",
"- Otherwise, compute new value in the ordinary way and store this in the table.\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"memoize_table = {}\n",
"def memoize(f, name):\n",
" if name not in memoize_table:\n",
" memoize_table[name] = {}\n",
" table = memoize_table[name]\n",
" def helper(*args):\n",
" if args in table:\n",
" return table[args]\n",
" else:\n",
" result = f(*args)\n",
" table[args] = result\n",
" return result\n",
" return helper"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 73
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Design Pattern (Wrapper)\n",
"---\n",
"\n",
"- the method that we used to implement memoization is an important concept\n",
"- **Key Idea:** add an extra layer to introduce additional functionality and use the original function to do \u201cold work\u201d"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def choose(n,k):\n",
" if k > n:\n",
" return 0\n",
" elif k==0 or k==n:\n",
" return 1\n",
" else:\n",
" return choose(n-1,k) + choose(n-1,k-1)\n",
"\n",
"# versus\n",
"\n",
"def memo_choose(n,k):\n",
" def helper(n,k):\n",
" if k > n:\n",
" return 0\n",
" elif k==0 or k==n:\n",
" return 1\n",
" else:\n",
" return memo_choose(n-1,k) + memo_choose(n-1,k-1)\n",
" return memoize(helper, \"choose\")(n,k)"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 74
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Dynamic Programming version of choose\n",
"\n",
"def dp_choose(n,k):\n",
" # allocate space for table (all 1's)\n",
" row = [1]*(k+1)\n",
" table = []\n",
" for i in range(n+1):\n",
" table.append(row.copy())\n",
" \n",
" # fill first row with 0s\n",
" for j in range(1,k+1):\n",
" table[0][j] = 0\n",
" \n",
" # fill the rest\n",
" for i in range(1,n+1):\n",
" for j in range(1,k+1):\n",
" table[i][j] = table[i-1][j-1] + table[i-1][j]\n",
" \n",
" return table[n][k]"
],
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"prompt_number": 75
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment