{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Fall 2017-2018

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recitation 7" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We discussed memoization and demonstrated it using our recursive implementations for binom, change, and cnt_paths. \n", "We have additionally solved an exam question about Catalan numbers which involved recursion, memoization, and complexity. \n", "Finally, we gave an intro to analysis of prime numbers and primality testing. We will continue this subject in the next recitation.\n", "\n", "\n", "#### Takeaways:\n", "- Memoization is mainly technical. Remember the main steps of defining an envelope function, deciding what keys you use to describe the input, \n", "and finally changing your recursive implementation so that it we rely and update the dictionary. \n", "- The keys of the dictionary should be chosen to represent the current input to the function in a one-to-one fashion.\n", "- When analyzing the time complexity of a recursive function with memoization, consider the recursion tree and remember that a node that has already been computed will not have a subtree." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recursion & Memoization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Binom" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The number of sets of size $k$ selected from a set of $n$ elements (with no repetitions)\n", "Recursive formula (Pascal):\n", "$\\binom{n}{k} = \\binom{n-1}{k} + \\binom{n-1}{k-1}$\n", "where the stopping criterion is $\\binom{n}{0} = \\binom{n}{n} = 1$\n", "\n", "The time complexity of binom is exponential in $n$ (worst case behaviour is when $k=\\frac{n}{2}$)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From previous class:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def binom(n,k):\n", " if n < 0 or k < 0 or n < k:\n", " return 0\n", " elif (k==0 or n==k):\n", " return 1\n", " return binom(n-1,k) + binom(n-1,k-1)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ ">>(4,2)\n", ">>>>(3,2)\n", ">>>>>>(2,2)\n", "<<<<<<(2,2)\n", ">>>>>>(2,1)\n", ">>>>>>>>(1,1)\n", "<<<<<<<<(1,1)\n", ">>>>>>>>(1,0)\n", "<<<<<<<<(1,0)\n", "<<<<<<(2,1)\n", "<<<<(3,2)\n", ">>>>(3,1)\n", ">>>>>>(2,1)\n", ">>>>>>>>(1,1)\n", "<<<<<<<<(1,1)\n", ">>>>>>>>(1,0)\n", "<<<<<<<<(1,0)\n", "<<<<<<(2,1)\n", ">>>>>>(2,0)\n", "<<<<<<(2,0)\n", "<<<<(3,1)\n", "<<(4,2)\n" ] }, { "data": { "text/plain": [ "6" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def binom_trace(n,k):\n", " result = binom_trace(n,k)\n", " return result\n", "\n", "def binom_trace(n,k,indent=1):\n", " #indent = how much to indent the printouts\n", " if (k<0 or n<0 or n>\"*indent + \"({},{})\".format(n,k))\n", " print(\"<<\"*indent + \"({},{})\".format(n,k))\n", " return 1\n", " print(\">>\"*indent + \"({},{})\".format(n,k))\n", " indent+=1\n", " val = binom_trace(n-1,k,indent) + binom_trace(n-1,k-1,indent)\n", " indent-=1\n", " print(\"<<\"*indent + \"({},{})\".format(n,k))\n", " return val\n", "\n", "binom_trace(4,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Now with memoization:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def binom_fast(n,k):\n", " mem = dict()\n", " return binom_mem(n,k,mem)\n", "\n", "def binom_mem(n,k,mem):\n", " if n < 0 or k < 0 or n < k:\n", " return 0\n", " elif (k==0 or n==k):\n", " return 1\n", " if (n,k) not in mem:\n", " mem[(n,k)] = binom_mem(n-1,k,mem) + binom_mem(n-1,k-1,mem)\n", " return mem[(n,k)]" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ ">>(4,2)\n", ">>>>(3,2)\n", ">>>>>>(2,2)\n", "<<<<<<(2,2)\n", ">>>>>>(2,1)\n", ">>>>>>>>(1,1)\n", "<<<<<<<<(1,1)\n", ">>>>>>>>(1,0)\n", "<<<<<<<<(1,0)\n", "<<<<<<(2,1)\n", "<<<<(3,2)\n", ">>>>(3,1)\n", ">>>>>>(2,1)\n", "<<<<<<(2,1)\n", ">>>>>>(2,0)\n", "<<<<<<(2,0)\n", "<<<<(3,1)\n", "<<(4,2)\n" ] }, { "data": { "text/plain": [ "6" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def binom_fast_trace(n,k):\n", " mem = dict()\n", " result = binom_mem_trace(n,k,mem)\n", " return result\n", "\n", "def binom_mem_trace(n,k,mem,indent=1):\n", " #indent = how much to indent the printouts\n", " if (k<0 or n<0 or n>\"*indent + \"({},{})\".format(n,k))\n", " print(\"<<\"*indent + \"({},{})\".format(n,k))\n", " return 1\n", " print(\">>\"*indent + \"({},{})\".format(n,k))\n", " indent+=1\n", " if (n,k) not in mem:\n", " mem[(n,k)] = binom_mem_trace(n-1,k,mem,indent) + binom_mem_trace(n-1,k-1,mem,indent)\n", " indent-=1\n", " print(\"<<\"*indent + \"({},{})\".format(n,k))\n", " return mem[(n,k)]\n", "\n", "binom_fast_trace(4,2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Analysis of binom_fast(n,k):\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Change problem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A bus driver needs to give an exact change and she has coins of limited types. She has infinite coins of each type.\n", "Given the amount of change ($amount$) and the coin types (the list $coins$), how many ways are there? \n", "\n", "solution:\n", "The requested value (denoted as $W(amount, coins)$) is equal to the number of ways to give the change when using coins of type $coins[-1]$ at least once plus the number of ways to give the change without using coins of type $coins[-1]$.\n", "$W(amount, coins) = W(amount-coins[-1], coins) + W(amount, coins[:-1])$\n", "\n", "stopping crtiteria:\n", "- If $amount == 0$ return 1\n", "- If $amount <0$ or $coins==[]$ return 0\n", "\n", "This function change() below has an exponential time complexity." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From previous class:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def change(amount, coins):\n", " if amount == 0:\n", " return 1\n", " elif amount < 0 or coins == []:\n", " return 0\n", " return change(amount, coins[:-1]) +\\\n", " change(amount - coins[-1], coins)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Now with memoization:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def change_mem(amount, coins):\n", " d = {}\n", " return change_rec(amount, coins, d)\n", "\n", "def change_rec(amount, coins, d):\n", " if amount == 0:\n", " return 1\n", " elif amount < 0 or coins == []:\n", " return 0\n", " if (amount, tuple(coins)) in d:\n", " return d[(amount, tuple(coins))]\n", " else:\n", " d[(amount, tuple(coins))] = change_rec(amount, coins[:-1],d) +\\\n", " change_rec(amount - coins[-1], coins,d)\n", " return d[(amount, tuple(coins))]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Count paths" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We solved question 2(b) from the 2015 fall semester exam (Moed B):\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### From previous class:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def cnt_paths(L):\n", " if all_zeros(L):\n", " return 1\n", " \n", " result = 0\n", " for i in range(len(L)):\n", " if L[i] != 0:\n", " L[i] -= 1\n", " result += cnt_paths(L)\n", " L[i] += 1\n", " return result\n", "\n", "def all_zeros(L):\n", " for i in L:\n", " if i != 0:\n", " return False\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Now with memoization:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def cnt_paths_mem(L):\n", " d = {}\n", " return cnt_paths_rec(L,d)\n", "\n", "def cnt_paths_rec(L,d):\n", " if all_zeros(L):\n", " return 1\n", " elif tuple(L) not in d:\n", " result = 0\n", " for i in range(len(L)):\n", " if L[i] != 0:\n", " L[i] -= 1\n", " result += cnt_paths_rec(L,d)\n", " L[i] += 1\n", " d[tuple(L)] = result\n", " return d[tuple(L)]\n", "\n", "def all_zeros(L):\n", " for i in L:\n", " if i != 0:\n", " return False\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Catalan numbers" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We solved question 5 from the 2015 spring semester exam (Moed B):\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### An iterative implementation (section a):" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def catalan1(n):\n", " cat = [0]*(n+1)\n", " cat[0] = 1\n", " for i in range(1,n+1):\n", " for j in range(i):\n", " cat[i] += cat[j] * cat[i-j-1]\n", " \n", " return cat[n]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Complexity (section b):\n", "Let's consider the significant operations invelved in the function. First, it creates a list of size $n+1$, so that's $O(n)$ work. Then, it iterates through two loops, in a nested structure, where the inner loop is dependent on the outer loop. \n", "Using the tools we learned in class, we can analyze thenumber of iteration: $\\sum_{i=1}^{n} i = O(n^2)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A recursive implementation with memoization (section c):" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def catalan2(n):\n", " d = dict()\n", " return catalan_rec(n,d)\n", "\n", "def catalan_rec(n,d):\n", " if n == 0:\n", " return 1\n", " if n not in d:\n", " result = 0\n", " for j in range(n):\n", " result += catalan_rec(j,d) * catalan_rec(n-j-1,d)\n", " d[n] = result\n", " return d[n]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Analysis of the recursive version:\n", "When we look at the implementation, we have two recursive calls in each inner loop. The resulting tree will have a branch of length $n$, where the amount of work done in the node in depth $i$ of this branch is $n-i$. All other branches are of length at most $2$, since the function employs memoization. Thus, the complexity is $\\sum_{i=0}^{n} n-i = O(n^2)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Intro to primes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Fermat's little theorem: if $p$ is prime and $1 < a < p$, then $a^{p-1} (\\textrm{mod}\\ p) \\equiv 1$\n", "\n", "Equivalently: if $m$ is not a prime then there exists $1 < a < p$ such that $a^{p-1} (\\textrm{mod}\\ p) \\not\\equiv 1$. Such a number $a$ is called a witness to the fact that $m$ is not prime.\n", "\n", "In our probabilistic primality test, we will try random $a$s and see if one works." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Primality test using Fermat's witness" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 is composite \n", " 3 is a witness, i= 2\n" ] }, { "data": { "text/plain": [ "False" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import random\n", "\n", "def is_prime(m, show_witness=False):\n", "\n", " \"\"\" probabilistic test for m's compositeness \"\"\"\n", "\n", " for i in range(0,100):\n", " a = random.randint(1,m-1) # a is a random integer in [1..m-1]\n", " if pow(a,m-1,m) != 1:\n", " if show_witness: # caller wishes to see a witness\n", " print(m,\"is composite\",\"\\n\",a,\"is a witness, i=\",i+1)\n", " return False\n", "\n", " return True\n", "\n", "is_prime(10, show_witness=True)\n", "# is_prime(503, show_witness=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### The probability for error:\n", "First, notice that if the function says that an imput number $m$ is not prime, then it is true. \n", "The function can make a mistake only is the case where a number $m$ is not prime, and is excidentally categorized by the function as prime. This can happen if all $100$ $a$'s that the function tried were not witnesses. According to the Miller-Rabin theorem $\\frac{3}{4}$ of all possible $a$s are witnesses, so the probability for error is $(\\frac{1}{4})^{100}$ (this is extremely low)." ] } ], "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 }