Compsci 101/6, Timing FUN, March 27

Name____________________   net-id _________       

Name____________________   net-id _________       

Name____________________   net-id _________

ModeTimings

The questions here are about the code in ModeTimings.py in which there are four functions given to return the most frequenly occurring value in a list of integers. First you'll be asked some questions about the functions, then about how efficient they are.

In mode_compA what's the value assigned to mindex?
1. The largest value in the list occs (an integer).
2. The index in occs at which the largest value of occs occurs (an integer).
3. The number of times that m occurs in occs (an integer).
In mode_compA which is the most relevant as to why the function works correctly.
1. The number of occurrences of nums[i] is the value stored in occs[i], for 0 <= i < len(nums).
2. The same number may occur multiple times in nums, but the count of this number only occurs once in occs.
3. The function max works on integer values, string values, and list values --- i.e., it would return the largest list in a list of lists.
What's the difference between mode_compB and mode_compC (in as few words as possible).

In mode_compD why is the value mn subtracted from n in the loop and added to mindex in the return statement?

Using mn helps ensure that the code will work with lists of string values as well as lists of int values.
This helps ensure that the lowest value in nums has its count stored in counts[0], i.e., the use of nm maps the lowest value in nums to zero and vice-versa.
The primary purpose of mn is to ensure symmetry with the use of mx.

Several runs of the program are shown below (from ola's macbook pro):

Run with n = 10,000 Run with n = 20,000 Run with n = 30,000

The function mode_compD has these timings for larger values of n (the number of elements in the list):

n time
100,000 0.03
200,000 0.07
300,000 0.10
400,000 0.13
500,000 0.16

Predict and justify the time for mode_compD and mode_compB for a list with one million elements.

n	time
100,000	0.03
200,000	0.07
300,000	0.10
400,000	0.13
500,000	0.16

SetTimings

These questions are for the code in SetTimings.py

What does the function create_word do?
1. Creates a string by shuffling the letters in "etaoins", but returns a list.
2. Creates a string by shuffling the letters in "etaoins", and returns the string.
3. Returns the same string every time it is called.
What is the purpose of the slice operator used in diffB?
1. It ensures that the .count(word) is applied to the part of words before the occurrence of word.
2. It ensures that the .count(word) is applied to the part of words after the occurrence of word.
3. It creates a copy of words so that words is not modified by the function diffB.
A run of the program is shown for different sized lists. Predict the time it will take for both diffA and diffB to run on a 20,000 element list, justify your answer.

SearchTiming

These questions are for the code in SearchTimings.py

Why is the function linear_search named that?
1. The code has one loop.
2. The code does a linear search using the if i in nums check to (possibly) examine all values of nums
3. The code uses single-letter variable names.
The function bisect.bisect_left returns the least or left-most index where the parameter being searched for does occur, if it occurs at all. If the value is len(nums) the value cannot occur in the list nums. What's the purpose of the compound if statement in binary_search?
1. It checks whether the value i is not found in list nums.
2. It checks for whether the value i occurs, but ensures that any index of list nums is valid, i.e., will not generate an index-out-of-bounds exception.
3. The check for index != len(nums) is un-needed, the code would work without the check.
A run is shown below. How long will it take the linear_search function to search for 20,000 elements in a list of 40,000 elements? Justify.