15110 SUMMER SESSION TWO 2014

Lab 4 - Wednesday, July 9

Goals

• Create a list from a range expression (e.g., list(range(10)))
• Measure the time it takes to execute some Python code
• Analyze a simple relationship between the input to a function and the length of time the function takes to execute
• Use iteration to search a list for an element that has some property (e.g., it is even, or it is odd, or it is equal to some given key)
• Use a while loop to search a "gapped" list. That is, search every nth element of a list (for example, every other element, every third element, every fourth element, etc.)

Deliverables

1. timings.txt
2. is_all_odd.py
3. gap_search.py

Place these files in a lab4 folder. Before leaving lab, zip up the lab4 folder and hand in the zip file.

CA Demonstration (as necessary)

• Creating a list containing a range of elements

  list(range(0, 10))
  (not needed today, but note that [elem] * N replicates a single value)
  

• Linear search function to find a list element equal to the key. Note that the same structure can be used to find a list element having some other property (e.g., is even, odd, positive, negative, etc.).

  def search(list, key):
    for i in range(0, len(list)):
      if list[i] == key:
        return i
    return None
  

• Timing linear search for 700 in list(range(100,1000000)) by using time()

  import time
  
  def timer():
    start = time.time()
    """
      insert the code to be timed here, e.g. search(list, key)
      Make sure to remove the quote marks!
    """
    end = time.time()
    return end - start
  

Activities

1. Create a list whose elements contain the integers from 100,000 through 300,000, inclusive (be careful! what should the range be?) and set the variable big_list to contain that list.

   1. Time how long it takes the search function above to find each of the following in big_list:

      1. element at front (100000)
      2. element in middle (200000)
      3. element at back (300000)
      4. element not in the list (3)

      How long does each take?

   2. If you repeat the same searches, does it take exactly the same amount of time? Why do you think this is?

   3. How would you describe the relationship between the position of the item you are searching for in the list and how long it takes to find that item? (Is the search time independent of the position, or is there some mathematical relationship between the two quantities?)

   Write your answers in a text file called timings.txt.

2. In is_all_odd.py, write a Python function is_all_odd(numlist) that takes an integer list as an argument and returns True if all the elements in the list are odd numbers and False otherwise. (Hint: how is this different from the function search(list, key) given above?)

   Example:

   > python3 -i is_all_odd.py
   >>> 4 % 2
   0
   >>> 5 % 2
   1
   >>> is_all_odd([1, 2, 8, 12, 99])
   False
   >>> is_all_odd([1, 3, 5, 7])
   True
   >>> is_all_odd([])
   True
   

3. In this exercise, you will iterate over a "gapped" list (i.e., by examining every nth element). In gap_search.py, write a Python function gap_search(list, key, gap). This function works like search(list, key) above, but with two important differences:

   • You will use a while loop instead of a for loop; and
   • The search must start with the first list element, then skip over the number of elements given by gap, and so on. For example, if we have the following list and a gap value of 2,

     	  [ 't', 'u', 'v', 'w', 'x', 'y', 'z' ]
     	

     the search must examine 't', 'v', 'x', and 'z'. But if the gap value is 3 the search must examine 't', 'w', and 'z'; if the gap is 4 it must examine 't' and 'x'; and if the gap is greater than 6 only 't' must be examined.

   Use the following algorithm:

   1. The parameters are a list, a key, and a gap.
   2. Set i to 0
   3. While i is less than the length of the list:
      1. If the element at index i is equal to the key, return i.
      2. Otherwise, increase i by the gap amount.
   4. (The loop is done at this point, which means the key was not found.) Return None.

   Example:

   > python3 -i gap_search.py
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 1)
   4
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 2)
   4
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 3)
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 4)
   4
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 5)
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 6)
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'x', 7)
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'a', 1)
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'z', 1)
   6
   >>> gap_search(['t', 'u', 'v', 'w', 'x', 'y', 'z'], 'z', 3)
   6
   >>> 
   

4. Suppose you can be sure the list input to gap_search is always sorted in increasing order. Modify the code to return as soon as it detects that the key cannot be in the gapped list because it has encountered an element greater than the key.