[SOLVED] :(csci 323) assignment 5 “estimate, evaluate and rank recurrences”

Overview:
In this assignment, we create generic code for the evaluation of recurrence relations, both for its own sake and as a tool to
test closed-form formulas that we may derive. To avoid the recomputation associated with recurrences, we store any
intermediate results in a dictionary. (This is known in the context of Dynamic Programming as “Memoization”.)In addition, we code the “Master Theorem” used to determine the order of magnitude of recurrences associated with some
divide-and-conquer algorithms.Submissions:
In the Google form. please submit the following.
● Assignment5.py (source code)
● Assignment5.txt (console output including table)
● Assignment5.png (bar graph)[0] Please see and follow the preliminary instructions in Assignment 1.
[1] Use this function to obtain the content of a function, i.e. the part after the return statement.
def func_body(f):
body = inspect.getsource(f) # gets the code
idx = body.index(“return”) # get the part after the word return
return ‘”‘ + body[7 + idx:].strip() + ‘”‘[2] Create an empty dictionary to store intermediate results and a helper function ff to efficiently run a function f for input n:
dict_funcs = {}
def ff(f, n):
func_name = f.__name__
if func_name not in dict_funcs:
dict_funcs[func_name] = {}
dict_func = dict_funcs[func_name]
if n not in dict_func:
dict_func[n] = f(f, n)
return dict_func[n][3] Define a sample function f1, like the one for MergeSort. Try to use the one-line if/else (aka “ternary expression”) as it
will make it easier to capture the function content in Task 1. Make sure that all quotients are converted to int.
def f1(f, n):
return 0 if n == 1 else 2 * ff(f, int(n/2)) + n[4] Test the function by calling from your main function
def call_and_print(func, n, desc):
print(func.__name__, desc, “for n =”, n, “is”, ff(func, n))
call_and_print(f1, 256, “f(n) = 2*f(n/2) + n”)[5] See all the intermediate values that were also computed by executing:
for func in dict_funcs:
func_name = func.__name__
print(func_name, dict_funcs[func_name])[6] Once this works, create functions f2 thru f10 corresponding to nine more recurrences from the slides or old exams.
[7] Define a function master_theorem(a, b, c) that determines the order of magnitude of the solution to a recurrence of the
form T(n) = aT(n/b) + O(n
c
). See See https://www.geeksforgeeks.org/how-to-analyse-complexity-of-recurrence-relation/[8] Define a function evaluate_functions to evaluate all functions in a list for a set of values of n. Use the function
run_searches from an earlier assignment as a starting point, but modify/simplify it as follows:
● replace “searches” with “functions” and the loop with “for func in functions”
● sizes can be called ns and will be a set of different values of n
● instead of search.__name__, use the content of the function per Task 1.
● we only need one trial
● nothing is random here – whatever we compute is what it is
● there is no need to time anything the value stored in the dictionary is the value of the function itself
● we don’t need to check any indexes because we aren’t searching[9] Invoke the code from an earlier assignment to print the table.
[10] Invoke the code from an earlier assignment to plot the graph.
Instead of just using labels f1, f2, etc., per Task 1, include what the function is computing[11] Because the range of inputs and outputs varies so greatly, you may be better off – for the purposes of the table and
graph – by taking the log of the input and log of the output. See https://en.wikipedia.org/wiki/Log%E2%80%93log_plot