Lecture "Dynamic programming algorithms", exercise 2

[essepuntato]

Choose any recursive algorithm introduced in the previous chapters and provide a new implementation of it in Python following the dynamic programming approach.

[Bianca-LM]

def` test_exponentiation(base_number, exponent, d, expected): 
    result = exponentiation(base_number, exponent, d)
    if expected == result: 
        return True
    else: 
        return False

def exponentiation(base_number, exponent, d):
    if base_number**exponent not in d: 
        if exponent == 0: 
            d[base_number**exponent] = 1
        elif exponent == 1:
            d[base_number**exponent] = base_number
        else: 
           d[base_number**exponent] = base_number * exponentiation(base_number, exponent-1, d)
    return d.get(base_number**exponent)


print(test_exponentiation(3,4, dict({1**2: 1}), 81))
print(test_exponentiation(17,1, dict(), 17))
print(test_exponentiation(2,0, dict({2**0:1, 3**1: 3.}), 1))

[AmeliaLamargese]

def test_exponentiation(int, exp, dictionary, expected):
    result = exponentiation(int, exp, dictionary)
    if result == expected:
        return True
    else:
        return False

def exponentiation(int, exp, dictionary):
    if int not in dictionary:    
        if exp == 0:
            dictionary[int] = 1
        elif exp == 1:
            dictionary[int] = int
        else:
            dictionary[int] = int * exponentiation(int, exp-1, dict)  

    return dictionary.get(int)  

print(test_exponentiation(2, 0, dict(), 1))
print(test_exponentiation(2, 1, dict(), 2))
print(test_exponentiation(2, 4, dict(), 16))

[ManueleVeggi]

def test_exponentiation(int_1, int_2, solution_dict, expected):
    result = exponentiation(int_1, int_2, solution_dict)
    if result == expected:
        return True
    else:
        return False

def exponentiation(int_1, int_2, solution_dict):
    if int_2 not in solution_dict:
        if int_2 == 0:
            solution_dict[int_2] = 1
        elif int_2 == 1:
            solution_dict[int_2] = int_1
        else: 
            solution_dict[int_2] = int_1 * exponentiation(int_1, int_2 - 1, solution_dict)
    
    return solution_dict.get(int_2)

print(test_exponentiation(3,0,dict(),1))
print(test_exponentiation(3,1,dict(),3))
print(test_exponentiation(3,2,dict(),9))
print(test_exponentiation(3,0,{0:1, 1:3, 2:9, 3:27},1))
print(test_exponentiation(3,1,{0:1, 1:3, 2:9, 3:27},3))
print(test_exponentiation(3,2,{0:1, 1:3, 2:9, 3:27},9))

The output is True for all the test cases

[olgagolgan]

[martasoricetti]

[tommasobattisti]

def test_factorial_recursive(n, d, expected):
    result = factorial_recursive(n, d)
    if expected == result:
        return True
    else:
        return False

factorial_dict = {}

def factorial_recursive(n, d):
    if n not in d:
        if n == 1:
            d[n] = 1
        else:
            d[n]= n * factorial_recursive(n-1, d)
    return d.get(n)

print(test_factorial_recursive(12, factorial_dict, 479001600))
print(test_factorial_recursive(7, factorial_dict, 5040))
print(test_factorial_recursive(3, factorial_dict, 6))

[CarmenSantaniello]

def test_exponentiation(base_number, exponent, solution_dict, expected):
    result = exponentiation(base_number, exponent, solution_dict)
    if result == expected:
        return True
    else:
        return False

def exponentiation(base_number, exponent, solution_dict):
    if base_number**exponent not in solution_dict:
        if exponent == 0:
            solution_dict[base_number**exponent] = 1
        elif exponent == 1:
            solution_dict[base_number**exponent] = base_number 
        else:
            solution_dict[base_number**exponent] = base_number * exponentiation(base_number, exponent - 1, solution_dict)

    return solution_dict.get(base_number**exponent)
    
print(test_exponentiation(3, 4, dict(), 81))
print(test_exponentiation(17, 1, dict(), 17))
print(test_exponentiation(2, 0 ,dict(), 1))
print(exponentiation(3, 4, dict()))
print(exponentiation(17, 1, dict()))
print(exponentiation(2, 0, dict()))

[AnastasiyaSopyryaeva]

#Defining test function

def test_exponentiation_extended(base_number, exponent, solution_dict, expected):
    result = exponentiation_extended(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else:
        return False

#Function code
def exponentiation_extended(base_number, exponent, solution_dict):
    numbers = base_number, exponent
    if numbers not in solution_dict:
        if exponent == 0:
            solution_dict[base_number, 0] = 1
        else:
            return base_number * exponentiation_extended(base_number, exponent - 1, solution_dict)
    return solution_dict.get(numbers)

#print
print(test_exponentiation_extended(3, 4, dict(), 81)) #true
print(test_exponentiation_extended(17, 1, dict(), 17)) #true
print(test_exponentiation_extended(2, 0, dict(), 1)) #true

[angstigone]

[essepuntato]

Hi,

just a few comments for you to check in your solutions:

• You cannot use the exponentiation operator "**" (nor "^", @martasoricetti, which does not what you think, try it in a Python shell) in the definition of your function since you are actually defining such an operator with your function. Using "**" is like defining a term in a word dictionary by using itself in the definition! Your function should define the operation, not reuse the existing one. Revise your algorithm to avoid using "**".

• Try to run your function passing the same dictionary with existing solutions in all the tests, avoiding creating a new dictionary every time. To do that, just initialise an empty dictionary in a variable and then pass it every time as input of your tests.

• Try to run your code using Python Tutor and see if the dictionary with existing solutions is used in some tests. If it is not used in all the tests, then what's the usefulness of having such a dictionary? Two possible explanations of this situation may be that (a) you are not storing the solutions in the dictionary as you think and, as such, they are not reused, or (b) you create a new dictionary in every test and thus no past solutions are really reused. Modify your code to avoid such situations.

[ahsanv101]

print(test_exp_rec(2, 0, dict(), 1))
print(test_exp_rec(3,1,dict(),3))
print(test_exp_rec(3,2,dict(),9))
print(test_exp_rec(3,0,{0:1, 1:3, 2:9, 3:27},1))
print(test_exp_rec(2, 1, dict(), 2))
print(test_exp_rec(2, 4, dict(), 16))
print(test_exp_rec(3,0,dict(),1))
print(test_exp_rec(3,1,{0:1, 1:3, 2:9, 3:27},3))
print(test_exp_rec(3,2,{0:1, 1:3, 2:9, 3:27},9))

[RebeccaJillianBeattie]

[sanyuezoe]

def exponentiation_dynamic_test(base_number, exponent, save_dict, expected):
    result = exponentiation_dynamic(base_number, exponent, save_dict)
    if result == expected:
        return True
    else:
        return False

def exponentiation_dynamic(base_number, exponent, save_dict):
    exponent_pair = (base_number, exponent)
    if exponent_pair not in save_dict:
            if exponent == 0:
                save_dict[exponent_pair] = 1
            else:
            save_dict[exponent_pair] = base_number * (exponentiation(base_number, exponent - 1, save_dict))

    return save_dict[exponent_pair]


my_dict =dict()

print(exponentiation_dynamic_test(3, 4, my_dict, 81))
print(exponentiation_dynamic_test(17, 1, my_dict, 17))
print(exponentiation_dynamic_test(2, 0, my_dict, 1))