Quiz #8: Empirical Measurements, Unit Testing ICS-33 Winter 2020 When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed. You can download the q8helper project folder (available for Friday, on the Weekly Schedule link) in which to write/test/debug your code. Submit your completed q8solution modules (81, 82) and empirical.pdf online by Thursday, 11:30pm. I will post my solutions to EEE reachable via the Solutions link on Friday morning. 1a. (5 pts) Write a script that uses the Performance class to generate data that we can use to determine empirically the complexity class of the find_influencers function defined in the influence.py module (my solution to problem 1 of Programming Assignment #1). Call the evaluate and analyze functions on an appropriately constructed Performance class object for random graphs constructed from 100 nodes, 200 nodes, … up to 12,800 nodes (on graphs that have five times the number of edges as nodes) using a loop to double the number of nodes each time. Do 5 random timings for each size: each timing in Performance should run on a different random graph, and creating the random graph should not be timed. Hint: Write a script with a create_random function that stores a random graph (see the random_graph function in the q81solution.py module) of the correct size into a global name, then time the find_influencers function using that global name as an argument. If an exception is raised for any size, print an error message for that size but continue collecting data: this might happen for small sizes. I had about 30 lines in my module (including blank lines). See the file sample8.pdf (included in the download) for what your output should look like: of course, your times will depend on the speed of your computer (but the complexity class estimation will not). The process can take a few minutes. Do not time the execution of the random_graph function! 1b. (3 pts) Fill in part 1b of the empirical.doc document (included in the download) with the data that you collect (or use the data in sample8.pdf if you cannot get your code to produce the correct results) and draw a conclusion about the complexity class of the find_influencers function by seeing how much time it takes to run as the size (in number of nodes) of its input graph doubles. Then predict how long this function will take when running on an input graph of 1 million nodes. 2a. (5 pts) Write a script that uses the cProfile module to profile all the functions called when the find_influencers3 function (a faster version of find_influencers) is run on a random graph that has been constructed with 10,000 nodes and 50,000 edges. Generate the random graph first (do not include its generation in the profile information) and then call CProfile.run so that it runs find_influencers3 on that graph; also specify a second argument, which is the file to put the results in (and the file on which to call pstats.Stats) to print the results. For the first one, sort the results decreasing by ncalls (print at most the top 20); for the second one, sort the results decreasing by tottime (print at most the top 20). Hint: The notes show how to instruct the profiler put the profile information into a file and then show how to access that file and format the results it displays to the console; I had 23 lines in my module (including blank lines). It should take only a few seconds to profile this code. See the file sample8.pdf (included in the download) for what your output should look like: of course, your counts and times will depend on the speed of your computer and the random graph generated. 2b. (2 pts) Answer the questions in part 2b of the empirical.doc document (included in the download) with the data that you collect (or the data in sample8.pdf if you cannot get your code to produce the correct results). After editing empirical.doc for parts 1b and 2b, convert it into a .pdf document and submit the document in that format on checkmate. You can use the lab machines to do the conversion.
