Task 1: Merge Sort Part A: Merge Write a function merge (1st1, 1st2) that takes two...

Transcribed Image Text:

Task 1: Merge Sort Part A: Merge Write a function merge (1st1, 1st2) that takes two sorted lists as arguments, and returns the elements of both lists, merged. This function must have a complexity of O(n + m) where n list the length of 1st1 and m is the length of 1st2. Part B: Merge Sort Implement the iterative version of merge_sort (1st), where 1st is an unsorted list, you should also return the sorted list. Your code should call merge (1st1, 1st2) from Part A. Part C: Analysis of Sorting Algorithms Ensure your Merge Sort, Insertion Sort and Selection Sort functions from this week and last week are fully functional before commencing this task. Over the past couple of weeks you have been introduced to several different sorting algorithms. We will analyse the run times of these algorithms and compare them against each other to recognise the different computational complexities they present. You should first: Copy and paste your insertion sort and selection sort functions from last week into this week's workshop. Your task is to implement a function sort_analysis that takes two arguments, func, a function as an pa- rameter representing a sorting algorithm and n, representing the number of elements in a list to be sorted. sort_analysis should return a dictionary of run times with string representations of 'non-decreasing', 'decreas- ing' and 'random' as keys and their respective run times as values. For Example: >>> from workshop07 import merge_sort, merge >>> sort_analysis (merge-sort, 1000) # Merge Sort with 1000 elements {'non-decreasing': 0.0025189999999923884, 'decreasing': 0.002601599999991322, 'random': 0.003887900000009381} Note: Your values do not have to match the example values as they are dependent on your computer's clock. Inside sort_analysis you are required to: Construct three lists to test your sorting algorithms. You should have one list with non-decreasing, one for decreasing and one for randomised numbers ranging from 1 to n inclusively. . Consider how you would randomise your random list and ensure you are using the same random list across all of your algorithms. Have a look into Python's random module about shuffling and creating a seed. https://docs.python.org/3/library/random.html. Extract the system timer to get the run times of the algorithm, Hint: There are a couple of options to implement this, but one way is to extract the start and end times of a function. Have a look at Python's timeit and/or time modules to figure this out. https://docs.python.org/3.8/library/timeit.html. Once complete, test the performance of each sorting algorithms against each other by using the sort_analysis function in the Python shell and manipulating the input size. Then write a paragraph inside the docstring about any of the observations you have made. Can you determine the time-complexities of each sorting algorithm given different lists (i.e., non-decreasing, decreasing, random). Task 2: Closing down a post office Assume you are an executive of a postal service company and, unfortunately, due to shrinking demand in delivering physical letters, you have close down one of your post offices. To reduce the spatial coverage of your letter distribution network as little as possible, you would like to merge two offices that are closest to each other. Here, you consider as distance the usual Euclidean distance. That is, if (x1, yl) are the coordinates of one post office and (x2, y2) are the coordinates of another, then their distance is given as: dist ((x1, y), (x2, y2)) = (x1 x2) + (y1 Y2) . (1) The partial specification of a function offices_to_merge (points) that you can use to determine which post offices to merge is as follows: Input: list of 2d coordinates of post offices: points=[(x1, y1), (x2, y2)... (xn, yn)] with n>1. Output: a pair of indices i, j such that. For example: = >>> points [(350, 150), (500, 250), (150, 150), (50, 400), (200,100)] >>> offices_to_merge (points) (2, 4) 1. Write a Python function with a completed output specification in the documentation. 2. Implement and algorithm that correctly solves the problem given in the specification. 3. Make sure that your algorithm does not compute the distances between identical points more than once. Explain how you have achieved this in a separate paragraph in your function documentation. 4. What is the computational complexity of your algorithm? Give an analysis in another paragraph of your function documentation. 5. Optional: Annotate an invariant in your function that shows that the correct output is computed. Task 1: Merge Sort Part A: Merge Write a function merge (1st1, 1st2) that takes two sorted lists as arguments, and returns the elements of both lists, merged. This function must have a complexity of O(n + m) where n list the length of 1st1 and m is the length of 1st2. Part B: Merge Sort Implement the iterative version of merge_sort (1st), where 1st is an unsorted list, you should also return the sorted list. Your code should call merge (1st1, 1st2) from Part A. Part C: Analysis of Sorting Algorithms Ensure your Merge Sort, Insertion Sort and Selection Sort functions from this week and last week are fully functional before commencing this task. Over the past couple of weeks you have been introduced to several different sorting algorithms. We will analyse the run times of these algorithms and compare them against each other to recognise the different computational complexities they present. You should first: Copy and paste your insertion sort and selection sort functions from last week into this week's workshop. Your task is to implement a function sort_analysis that takes two arguments, func, a function as an pa- rameter representing a sorting algorithm and n, representing the number of elements in a list to be sorted. sort_analysis should return a dictionary of run times with string representations of 'non-decreasing', 'decreas- ing' and 'random' as keys and their respective run times as values. For Example: >>> from workshop07 import merge_sort, merge >>> sort_analysis (merge-sort, 1000) # Merge Sort with 1000 elements {'non-decreasing': 0.0025189999999923884, 'decreasing': 0.002601599999991322, 'random': 0.003887900000009381} Note: Your values do not have to match the example values as they are dependent on your computer's clock. Inside sort_analysis you are required to: Construct three lists to test your sorting algorithms. You should have one list with non-decreasing, one for decreasing and one for randomised numbers ranging from 1 to n inclusively. . Consider how you would randomise your random list and ensure you are using the same random list across all of your algorithms. Have a look into Python's random module about shuffling and creating a seed. https://docs.python.org/3/library/random.html. Extract the system timer to get the run times of the algorithm, Hint: There are a couple of options to implement this, but one way is to extract the start and end times of a function. Have a look at Python's timeit and/or time modules to figure this out. https://docs.python.org/3.8/library/timeit.html. Once complete, test the performance of each sorting algorithms against each other by using the sort_analysis function in the Python shell and manipulating the input size. Then write a paragraph inside the docstring about any of the observations you have made. Can you determine the time-complexities of each sorting algorithm given different lists (i.e., non-decreasing, decreasing, random). Task 2: Closing down a post office Assume you are an executive of a postal service company and, unfortunately, due to shrinking demand in delivering physical letters, you have close down one of your post offices. To reduce the spatial coverage of your letter distribution network as little as possible, you would like to merge two offices that are closest to each other. Here, you consider as distance the usual Euclidean distance. That is, if (x1, yl) are the coordinates of one post office and (x2, y2) are the coordinates of another, then their distance is given as: dist ((x1, y), (x2, y2)) = (x1 x2) + (y1 Y2) . (1) The partial specification of a function offices_to_merge (points) that you can use to determine which post offices to merge is as follows: Input: list of 2d coordinates of post offices: points=[(x1, y1), (x2, y2)... (xn, yn)] with n>1. Output: a pair of indices i, j such that. For example: = >>> points [(350, 150), (500, 250), (150, 150), (50, 400), (200,100)] >>> offices_to_merge (points) (2, 4) 1. Write a Python function with a completed output specification in the documentation. 2. Implement and algorithm that correctly solves the problem given in the specification. 3. Make sure that your algorithm does not compute the distances between identical points more than once. Explain how you have achieved this in a separate paragraph in your function documentation. 4. What is the computational complexity of your algorithm? Give an analysis in another paragraph of your function documentation. 5. Optional: Annotate an invariant in your function that shows that the correct output is computed.