Python I will give a like

import random, timeit

def mystery1(vals):

diff = 0

for i in range(len(vals)):

for j in range(len(vals)):

if(vals[i] - vals[j] > diff):

diff = vals[i] - vals[j]

return diff

def mystery2(filename):

time = {}

with open(filename) as fp:

text = fp.read()

for ltr in text:

time[ltr] = text.count(ltr)

return time

def mystery3(filename):

storage = []

with open(filename) as fp:

for line in fp:

items = line.split()

name = items[0]

time = int(items[1])

if time >= len(storage): #Need more spots in storage

x = time - len(storage) + 1

extend = ['']*x #Makes a list of x empty strings

storage = storage + extend

storage[time] = name

sort_list = []

for spot in storage:

if spot != '': #Ignore empty spots

sort_list.append(spot)

return sort_list

if __name__ == '__main__':

lst = [random.randint(0, 9999999) for i in range(1000)]

time1 = timeit.timeit('mystery1(lst)', globals=globals(), number = 10)

out = mystery1(lst)

print("mystery1(lst) output:", out)

print("mystery1(lst) runtime:", time1, "seconds")

print(' ------------------ ')

time2 = timeit.timeit('mystery2("wizard.txt")', globals=globals(), number = 10)

out = mystery2('wizard.txt')

print("mystery2('wizard.txt') output:", out)

print("mystery2('wizard.txt') runtime:", time2, "seconds")

print(' ------------------ ')

time3 = timeit.timeit('mystery3("screentime_ms.txt")', globals=globals(), number = 10)

out = mystery3("screentime_ms.txt")

print("mystery3('screentime_ms.txt') output:", out)

print("mystery3('screentime_ms.txt') runtime:", time3, "seconds")

In this assignment, you're given three Python functions (mystery1, mystery2, and mystery3) that are implemented very inefficiently: your task is first to figure out what they are doing, and then to alter them so that they are asymptotically faster but still accomplish the same task. The first two functions are both quadratic (O(n2)) with respect to the size of their input: you should be able to find a solution that scales linearly (O(n)). The last function is theoretically exponential (O(kn)) with the size of the input because it scales with the values being passed in: for example if we started with the number ' 1000 ' in the input file and changed it to the number ' 1000000 ' then we've only doubled the input size ( 4 characters to 8 characters), but the runtime would be about 10000 times slower ( 1000 to 10000000). It's not possible to get this one to have a linear runtime, but you should be able to get it to be quadratic or even logilinear (O(nlgn)). Quadratic should be fast enough to pass the test cases, so you don't need to fully optimize the last one if you don't want to. We'll be using the timeit Python module to test whether or not your code has been improved. We're not concerned about full optimization, so anything under about 30ms(0.03s) for each of the three functions will be counted as "optimized enough" for full credit. Download the ZIP file pa02files.zip from Canvas, and unzip it. This contains two sample text files (screentime_ms.txt, wizard.txt). While there will be additional CSV files used for tests on Gradescope, you can assume the following about their contents: - Text files used to test mysteryz will consist of English prose using standard ASCII characters, similar to wizard.txt. - Text files used to test mystery 3 will follow the same format as screentime_ms.txt: each line contains one space, separating a word and a number. The zip folder should also contain a template file pa02.py. This is what you'll be editing and turning in to Gradescope at the end: the text files do not need to be submitted. The file contains three functions: - mystery1(vals) takes in a list of integers as input - mysteryz(filenane) takes in a string representing the name of a file as input - mysteryz (filename) takes in a string representing the name of a file as input The detalls of what each of these functions do are up to you to figure out. Once you've done so, alter the functions so that they implement a more efficient algorithm to solve the same problem. At the bottom of the file, we've included code in the if name_ == ' _ main ' block that tests these functions on inputs large enough to expose their inefficient design: it should generally take somewhere between 0.1 s and 10 s for each to run, depending on your machine. Your task is to implement a O(n) algorithm for the first two functions, and a O(n2) or O(nlgn) for the last one: this should cause the runtimes to go below 0.03 s even on relatively slow machines. Remember, you also must ensure that the functions still accomplish the same task as before: they should still yleld the same output for any given input