Lab 2: Runtime Review
Background
Very early on in Tim’s talking career, Tim had developed a small habit of rambling during some of the talks he was giving. In the best case scenarios, he was able to get his point across in a few sentences. However, in the worst case scenarios, the audience would begin to lose sight of the points he was trying to make, leading to an inefficient speech. In the end, Tim was able to mitigate this issue and he has grown into a fan-favorite speaker all over the world. How did he do it?
By analyzing runtime. In this lab, you will be able to calculate and see the differences in runtimes of efficient vs. inefficient functions through plotted graphs, similar to how Tim was able to use his knowledge of runtime analysis to help him become a renowned speaker.
What is Runtime?
Runtime (or Execution Time) is the time it takes a computer to execute a program. Runtime is an important metric that is often used to determine the efficiency of a function. Each program has a best-case runtime and a worst-case runtime. The reason for this is because the runtime of a program is not static. For example, the size of a datafile may affect the iterations a program must perform, which makes the runtime depend on the size of the file. Worst-case runtime is the most commonly used metric because we must always account for the worst-case scenarios (i.e. a data file with hundreds of inputs).
Set-Up
The goal of this assignment is to be able to see the differences in runtimes of efficient vs. inefficient functions, through plotted graphs. Most of the program is already written and your task will be to fill in two of the methods.
This stencil code contains 7 functions. The generate_graphs function will use its helpers graph and time to plot graphs which show the runtimes of distinct1 and distinct2 on different inputs. Those inputs will come from the best_case_input and worst_case_input functions. Although distinct1 and distinct2 have the same functionality, distinct2 should be faster in the worst-case scenario. You will implement worst_case_input and finish the stencil of generate_graphs.
When the input to distinct1 and distinct2 is the output from best_case_input, they should run with their best (fastest) possible runtimes. When the input to distinct1 and distinct2 is the output from worst_case_input, they should run with their worst (slowest) possible runtimes.
When you implement worst_case_input, start by looking at distinct1 and distinct2. In what cases do distinct1 and distinct2 have the best possible runtime? In what cases do distinct1 and distinct2 have the worst possible runtime? Construct an input to distinct1 and distinct2 which would give them the worst case runtime. That value should be returned by worst_case_input.
Create a new folder and open it in VSCode. You can name it runtime_lab. Then download the stencil code below and save it in this directory as runtime_lab.py. Alternatively, copy the stencil code, create a runtime_lab.py file in the directory, and paste the stencil code into the file.
IMPORTANT: Since this program uses matplotlib in order to be able to create the graphs and save them to your directory, you will need to head over to the Terminal and run pip3 install matplotlib.
Task
- Complete the worst_case_input() method by looking at the hints outlined in the method’s header comment.
- Complete the generate_graphs() method, which is also outlined in the stencil code. This method is in charge of calling the helper methods, respectively, in order to generate the graphs.
Running File
Use a Terminal to navigate to your runtime_lab directory and call python3 runtime_lab.py to run the program.
After running the program, you should see four images in your directory (best1.png, best2.png, worst1.png, worst2.png). Sometimes you must go to your folder/directory in Finder in order to see the images. You can also open these images directly in VSCode. These images will show how the runtime increases as the size of the input also increases.
CHECKPOINT:
Once you have completed both methods and the graph images are saved in your directory, notify your TA.