Choose any recursive algorithm introduced in the previous chapters and provide a new i

<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clip

Lecture "Dynamic programming algorithms", exercise 2,about comp-think/2020-2021

Comments (19)

SarahTew commented on August 27, 2024

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))

from 2020-2021.

diegochillo commented on August 27, 2024

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))

from 2020-2021.

giorgiasampo commented on August 27, 2024


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"))

from 2020-2021.

dbrembilla commented on August 27, 2024

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

from 2020-2021.

AleRosae commented on August 27, 2024

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!"))

from 2020-2021.

LuisAmmi commented on August 27, 2024

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))

from 2020-2021.

GiuliaMenna commented on August 27, 2024

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))

from 2020-2021.

ChiaraCati commented on August 27, 2024

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))

from 2020-2021.

gabrielefiorenza commented on August 27, 2024

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

from 2020-2021.

vanessabonanno commented on August 27, 2024

# 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

from 2020-2021.

fcagnola commented on August 27, 2024

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)

from 2020-2021.

AlessandraFa commented on August 27, 2024

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))

from 2020-2021.

SofiBar commented on August 27, 2024

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))

from 2020-2021.

AlessandroBertozzi commented on August 27, 2024

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.

from 2020-2021.

essepuntato commented on August 27, 2024

@fcagnola and @AlessandroBertozzi: I believe that your approach works only if I use exactly the same list for all the various calls, otherwise you may get an error in return, right?

@fcagnola: it is important to define the tests, as required by the text of the exercise. As far as I can see, you avoid doing that since you prefer to run several executions of the function. But this does not allow you to check if the result you obtain after each execution is correct or not.

from 2020-2021.

fcagnola commented on August 27, 2024

@fcagnola and @AlessandroBertozzi: I believe that your approach works only if I use exactly the same list for all the various calls, otherwise you may get an error in return, right?

@fcagnola: it is important to define the tests, as required by the text of the exercise. As far as I can see, you avoid doing that since you prefer to run several executions of the function. But this does not allow you to check if the result you obtain after each execution is correct or not.

@essepuntato you are right, for both observations. I hadn't really though of that limit, but it is in fact the case. If I were to, in any way, alter the input list, the algorithm would not work.
As for the test part, it was only laziness on my part, I had actually implemented the usual test function, I just hadn't copied it to the comment, I will edit the code and add it in now. thank you for taking the time to read all our code!

from 2020-2021.

edoardodalborgo commented on August 27, 2024

def test_pokemon_champion(input_list, i, dict, expected):
    return pokemon_champion(input_list, i, dict) == expected

def pokemon_champion(input_list, i, dict):
    if len(input_list) > 1:
        if i < len(input_list):
            left = input_list[i]
            right = input_list[i+1]
            if right > left:
                pair = (left, right)
            else:
                pair = (right, left)
            if pair not in dict:
                if left[1] > right[2]:
                    input_list.remove(right)
                    dict[pair] = left
                else:
                    input_list.remove(left)
                    dict[pair] = right
                i += 1
                pokemon_champion(input_list, i, dict)
        else:
            i = 0
            pokemon_champion(input_list, i, dict)
    return input_list[0]

i = 0
my_rec_dict = {}
pokemon_tournament = [("Poliwag",10,5), ("Charmander",15,2), ("Abra",8,7), ("Pidgey",4,5), ("Goldeen",6,8), ("Bulbasaur",12,10), ("Charmeleon",18,8), ("Psyduck",3,4)]
print(test_pokemon_champion(pokemon_tournament, i, my_rec_dict, ('Bulbasaur', 12, 10)))
pokemon_tournament1 = [("Poliwag",10,5), ("Charmander",15,2), ("Abra",8,7), ("Pidgey",4,5), ("Goldeen",6,8), ("Charmeleon",18,8), ("Psyduck",3,4), ("Pidgey",4,5)]
print(test_pokemon_champion(pokemon_tournament1, i, my_rec_dict, ("Poliwag",10,5)))

from 2020-2021.

IlaRoss commented on August 27, 2024

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

# algorithm
def exponentiation(base_number, exponent, solution_dictionary):
    if base_number == 0:
        return 0
    else:
        if exponent == 0:
            return 1

        mykey = (base_number, exponent)
        if mykey in solution_dictionary.keys():
            return solution_dictionary[mykey]
        else:
            if exponent > 0:
                result = base_number * exponentiation(base_number, exponent-1, solution_dictionary)
                solution_dictionary[mykey] = result
            elif exponent < 0:
                result = 1 / base_number * (exponentiation(base_number, exponent + 1, solution_dictionary))
                solution_dictionary[mykey] = result
        return solution_dictionary[mykey]

# test runs
adict = {}
print(test_exponentiation(3, 4, adict, 81))
print(test_exponentiation(17, 1, adict, 17))
print(test_exponentiation(2, 0, adict, 1))
print(test_exponentiation(3, 2, adict, 9))
print(test_exponentiation(0, 5, adict, 0))
print(test_exponentiation(-2, 3, adict, -8))
print(test_exponentiation(3, 0, adict, 1))

#print(adict)

from 2020-2021.

yunglong28 commented on August 27, 2024

Sorry for not posting this before. I added the string to the already stored result option just to diversify the two outputs.

def dyamic_exponentiation (base, exponent, dict1):
 power = (base, exponent)
 if power not in dict1:
    if exponent == 0:
        dict1[power] = 1
    elif exponent > 0:
        dict1[power] = base * dyamic_exponentiation(base, exponent - 1, dict1)
    else:
        dict1[power]  = (1 / base) * dyamic_exponentiation(base, exponent + 1, dict1)
 else:
     return "I stored the result already: " + str(dict1.get(power))

 return dict1[power]

def test_dynamic_exponentiation (base, exponent, dict1, expected):
    result = dyamic_exponentiation(base, exponent, dict1)
    if result == expected:
        return True
    else:
        return False


dictio = {}
print(test_dynamic_exponentiation(1, 0, dictio, 1))  #True
print(test_dynamic_exponentiation(1, 0, dictio,'I stored the result already: 1'))  #True
print(test_dynamic_exponentiation(3,2, dictio, 9))  #True
print(test_dynamic_exponentiation(2, -2, dictio, 0.25))  #True

from 2020-2021.

Lecture "Dynamic programming algorithms", exercise 2 about 2020-2021 HOT 19 OPEN

Comments (19)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent