Design and code a python solution for the problems. You must come up with your own algorithm and the honor code applies (no references). It is strongly recommended that you followthese problem...

Design and code a python solution for the problems. You must come up with your own algorithm and the honor code applies (no references).

It is strongly recommended that you followthese problem solvingsteps to help you find a correct and efficient algorithm, but you are not required to submit them.

1. Work out the steps to figure out some concrete examples.


2. Find and describe a pattern and attempt to generalize.


3. Might there be amore efficient approach? If so, return to step 1.


4. Investigate and explain special cases to see if the pattern holds up.


5. Come up with a solution and write a python function.


6. Might there be amore efficient approach? If so, return to step 1.

Problem 1[50 points] Design an algorithm that will efficiently find the largest difference between any two elements (not necessarily adjacent) in a list of numbers. Submit a python functionmax_difference(values)that returns the maximum difference as a number. **You may assume there will be at least 2 elements in the list.

Problem 2[50 points] Suppose you are given a list of N values, each of which is either a 0 or a 1, initially arranged in random value. You need tomodify the values in the list in situ(don't use another list)so that it consists of a sequence of 0s (possibly empty) followed by a sequence of 1s (also possibly empty), with the same number of both as were originally in the list. For example:


0111010010 -> 0000011111
1000111000 -> 0000001111
0000000000 -> 0000000000

This problem could be solved by any of the common sorting algorithms, but the special nature of the values in the list makes it possible to devise a particularly efficient solution. (Here, efficiency would refer partly to how many times you need to reset a value in the list, and partly to how many times you would have to change list position variables in your algorithm.) Design an efficient algorithm and submit it as a python functionsort_bivalued(values)that returns the sorted list.

Rules and Exceptions:

• Theonlyfunctions you may use arelenandrange
  


• Note that you may not use slicing (AKA colons in your indicies).


• We will not deduct for the use of str(), but you do not actually need it.


• Do not import libraries.

Submission Instructions

• Upload yourHW5.pyfile to WebCAT via your browser(not eclipse)


• There is a hard limit of 5 submissions to WebCAT.We suggest you run your own tests before submitting them. For example, you can call the function and print the return value:print(max_difference([1,2,3,4,5])
  


• But thenremovethese before submitting because they will use WebCAT server time.

Grading

• 35 Points: The correctness of your algorithm


• 15 Points: Efficiency of your algorithm

**Note: WebCAT doesnottest for your efficiency. Getting full points on WebCAT doesnotguarantee you will receive full points for efficiency.