Homework 08 METU CENG310

Homework 08
METU CENG310 
Data Structures and Algorithms with Python

1 Heap Performance Experiment
In this assignment, you will be conducting a simple experiment to show that removing minimum operations,
in average, take time proportional to the binary logarithm of the input size. In doing so, you will
• Create a HeapPriorityQueue class by making use of Code Fragments 9.1, 9.4, and 9.5 from the textbook,
• Develop a function called test_heap that takes a single argument, n, which is the number of (key, value)
pairs to be inserted to an instance of HeapPriorityQueue class, and then perform remove minimum
operation on the heap object with each of the n items, and return the average and worst remove
minimum times, and
• Develop a report_results function that creates and saves a line chart where x-axis is n and the y-axis
is the average and worst remove minimum times.
1.1 The test_heap Function
The test_heap function should work as follows. Initially, it should create an instance of HeapPriorityQueue
class (Let’s call it _heap). And then n distinct random integer numbers should be drawn from the range
[0, 103n], and inserted to _heap object with the add operation (you can add the same number as key and
value). At this moment, your heap should have n distinct numbers.
After filling the heap, you should perform remove minimum (remove_min) operation until the heap is empty.
You will need to measure the time elapsed between the beginning and the end of the remove_min operation.
And those elapsed time values should be saved in a temporary list called measures. Elapsed times for each
remove_min operations can take time in the magnitude of nanoseconds. So you may want to save the time
value in nanoseconds unit rather than seconds for the sake of simplicity.
Finally, test_heap function should return the average and maximum of values in measures as a tuple.
1.2 The report_results Function
report_results is a function that does not take a parameter, however, reports the results of a series of tests
that you will perform with test_heap. The test_heap function will be called iteratively for the range of range
(10000:1000001:10000) (i.e., there will be 100 iterations). After each iteration, a tuple with the following
values will be appended to a list object: (n, avg_time, max_time). Let’s call that list object results_list.
After having the results from this simple experiment, you will plot these results as a line chart by making use of
the library module matplotlib. You are expected to learn how you can plot with plot function of matplotlib
(https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.plot.html).
plot function accepts one-dimensional number arrays as parameters. You can convert the results_list to a
pandas data frame and then work with value vectors as follows.
1 # import pandas to use pandas DataFrame
2 import pandas as pd
3 # create DataFrame using data
4 df = pd . DataFrame ( results_list , columns =[ ’n’, ’avg ’, ’max ’])
5
6 # Then you can use df[ ’n ’] , df[ ’avg ’] , and df[ ’max ’] as value vectors .
7 # matplotlib ’s plot function accepts value vectors , as you will find
out.
The outcome of the execution of report_results function should be a single PDF file having a single line
chart having two lines for average and maximum values plotted against n.
1
1.3 The Deliverable
Your deliverable should be a Python module named as hw8.py that includes HeapPriorityQueue class, and
test_heap and report_results functions. You can also send your own PDF result for control purposes.
2 Instructions
A Homework-08 page will be generated soon after the start date of this homework. All deliveries should
be done over ODTUClass. Please also be aware of the late penalties (Please check the Announcements –
Homework and Assignment Policy in ODTUClass if you have not already done so.). Should you have any
questions pertaining to homework tasks, please ask them in advance (not on the due date) for your own
convenience.
2