Lab 3, CSC 202
For this lab, you will take some simple measurements of running time, for a few of the functions we have discussed in class.
For this lab, please use your existing definitions of the linked list.
The linked list should be your only data structure for this assignment; do not use Python Lists, Python Sets, or other data structures. (The goal is to understand the running time of these functions; if you’re using data structures whose performance we have not discussed, it’s going to be hard to reason about the running times that you’re observing.)
NOTE FOR THE FUTURE: Please follow the design recipe and use the template for each of these functions; this will help us in the analysis phase.
Develop the range function, that accepts an integer larger than zero and returns a linked list of the numbers from 0 up to n-1. (Either order is fine, as long as it’s consistent.
Develop the occurs function, that accepts an integer and a linked list and returns true exactly when the number appears in the list.
Develop the has_dup function, that accepts a linked list of numbers and returns true exactly when it contains one or more duplicates.
Using the insert function you developed earlier, develop the insertion-sort function that sorts elements by inserting them into the result of the recursive call.
ITEM FOR THE FUTURE: For each of the functions above, predict its worst-case performance, using the running-time analysis as we’ve performed it in class. Specifically, make a table for inputs of size 1, 2, 5, and 10, and show the number of function calls performed on an input of this size.
Using the time.perf_counter() built-in function in Python, test the time taken by the range function. Draw a graph of the results. Your graph should include at least ten different values, ranging from zero up to about a million. For each value, run the test four times and average the times taken to obtain the y value for that value’s point on the graph.
Do the same for occurs. In this case, do your tests on the worst case. Think about what the worst case for occurs is.
Do the same for has_dup. Again, do a worst-case analysis.
Do the same for insert. Again, do a worst-case analysis.
Do the same for insertion-sort. Again, do a worst-case analysis. Again, think about what the worst case for insertion sort is.
Finaly, combine all of your graphs into a single lab report. The lab report should separate each section clearly, include the code and the graph and your thinking about the worst case, and draw a conclusion about the running-time category of the function.
Add this lab report to your repository as a PDF.