We discussed memoization and demonstrated it using our recursive implementations for binom, change, and cnt_paths. We have additionally solved an exam question about Catalan numbers which involved recursion, memoization, and complexity. Finally, we gave an intro to analysis of prime numbers and primality testing. We will continue this subject in the next recitation.
and finally changing your recursive implementation so that it we rely and update the dictionary.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
The number of sets of size $k$ selected from a set of $n$ elements (with no repetitions) Recursive formula (Pascal): $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ where the stopping criterion is $\binom{n}{0} = \binom{n}{n} = 1$
The time complexity of binom is exponential in $n$ (worst case behaviour is when $k=\frac{n}{2}$)
def binom(n,k):
if n < 0 or k < 0 or n < k:
return 0
elif (k==0 or n==k):
return 1
return binom(n-1,k) + binom(n-1,k-1)
def binom_trace(n,k):
result = binom_trace(n,k)
return result
def binom_trace(n,k,indent=1):
#indent = how much to indent the printouts
if (k<0 or n<0 or n<k): # safety checks
return 0
elif (k==0 or k==n): # halting conditions
print(">>"*indent + "({},{})".format(n,k))
print("<<"*indent + "({},{})".format(n,k))
return 1
print(">>"*indent + "({},{})".format(n,k))
indent+=1
val = binom_trace(n-1,k,indent) + binom_trace(n-1,k-1,indent)
indent-=1
print("<<"*indent + "({},{})".format(n,k))
return val
binom_trace(4,2)
>>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2)
6
def binom_fast(n,k):
mem = dict()
return binom_mem(n,k,mem)
def binom_mem(n,k,mem):
if n < 0 or k < 0 or n < k:
return 0
elif (k==0 or n==k):
return 1
if (n,k) not in mem:
mem[(n,k)] = binom_mem(n-1,k,mem) + binom_mem(n-1,k-1,mem)
return mem[(n,k)]
def binom_fast_trace(n,k):
mem = dict()
result = binom_mem_trace(n,k,mem)
return result
def binom_mem_trace(n,k,mem,indent=1):
#indent = how much to indent the printouts
if (k<0 or n<0 or n<k): # safety checks
return 0
elif (k==0 or k==n): # halting conditions
print(">>"*indent + "({},{})".format(n,k))
print("<<"*indent + "({},{})".format(n,k))
return 1
print(">>"*indent + "({},{})".format(n,k))
indent+=1
if (n,k) not in mem:
mem[(n,k)] = binom_mem_trace(n-1,k,mem,indent) + binom_mem_trace(n-1,k-1,mem,indent)
indent-=1
print("<<"*indent + "({},{})".format(n,k))
return mem[(n,k)]
binom_fast_trace(4,2)
>>(4,2) >>>>(3,2) >>>>>>(2,2) <<<<<<(2,2) >>>>>>(2,1) >>>>>>>>(1,1) <<<<<<<<(1,1) >>>>>>>>(1,0) <<<<<<<<(1,0) <<<<<<(2,1) <<<<(3,2) >>>>(3,1) >>>>>>(2,1) <<<<<<(2,1) >>>>>>(2,0) <<<<<<(2,0) <<<<(3,1) <<(4,2)
6
Analysis of binom_fast(n,k):
A bus driver needs to give an exact change and she has coins of limited types. She has infinite coins of each type. Given the amount of change ($amount$) and the coin types (the list $coins$), how many ways are there?
solution: 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]$. $W(amount, coins) = W(amount-coins[-1], coins) + W(amount, coins[:-1])$
stopping crtiteria:
This function change() below has an exponential time complexity.
def change(amount, coins):
if amount == 0:
return 1
elif amount < 0 or coins == []:
return 0
return change(amount, coins[:-1]) +\
change(amount - coins[-1], coins)
def change_mem(amount, coins):
d = {}
return change_rec(amount, coins, d)
def change_rec(amount, coins, d):
if amount == 0:
return 1
elif amount < 0 or coins == []:
return 0
if (amount, tuple(coins)) in d:
return d[(amount, tuple(coins))]
else:
d[(amount, tuple(coins))] = change_rec(amount, coins[:-1],d) +\
change_rec(amount - coins[-1], coins,d)
return d[(amount, tuple(coins))]
We solved question 2(b) from the 2015 fall semester exam (Moed B):
def cnt_paths(L):
if all_zeros(L):
return 1
result = 0
for i in range(len(L)):
if L[i] != 0:
L[i] -= 1
result += cnt_paths(L)
L[i] += 1
return result
def all_zeros(L):
for i in L:
if i != 0:
return False
return True
def cnt_paths_mem(L):
d = {}
return cnt_paths_rec(L,d)
def cnt_paths_rec(L,d):
if all_zeros(L):
return 1
elif tuple(L) not in d:
result = 0
for i in range(len(L)):
if L[i] != 0:
L[i] -= 1
result += cnt_paths_rec(L,d)
L[i] += 1
d[tuple(L)] = result
return d[tuple(L)]
def all_zeros(L):
for i in L:
if i != 0:
return False
return True
We solved question 5 from the 2015 spring semester exam (Moed B):
def catalan1(n):
cat = [0]*(n+1)
cat[0] = 1
for i in range(1,n+1):
for j in range(i):
cat[i] += cat[j] * cat[i-j-1]
return cat[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. Using the tools we learned in class, we can analyze thenumber of iteration: $\sum_{i=1}^{n} i = O(n^2)$.
def catalan2(n):
d = dict()
return catalan_rec(n,d)
def catalan_rec(n,d):
if n == 0:
return 1
if n not in d:
result = 0
for j in range(n):
result += catalan_rec(j,d) * catalan_rec(n-j-1,d)
d[n] = result
return d[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)$.
Fermat's little theorem: if $p$ is prime and $1 < a < p$, then $a^{p-1} (\textrm{mod}\ p) \equiv 1$
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.
In our probabilistic primality test, we will try random $a$s and see if one works.
import random
def is_prime(m, show_witness=False):
""" probabilistic test for m's compositeness """
for i in range(0,100):
a = random.randint(1,m-1) # a is a random integer in [1..m-1]
if pow(a,m-1,m) != 1:
if show_witness: # caller wishes to see a witness
print(m,"is composite","\n",a,"is a witness, i=",i+1)
return False
return True
is_prime(10, show_witness=True)
# is_prime(503, show_witness=True)
10 is composite 3 is a witness, i= 2
False
First, notice that if the function says that an imput number $m$ is not prime, then it is true. 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).