Assignment 02 Given: Thursday, April 11, 2024 Due: Friday, April 19, 2024 CS209 - Data Structures and Mathematical Foundations Skidmore College Instructor: Michael Eckmann ====================================================================== 1. Save the Heap code (pqheap.py) that we wrote on 04/05 that is posted on class notes page. That is save pqheap.py to a local folder but name it heap.py . Add a comment line to the top of the file with your name in it. Get rid of the ItemAndPriority class. Edit the BinaryMaxHeap to instead of storing objects of ItemAndPriority, to instead just store a value (expected to be a number). Anything referencing item, val, etc should be removed or fixed. Any variables that refer to item or priority or iandp, should be renamed or removed as appropriate. The add method should be changed to just take in a value as a parameter (not an item and priority). Write code to test it out, by creating a heap and add the following values in this order: 9, 14, 11, 6, 20, 18, 19, 4, 5, 3, 21 Then loop and remove items, printing them out, until the heap is empty. Output should be: 21 20 19 18 14 11 9 6 5 4 3 ====================================================================== 2. Implement heap_sort in the BinaryMaxHeap class. Use the following def: def heap_sort(nums): # do not put self as first parameter (This should be a function, not an instance method) It should be able to be called like so: import heapcode mylist = [4,7,2,3,9,10,11,1,6,5,8] heapcode.BinaryMaxHeap.heap_sort(mylist) print(mylist) # should print out sorted from low to high Note well: The first thing you should do in heap_sort is create a BinaryMaxHeap as a local variable. Create that heap by adding all the values in the parameter list to this heap. At this point, you'll have a list that is the parameter currently unchanged and a heap stored as a list with the same values, but in heap order. have a variable that stores the index of the last place You should be able to loop and do: remove a value from the heap store that removed value in the last place in the parameter list decrement the last place in the list index That should result in the parameter list being sorted and the algorithm is over. ====================================================================== 3. Revisit the code you wrote in lab 8. Add heap_sort testing to compare against merge_sort and selection_sort. Save an image of a graph of the performance for different values of n for heap_sort. Save an image of a graph of merge_sort and heap_sort graphed on same plot. (leave out selection_sort and python's sort) ====================================================================== 4. Visit this link https://math.hws.edu/eck/js/sorting/xSortLab.html (choose InsertionSort from the dropdown menu) to remind yourself of what InsertionSort entails. Copy / paste this function into your code unchanged. def insertion_sort(nums): insertion_sort_portion(nums, 0, len(nums) - 1) def insertion_sort_portion(nums, start_i, end_i): # your code here You are required to write insertion_sort_portion that will sort the portion of the list given in the first parameter from the start index to the end index inclusive (which are the next 2 parameters). For example if we called it like this: alist = [9,3,6,2,5,8,4] # notice the alist portion from index 1 to 4 is 3,6,2,5 insertion_sort_portion(alist, 1, 4) # alist should become [9,2,3,5,6,8,4] after the call above # notice now that the alist portion from index 1 to 4 is 2,3,5,6 # the values in the other indices (before start_i=1 and after end_i=4) remain where they were Put these two functions insertion_sort and insertion_sort_portion in the same file, sorting.py from the lab 8, keeping the code for the other sorts in there. Test your code to make sure it works for any list and any portions of lists. ====================================================================== 5. Create several versions of quick_sort that you will experiment with. Two versions are from lab 10 (last element as pivor and random pivot). Make one other version of the 2 quicksort defs that take in a ins_sort_size as a parameter. Name these two quicksort_is and quicksortR_is. Make sure to change the names of the 2 defs, with the added parameter and change the 3 calls to quicksortR to quicksortR_is. If you copy/pasted the global variable SMALLSIZE get rid of it. change the two references to SMALLSIZE to ins_sort_size (which is the name of the parameter.) Call this quicksort_is with different values for the ins_sort_size: 10, 50, 80 5 a. Determine which value for that new parameter, if any, runs faster than the original quicksort (by graphing and interpreting the results) and for which values of n. From what you learn from that set of experiments, try to figure out an ideal value for size, less or equal to which you should call insertion_sort_portion. Experiment with other values for the length of the portion (under which, you do insertion_sort). ====================================================================== 6. Save 1 plot with curves for quick_sort, merge_sort, heap_sort for various n. Make sure you know which color line goes with which sort. Also save 1 plot with curves for quick_sort, quick_sort 10, quick_sort 50, and quick_sort 80 to see which work best in general. Also save those as individual graphs. Save 1 plot with the best performing quick_sort ZZZ where ZZZ is the value of the size you use to determine whether to call insertion sort on that portion. ========================= Submit to theSpring: heapcode.py (containing heap_sort function and the removal of item and priority stuff) sorting.py (with the various quicksorts and insertion_sort and insertion_sort_portion ) a pdf with graphs and descriptions of the graphs and what colored lines refer to which algorithms on plots that have multiple curves on them (from problems 3 and 6). In the pdf, report about what values you tried in problem 5 a. and which one you determined was fastest generally.