Lecture "Dynamic programming algorithms", exercise 1
Opened this issue · 15 comments
Write an extension of the multiplication function introduced in the lecture "Recursion", i.e. def multiplication(int_1, int_2, solution_dict), by using a dynamic programming approach. This new function takes in input two integer numbers to multiply and a dictionary with solutions of multiplications between numbers, which can be used to retrieve directly the result of such multiplication if already present in it. The function returns the result of the multiplication and, at the same time, modifies the solution dictionary adding additional solutions when found.
Accompany the implementation of the function with the appropriate test cases.
Hi prof and others,
I did not really understand the point of this exercise since,
If one would draw a tree chart for the multiplication 3×4 according to the example (listing 3) in lecture 'Recursion' there will be no repeating sub-solutions. Meaning that when a sub-solution is stored in the dictionary it will not be used again.
I am correct or am I missing the point?
@HiImBono
example:
I t
2* 4 means 2 + 2 + +2 + 2 or 4 + 4
so
step 1: 2 + 2
step 2: 2 + 4
step 3: 2 + 6
we can use recurssion to solve this problem.
i think in this way we can compute it
def test_multiplication(n1, n2, expected, d=dict()):
if multiplication(n1, n2, d=dict()) == expected:
return True
else:
return False
def multiplication(n1, n2, d=dict()):
if n2 not in d:
if n2 == 0:
d[n2] = n2
else:
d[n2]= n1 + multiplication(n1, n2 - 1, d)
return d[n2]
print(test_multiplication(4,3,12)) #True
print(test_multiplication(5,2,10)) #True
print(test_multiplication(3,3,9)) #True
def test_mult_dp(n1, n2, d, exp):
if exp == mult_dp(n1, n2, d):
return True
else:
return False
def mult_dp(n1, n2, d):
if n2 not in d:
if n2 == 0:
d[n2] = 0
elif n2 == 1:
d[n2] = n1
else:
d[n2] = n1 + mult_dp(n1, n2-1, d)
return d[n2]
print(test_mult_dp(15, 67, {}, 1005))
print(test_mult_dp(45, 6, {}, 270))
print(test_mult_dp(39, 16, {}, 624))
True
True
True
# test for the algorithm
def test_multiplication(int_1, int_2, expected, solution_dict):
result = multiplication(int_1, int_2, solution_dict)
if expected == result:
return True
else:
return False
# code of the algorithm
def multiplication(int_1, int_2, solution_dict):
# checking if a solution exists
if int_2 not in solution_dict:
if int_2 == 0: # base case
solution_dict[int_2] = int_2 # if the input int is 0 return that input int
else: # recursive step
solution_dict[int_2] = int_1 + multiplication(int_1, int_2 - 1, solution_dict) # store the result of the multiplication in the
return solution_dict[int_2] # dictionary using the original input as key
# run some tests
print(test_multiplication(0, 1, 0, ({})))
print(test_multiplication(3, 0, 0, ({})))
print(test_multiplication(0, 0, 0, ({})))
print(test_multiplication(3, 4, 12, ({})))
print(test_multiplication(1, 1, 1, ({})))
True
True
True
True
True
def test_mult_dp(multiplied, multiplier, expected):
result = mult_dp(multiplied, multiplier)
if expected == result:
return True
else:
return False
# the dictionary is going to be specific for our multiplied,
# and will hold keys of the form --> [multiplier] : result
def mult_dp(multiplied, multiplier, d=dict()):
if multiplier not in d: # Checking if a solution exists
if multiplier == 0: # base case
d[multiplier] = multiplier
elif multiplier == 1: # second base case
d[multiplier] = multiplied
else: # recursive step
# the dictionary will be passed as input of the recursive calls of the algorithm
d[multiplier] = multiplied + mult_dp(multiplied, (multiplier-1), d)
return d[multiplier]
print(test_mult_dp(3, 4, 12))
print(test_mult_dp(0, 0, 0))
def test_multiplication(a, b, dic, expected):
result = multiplication(a, b, dic)
if result == expected:
return True
else:
return False
def multiplication(a, b, dic=dict()):
if b not in dic:
if b == 0:
dic[b] = 0
if b == 1:
dic[b] = a
elif b < 0:
dic[b] = -(a - multiplication(a, b+1, dic))
return dic[b]
else:
dic[b] = a + multiplication(a, b-1, dic)
return dic[b]
print(test_multiplication(3, 4,({}),12)) #True
print((test_multiplication(-3,-4,({}), 12))) #True
print(test_multiplication(2,0,({}),0)) #True
print(test_multiplication(-10,1,({}),-10)) #True
def test_multiplication(n1, n2, d, expected):
result = multiplication(n1, n2, d)
if result == expected:
return True
else:
return False
def multiplication(n1, n2, d={}):
if n2 < 0:
n1 = -n1
n2 = -n2
key = str(n1) + "-" + str(n2)
if key not in d:
if n2 == 0:
return 0
d[key] = n1 + multiplication(n1, n2-1, d)
return d[key]
d = {}
print(test_multiplication(3, 4, d, 12)) # True
print(test_multiplication(5, 5, d, 25)) # True
print(test_multiplication(-6, 3, d, -18)) # True
Note:
This dynamic multiplication algorithm recognises if two numbers had been multiplied before. The algorithm creates a dictionary which contains all the product which had been calculated during previous execution. The key is created based on the two factors. The content of this dictionary can be used even if the algorithm is called with new entry values. For example, after multiplying the factors "5" and "7", the product for "3x5" or "5x1" can be retrieved from the dictionary. (The order of the factors makes no difference while searching for previous multiplication.)
+++ Dynamic Multiplication Algorithm +++
# Test Function
def test_multiplication_dp(int_1, int_2, expected):
return expected == multiplication_dp(int_1, int_2)
# Algorithm
def multiplication_dp(int_1, int_2, d=dict()):
if int_1 < int_2:
key = str(int_1) + str(int_2)
else:
key = str(int_2) + str(int_1)
if key not in d:
if int_2 == 0:
return 0
else:
d[key] = int_1 + multiplication_dp(int_1, int_2 - 1)
return d[key]
# Test Cases
print(test_multiplication_dp(5, 7, 35))
print(test_multiplication_dp(5, 1, 5))
print(test_multiplication_dp(2, 5, 10))
print(test_multiplication_dp(5, 3, 15))
print(test_multiplication_dp(5, 4, 20))
print(test_multiplication_dp(5, 5, 25))
print(test_multiplication_dp(7, 5, 35))
def test_multiplication(int_1, int_2, solution_dict, expected):
result = multiplication(int_1, int_2, solution_dict)
if expected == result:
return True
else:
return False
def multiplication(int_1, int_2, solution_dict):
if int_2 not in solution_dict: #check whether it's in the dict
if int_2 == 0:
solution_dict[int_2] = int_2
else:
solution_dict[int_2] = int_1 + multiplication(int_1, int_2 -1, solution_dict) #store info in the dict
return solution_dict[int_2]
print(test_multiplication(0, 0, ({}), 0)) #true
print(test_multiplication(1, 1, ({}), 1)) #true
print(test_multiplication(5, 2, ({}), 10)) #true
print(test_multiplication(8, 3, ({}), 24)) #true
print(test_multiplication(6, 5, ({}), 30)) #true
Guys, I'd like to give some feedback if you don't mind.
It seems like only the algorithm of @beccadelbens works. All the other algorithms contain at least one of the following two errors:
-
Resetting the Dictionary
The dictionary is only useful if it is available for future executions of the algorithm. Given the formula n1 x n2 = n1 + (n1 x (n2 - 1)), the algorithm has to calculate every pair of two factors only once. Hence, the content of the dictionary is not used during the first run of the algorithm. However, if the dictionary is available for future executions the algorithm can save computation time if the searched product has common factors with previous products. For example, after having calculated "6x6" the algorithm can retrieve the product for "6x3" from the dictionary.
The reset was done with an empty dictionary as input value "test_multiplication_dp(5, 7, 35, ({}))" or "test_multiplication_dp(5, 7, 35, d=dict())". (The "d=dict()" is only necessary to define a standard value for d in the def of a new function, but will reset the dictionary if used during the execution of an algorithm.) -
Using One Factor as Key
If only one factor is used as a key, the algorithm fails for many multiplications in which one factor is matching the key, but the other factor has changed. For example, if the factor "6" of the calculation "9x6" was used as a key, the algorithm will save "54" as value for the key "6". Hence, the algorithm will return a wrong value for the calculation "10x6". Since the algorithm will search the dictionary for the key "6" and will return the value "54" instead of returning "60".
Hopefully, this is helpful. Correct me if I am mistaken.
Cheers,
Sevi ✌️
def test_multiplication(n_1, n_2, expected, d=dict()):
result = multiplication(n_1, n_2, d=dict())
if result == expected:
return True
else:
return False
def multiplication(n_1, n_2, d=dict()):
if n_2 not in d:
if n_2 == 0:
d[n_2] = 0
else: #recursive step
d[n_2] = n_1 + multiplication(n_1, n_2 - 1, d)
return d[n_2]
print(test_multiplication(8, 8, 64, ({}))) #True
print(test_multiplication(2, 9, 18, ({}))) #True
print(test_multiplication(20, 0, 0, ({}))) #True
@SeverinJB thank you for pointing out the errors:
result = multiplication(int_1, int_2, solution_dict)
if result == expected:
return True
else:
return False
def multiplication(int_1, int_2, solution_dict={}):
if int_2 not in solution_dict:
if int_2 < 0:
int_1 = -int_1
int_2 = -int_2
key = str(int_1) + "-" + str(int_2)
if key not in solution_dict:
if (int_2) == 0:
return 0
solution_dict[key] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
return solution_dict[key]
Thank you @SeverinJB for your feedback, it was really helpful.
def test_multiplication(int_1, int_2, d, expected):
result = multiplication(int_1, int_2, d)
if expected == result:
return True
else:
return False
def multiplication(int_1, int_2, d={}):
cache = str(int_1) + "-" + str(int_2)
if cache not in d:
if int_2 == 0:
return 0
else:
d[cache] = int_1 + multiplication(int_1, int_2 - 1, d)
return d[cache]
print(test_multiplication(5, 5, ({}), 25))
print(test_multiplication(7, 5, ({}), 35))
print(test_multiplication(0, 0, ({}), 0))
print(test_multiplication(44, 44, ({}), 1936))
def test_multiplication(n_1, n_2, expected, d = dict()):
if multiplication(n_1, n_2, d=dict()) == expected:
return True
else:
return False
def multiplication(n_1, n_2, d=dict()):
if n_2 not in d:
if n_2 == 0:
d[n_2] = n_2
else:
d[n_2] = n_1 + multiplication(n_1, n_2 - 1, d)
return d[n_2]
print(test_multiplication(0, 0, 0, ({})))
print(test_multiplication(1, 0, 0, ({})))
print(test_multiplication(5, 7, 35, ({})))
Hi all,
Here my take on the exercise - source codes available online.
# Test case for the algorithm
def test_multiplication(int_1, int_2, solution_dict, expected):
result = multiplication(int_1, int_2, solution_dict)
if expected == result:
return True
else:
return False
# Code of the algorithm
def multiplication(int_1, int_2, solution_dict):
if int_1 < int_2:
mult_pair = (int_1, int_2)
else:
mult_pair = (int_2, int_1)
if mult_pair not in solution_dict:
if int_2 == 0:
solution_dict[mult_pair] = 0
else:
solution_dict[mult_pair] = int_1 + multiplication(int_1, int_2 - 1, solution_dict)
return solution_dict[mult_pair]
my_dict = {}
print(test_multiplication(0, 0, my_dict, 0))
print(test_multiplication(1, 0, my_dict, 0))
print(test_multiplication(5, 7, my_dict, 35))
print(test_multiplication(7, 7, my_dict, 49))