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.

[SarahTew]

I did the exponent algorithm from a previous set of exercises. I made two different programs, one that can only handle positive exponents and another one which can handle positive and negative exponents.

Positive Exponents Only:

def exponent_dict(base_number, exponent, dictionary):
    key_pair = (base_number, exponent)
    if exponent < 0:
        return ("Positive Exponents Only!")
    elif key_pair not in dictionary:
        if exponent == 0:
            return 1
        else:
            dictionary[key_pair] = base_number * exponent_dict(base_number, exponent - 1, dictionary)
    return dictionary[key_pair]
my_dict = {}
print(exponent_dict(2,2,my_dict))
print(exponent_dict(3,3, my_dict))
print(exponent_dict(5,-2, my_dict))
print(exponent_dict(2, 0, my_dict))

def test_exponent_dict(base_number,exponent, dictionary, expected):
    result = exponent_dict(base_number, exponent, dictionary)
    if result == expected:
       return True
    else: 
        return False
        
print(test_exponent_dict(2,2,my_dict,4))
print(test_exponent_dict(2,1,my_dict,2))
print(test_exponent_dict(50,0, my_dict,1))
print(test_exponent_dict(3, -2, my_dict, "Positive Exponents Only!"))

Negative Exponents:
I kept getting an arithmetic error similar to what is happening here https://stackoverflow.com/questions/45071158/arithmetic-error-python-is-incorrectly-dividing-variables. In my code I have added rounding in order to get around this issue for large negative numbers. It rounds to the 17th place after the decimal point so that means it doesn't work correctly for very small negative exponents. I left a comment within the code if you want to see how it behaves without the rounding.

I understand why I'm getting the arithmetic error but I don't understand how to correct in this particular case. If anyone knows, please tell me.

def exponent2(base_number, exponent, dictionary):
    key_pair = (base_number, exponent)
    if key_pair not in dictionary:
        if exponent == 0:
            return 1
        elif exponent <= 0:
            dictionary[key_pair] = round(1 / base_number * exponent2(base_number, exponent + 1, dictionary),17)
            #change the above line to see arithmetic error:
            #dictionary[key_pair] = 1 / base_number * exponent2(base_number, exponent + 1, dictionary)
        else: 
            dictionary[key_pair] = base_number * exponent2(base_number, exponent - 1, dictionary)
            
    return dictionary[key_pair]
my_dict = {}
print(exponent2(2,2,my_dict))
print(exponent2(2,-1,my_dict))
print(exponent2(5,-3,my_dict))
print(exponent2(10, -8, my_dict))

def test_exponent2(base_number, exponent, dictionary, expected):
    result = exponent2(base_number, exponent, dictionary)
    if result == expected:
        return True
    else:
        return False
print(test_exponent2(2,2,my_dict, 4))
print(test_exponent2(2,-1,my_dict, 0.5))
print(test_exponent2(5,-3,my_dict, 0.008))

[diegochillo]

Debug print instruction here too, to check when results are taken from the dictionary.

def exponentiation(base_number,exponent,d):
  tpl=(base_number, exponent)

  if tpl not in d:
     if exponent == 0:
       d[tpl]=1
     elif exponent>0:
       d[tpl]=base_number * exponentiation(base_number, exponent - 1,d) 
     else:
       d[tpl]=(1 / base_number) * exponentiation(base_number, exponent+1,d)
  else:
     print ("DEBUG Found " + str(d[tpl]))

  return d[tpl]
    
def test_exponentiation(base_number,exponent,d,expected):
  result=exponentiation(base_number,exponent,d)
  return result==expected

# Test cases
sd=dict()
print(test_exponentiation(17, 1, sd, 17)) 
print(test_exponentiation(2, 0, sd, 1))
print(test_exponentiation(3, 4, sd, 81)) 
print(test_exponentiation(3, 6, sd, 729)) 
print(test_exponentiation(3, 9, sd, 19683))

print(test_exponentiation(2, -4, sd, 0.0625))
print(test_exponentiation(2, -5, sd, 0.03125))
print(test_exponentiation(3, -3, sd, 0.037037037037037035))

[giorgiasampo]

def test_exponentiation(base, exp, solution_dict, expected):
    result = exponentiation(base, exp, solution_dict)
    return result==expected

def exponentiation(base, exp, solution_dict):
    if base == 0:
        solution_dict[base]= "Impossible"
    elif exp == 0:
        solution_dict[base]=1
    elif exp == 1:
        solution_dict[base] = base
    else:
        solution_dict[base] = base * exponentiation(base, exp - 1, solution_dict)
    return solution_dict[base]

print(test_exponentiation(2,5,dict(),32))
print(test_exponentiation(2,0,dict(),1))
print(test_exponentiation(2,1,dict(),2))
print(test_exponentiation(0,5,dict(),"Impossible"))

[dbrembilla]

def exponentiation(base, exponent, sol_dict):
    if base == 0 and exponent == 0:
        return "Impossible"
    elif base != 0 and exponent == 0:
        return 1
    elif  exponent > 0 :
        if base == 0:
              return 0:
        else:    
              sol_dict[(base, exponent)] = base * exponentiation(base, exponent-1, sol_dict)
    elif exponent < 0: # rounded up to the 5th decimal
         if base == 0:
                return "Infinity"
         else:
                sol_dict[(base, exponent)] = round(1 / base * exponentiation(base, exponent+1, sol_dict), 5)
    return sol_dict[(base, exponent)]

def test(base, exponent, sol_dict, expected):
    return exponentiation(base, exponent, sol_dict) == expected
print(test(4,2,{}, 16)) #returns True
print(test(9,3, {}, 729))#returns True
print(test(4,-2,{},0.0625)) #True
print(test(0,0, {}, "Impossible"))#True 
print(test(4,-5, {}, 0.00098))#True

[AleRosae]

def test_exp(base_number, exponent, sol_dict, expected):
    return expected == exponentiation(base_number, exponent, sol_dict)

def exponentiation (base_number, exponent, sol_dict):
    if base_number not in sol_dict:
        if exponent == 0 and base_number == 0:
            return "No!"
        elif exponent == 0:
            sol_dict[base_number] = 1
        elif exponent == 1:
            sol_dict[base_number] = base_number
        elif exponent < 0:
            sol_dict[base_number] = 1 / (base_number) * (exponentiation(base_number, exponent + 1, sol_dict))
        else:
            sol_dict[base_number] = base_number * exponentiation(base_number, exponent-1, sol_dict)

    return sol_dict.get(base_number)

print(exponentiation(3,5,dict()))
print(test_exp(3,4, dict(), 81))
print(test_exp(17,1,dict(),17))
print(test_exp(2,0,dict(),1))
print(test_exp(2,-4,dict(),0.0625))
print(test_exp(0,0,dict(),"No!"))

[LuisAmmi]

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

def exponentiation(base_n, exp, dictionary):
    if (base_n, exp) not in dictionary:
        if exp == 0:
           dictionary[(base_n, exp)] = 1 # base case
        elif exp == 1:
            dictionary[(base_n, exp)] = base_n  # base case 2
        else:
           dictionary[(base_n, exp)] = base_n * exponentiation(base_n, exp - 1, dictionary)
    return dictionary.get((base_n, exp))

print(test_exponentiation(3, 4, {}, 81)) # true
print(test_exponentiation(17, 1, {}, 17))
print(test_exponentiation(2, 0, {}, 1))

[GiuliaMenna]

def test_exp(base_number, exponent, dictionary, expected):
    result = exp(base_number, exponent, dictionary)
    if expected == result:
        return True
    else:
        return False

def exp(base_number, exponent, dictionary):
    if (base_number, exponent) not in dictionary:
        if exponent == 0:
            dictionary[(base_number, exponent)] = 1 #base case
        else:
            dictionary[(base_number, exponent)] = base_number * exp(base_number, exponent - 1, dictionary)

    return dictionary.get((base_number, exponent))

print(test_exp(7,4, {}, 2401))
print(test_exp(28,1, {}, 28))
print(test_exp(9,0, {}, 1))

[ChiaraCati]

def test_exp(base, exponent, solution_dict, expected):
    result = exponential(base, exponent, solution_dict)
    if result == expected:
        return True
    else:
        return False


def exponential(base, exponent, solution_dict):
    if exponent >= 0:  # for exponent
        if exponent == 0:
            solution_dict[exponent] = 1
        elif exponent == 1:
            solution_dict[exponent] = base
        else:
            solution_dict[exponent] = base * exponential(base, exponent - 1, solution_dict)
    else:
        n= 1 / base
        if exponent == -1:
            solution_dict[exponent] = n
        else:
            solution_dict[exponent] = round(n * exponential(base, exponent + 1, solution_dict), 2)

    return solution_dict[exponent]

print(exponential(4, 2, dict()))
print(test_exp(3, 4, dict(), 81))
print(test_exp(17, 1, dict(), 17))
print(test_exp(2, 0, dict(), 1))
print(test_exp(4, -2, dict(), 0.06))

[gabrielefiorenza]

def test_binary_search(item, ordered_list, start, end,sd,expected):
    result =binary_search(item, ordered_list, start, end,sd)
    return expected == result

def binary_search(item, ordered_list, start, end,sd):
    if item not in sd:
        if item not in ordered_list:
            sd[item]=None
        else:
            middle = (end-start)//2
            if ordered_list[middle] == item:
                sd[item] = middle+start
            elif ordered_list[middle] < item:
                 sd[item]=binary_search(item,ordered_list,end-middle,end,sd)
            elif ordered_list[middle] >item:
                sd[item] = binary_search(item, ordered_list,start, start+middle,sd)
    return sd.get(item)

mylist=list(["tablet", "pc", "pen","pencil","room"])
print(test_binary_search("pc",mylist,0,4,dict(),1)) # returns True

[vanessabonanno]

# dynamic programming approach
def test_exponentiation(num, exp, solution_dict, expected):
    result = exponentiation(num, exp, solution_dict)
    if result == expected:
        return True
    else:
        return False


def exponentiation(num, exp, solution_dict):
    if (num, exp) not in solution_dict:
        if exp == 0:
            # return 1  # original code - base condition now doesn't return 1
            # but it adds elements to a dictionary:
            solution_dict[(num, exp)] = 1
        elif exp == 1:
            # return num # original code
            solution_dict[(num, exp)] = num
        elif exp > 0:
            # return num * exponentiation(num, exp - 1) # original code
            solution_dict[(num, exp)] = num * exponentiation(num, exp - 1, solution_dict)
        elif exp < 0:
            # return 1 / num * exponentiation(num, exp + 1) # original code
            solution_dict[(num, exp)] = 1 / num * exponentiation(num, exp + 1, solution_dict)

# I tried putting brackets before "num" and after "solution_dict)" above
# but somehow the result with a negative exponent was different (and wrong) than
# writing the division "1 / num * exponentiation(num, exp + 1, solution_dict)"
# without brackets and I don't understand why...

        else:
            return "Wrong input"
    # at the end algorithm returns the value related to that key:
    return solution_dict.get((num, exp))


my_dict = {}

print(exponentiation(3, 0, my_dict))   # output: 1
print(exponentiation(3, 2, my_dict))   # output: 9
print(exponentiation(3, 3, my_dict))   # output: 27
print(exponentiation(3, -3, my_dict))  # output: 0.037037037037037035

print(test_exponentiation(3, -3, my_dict, 0.037037037037037035))  # True
print(test_exponentiation(3, 0, my_dict, 0))                      # False

[fcagnola]

from test import test_5_parameter

# dynamic programming approach
def binary_search(item, ordered_list, start, end, solutions):

    if item in solutions: # base case for dynamic programming: if solution is in the dict, return that
        return solutions[item]

    mid = (start + end) // 2  # the middle of the section to be searched is stored in a variable

    if item == ordered_list[mid]:  # base case: if the item is found in the middle, return item and position
        solutions[item] = mid # store the solution in the dict
        return mid

    elif start == mid: # with this line python won't raise RecursionError, if start == middle it means value not in list
        return "Value not in list"

    elif ordered_list[mid] < item:  # if item comes after middle re-run search in the second half of the list
        solutions[item] = binary_search(item, ordered_list, mid, end, solutions)  # store the solution in the dict
        return solutions[item]

    elif ordered_list[mid] > item:  # if item comes before middle re-run search in the first half of the list
        solutions[item] = binary_search(item, ordered_list, start, mid, solutions)  # store the solution in the dict
        return solutions[item]


ord_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'z']

print(test_5_parameter(binary_search, "a", ord_list, 0, len(ord_list)-1, f, 0))  # Returns True
print(test_5_parameter(binary_search, "j", ord_list, 0, len(ord_list)-1, f, "Value not in list"))  # Returns True
print(test_5_parameter(binary_search, "l", ord_list, 0, len(ord_list)-1, f, 9))  # Returns True

for i in "abcdefghijklmnopqrstuvwxyz":
    print(binary_search(i, ord_list, 0, 21, d))
for i in "jaoknfbwobpqwmnsdènasjicubweovcpmdvowbjuvyvssca":
    print(binary_search(i, ord_list, 0, len(ord_list)-1, d))
for i in "bvhsfoiuqgbawòodiaèpàòdhsjvblòoqèpwoiruytrhdsjalbcznm":
    print(binary_search(i, ord_list, 0, len(ord_list) - 1, d))
print(d)

[AlessandraFa]

def test_new_exp(base_n, exp, exp_dict, expected):
    result = new_exp(base_n, exp, exp_dict)
    return result == expected


def new_exp(base_n, exp, exp_dic):
    if base_n < 0:
        return "Please insert positive base."
    if exp <= 0 and base_n == 0:
        return "Not possible. Try again."
    if (base_n, exp) not in exp_dic:
        if exp == 0:
            exp_dic[(base_n, exp)] = 1
        if exp < 0:
            exp_dic[(base_n, exp)] = 1/base_n * new_exp(base_n, exp + 1, exp_dic)
        else:
            exp_dic[(base_n, exp)] = base_n * new_exp(base_n, exp - 1, exp_dic)
    return exp_dic.get((base_n, exp))


dictionary = {}
print(test_new_exp(0, -2, dictionary, "Not possible. Try again."))
print(test_new_exp(2, 7, dictionary, 128))
print(test_new_exp(2, 3, dictionary, 8))
print(test_new_exp(-2, -4, dictionary, "Please insert positive base."))
print(test_new_exp(5, -1, dictionary, 1/5))

[SofiBar]

def exponentiation_dp(base_number, exponent, dic):
    tup = (base_number, exponent)

    if tup not in dic:
        if exponent == 1:
            dic[tup] = base_number
        elif exponent == 0:
            dic[tup] = 1
        elif exponent < 0:
            dic[tup] = 1/exponentiation_dp(base_number, -1*exponent, dic)
        else:
            dic[tup] = base_number*exponentiation_dp(base_number, exponent-1, dic)
    return dic.get(tup)

def test_exponentiation_dp(base_number, exponent, dic, expected):
    if exponentiation_dp(base_number, exponent, dic) == expected:
        return True
    else:
        return False
    
    
expo_dict = {}
print(test_exponentiation_dp(2, 4, expo_dict, 16))
print(test_exponentiation_dp(-3, 1, expo_dict, -3))
print(test_exponentiation_dp(5, 0, expo_dict, 1))
print(test_exponentiation_dp(0, 4, expo_dict, 0))
print(test_exponentiation_dp(3, -2, expo_dict, 0.1111111111111111))

[AlessandroBertozzi]

def test_binary_search(item, ordered_list, start, end, empty_dictionary, expected):
    result = binary_search(item, ordered_list, start, end, empty_dictionary)
    return result == expected


library = {}


def binary_search(item, ordered_list, start, end, empty_dictionary):
    my_list = ordered_list[start:end]
    position = len(my_list) // 2
    if item not in empty_dictionary:
        # Basic case
        if len(my_list) == 1 and item != my_list[position]:
            return None
        elif item == my_list[position]:
            empty_dictionary[my_list[position]] = position
            return position
        # Divide and conquer
        elif item < my_list[position]:
            empty_dictionary[my_list[position]] = position
            return binary_search(item, my_list, start, position, empty_dictionary)
        else:
            empty_dictionary[my_list[position]] = position
            return position + binary_search(item, my_list, position, end, empty_dictionary)
    else:
        return empty_dictionary.get(item)


print(test_binary_search("Le metamorfosi", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
                                            "Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
                                            "The Great Gatsby"], 0, 7, library, 3))

print(test_binary_search("Le metamorfosi", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
                                            "Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
                                            "The Great Gatsby"], 0, 7, library, 3))
print(test_binary_search("Il castello", ["Alice in Wonderland", "Il castello", "Le chiavi del regno",
                                         "Le metamorfosi", "Lolita", "Promessi sposi", "The Grapes of Wrath",
                                         "The Great Gatsby"], 0, 7, library, 1))

I define an external dictionary and then, every time I run my function, I check if input book is in my library (list) menawhile storing its position in a dictionary for a future research.