For this part, you will be solving some problems and implementing the solutions. For this part, your goal is to design and implement solutions that are as fast as possible, and to analyze these solutions as well. You will submit two files:

a5_part1_xxxxxx.py  needs to contain the functions you are asked to write for each question. 

a5_part1_xxxxxx.txt needs to contain, for each function, a rough analysis of its running time in terms of n(where n is the length of the input list a, i.e. n=len(a)) and where n=10,000. For example, if your function looks like this:

def riddle(a):

         s=0

         for x in a:

             for y in a:

                 s = s+ x*y

         return s

 

Then you would write: This function has two nested for loops. The inner loop executes 10,000 times for each step of the outer loop, which also executes 10,000 times. Therefore, this function performs roughly 10,000*10,000=100,000,000 operations. If your function uses Python’s sort() method or Python’ssorted() function to sort the list a, just say that that function call does about 140,000 operations (since Python’s sort does roughly n log_2 n operations).

Alternatively, if you prefer, you can write your analysis in terms of general n. Thus for the above function riddle, one would say that its running time is O(n^2). 

In all of the questions below you may assume that a is a list containing numbers. 

1a) (5 points) Write a function, largest_34(a), that returns the sum of the 3rd and 4th largest values in the list a. For simplicity, you may assume that the numbers in the list a are all distinct and that the list a has at least 4 elements. For example:

>>> largest_34([1000, 1, 100, 2, 99, 200, -100])

199

1b) (5 points) Write a function, largest_third(a), that computes the sum of the len(a)//3 of the largest values in the list a. For simplicity, you may assume that the numbers in the list a are all distinct and that the list a has at least 3 elements.

1c) (5 points) Write a function, third_at_least(a), that returns a value in a that occurs at least len(a)//3 + 1 times. If no such element exists in a, then this function returns None.

 

1d)  (5 points) Write a function, sum_tri(a,x), that takes a list , a, as input and returns True if there exists indices i, j and k (where i and j and k are not necessarily distinct) such that a[i]+a[j]+a[k]=x. Otherwise it returns False.  For example, if a=[1, 5, 8, 2, 6, 55, 90] and x=103, then sum_tri(a, x) would return True since a[1]+a[2]+a[6]=5+8+90=103. If a=[-1, 1, 5, 8, 2, 6] and x=-3, sum_tri(a, x) would return True since a[0]+a[0]+a[0]=-1+ -1 + -1 = -3. If a=[-10,2] and x=-18,  sum_tri(a, x) would return True since a[0]+a[0]+a[1]=-10+-10+2=18. If  a=[1, 1, 5, 8, 2, 6] and x=1000 would return False, since there are not indices i, j and k such that  a[i]+a[j]+a[k]=1000.