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.

[arcangelo7]

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

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

print(test_exponentiation(3, 4, 81, dict())) # True
print(test_exponentiation(17, 1, 17, dict())) # True
print(test_exponentiation(2, 0, 1, dict())) # True

[sntcristian]

This is a dynamic version of the exponentiation algorithm that uses the property of multiplication between powers with same bases to implement a divide and conquer approach.

def test_exponentiation(base_number, exp, d, expected):
    result = exponentiation_dp(base_number, exp, d)
    if expected == result:
        return True
    else:
        return False

def exponentiation_dp (base_number, exp, d):
    if (base_number, exp) not in d:
        if exp == 0:
            d[(base_number, exp)] = 1
        elif exp == 1:
            d[(base_number, exp)] = base_number
        else:
            half_exp = exp // 2
            exponentiation1 = exponentiation_dp(base_number, half_exp, d)
            exponentiation2 = exponentiation_dp(base_number, half_exp, d)
            if exp % 2 == 0:
                d[(base_number, exp)] = exponentiation1 * exponentiation2
            else:
                d[(base_number, exp)] = exponentiation1 * exponentiation2 * base_number
    return d[(base_number, exp)] 

print(test_exponentiation(2, 5, dict(), 32)) #True
print(test_exponentiation(4, 4, dict(), 256)) #True
print(test_exponentiation(2, 9, dict(), 512)) #True

[FrancescoFernicola]

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

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


print(test_exponentiation(3, 4, 81, dict())) #True
print(test_exponentiation(17, 1, 17, dict()))  #True
print(test_exponentiation(2, 0, 1, dict()))  #True
print(test_exponentiation(0, 0, 1, dict()))  #True
print(test_exponentiation(1, 0, 1, dict()))  #True
print(test_exponentiation(0, 2, 0, dict()))  #True

[essepuntato]

Hi all,

please find attached my personal solution – also available online:

# Test case for the function
def test_exponentation(base_number, exponent, solution_dict, expected):
    result = exponentation(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else:
        return False


# Code of the function
def exponentation(base_number, exponent, solution_dict):
    exp_pair = (base_number, exponent)

    if exp_pair not in solution_dict:
        if exponent == 0:
            solution_dict[exp_pair] = 1
        else:
            solution_dict[exp_pair] = base_number * exponentation(base_number, exponent - 1, solution_dict)

    return solution_dict[exp_pair]


# Tests
my_dict = {}
print(test_exponentation(3, 2, my_dict, 9))
print(test_exponentation(3, 4, my_dict, 81))
print(test_exponentation(17, 1, my_dict, 17))
print(test_exponentation(2, 0, my_dict, 1))
print(test_exponentation(2, 6, my_dict, 64))
print(test_exponentation(0, 15, my_dict, 0))
print(test_exponentation(0, 0, my_dict, 1))