15110 Summer 2015

Lab 4

Goals

The purpose of this lab is to get you to work with iteration as a tool for finding a value with a certain property in a sequence of values, and to learn to measure the time consumed by executing some Python code. When you are done, you should be able to

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)
Search a list of strings for a substring with the string.find(sub_string) method.
Use the list.append(element) method.

Deliverables

search_timing.py
timings.txt
find_largest_even.py
is_all_odd.py
substring_list_search.py

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

Part 1 - Search and Timing

1.1 Class Activity

Note: The search and timer functions below should be put in the file search_timing.py

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(integer_list, key):
  for i in range(0, len(integer_list)):
    if integer_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

1.2 Student Activity

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.

NOTE: Put the assignment that creates big_list in your python file outside the scope of a function. Do NOT assign to big_list in the timer or search functions because it will invalidate the timing and search results.
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.

Part 2 - Searching for Numerical Properties

2.1 Class Activity

Explanation of find_largest_even(integer_list) in find_largest_even.py. This function should take a list and return the largest even number in that list. If there are no even numbers in the list, then the function should return None. You may assume that all numbers in the list will be positive .
Explanation and demonstration of list.append(element)
Explanation and demonstration of string.find(sub_string)

2.2 Student Activity

In is_all_odd.py, write a Python function is_all_odd(integer_list) 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(integer_list, key) given above?)
Example:
```
>>> 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
```

Part 3 - Searching with Strings

3.1 Student Activity

In the file substring_list_search.py, write the function string_search(string_list, substring) that takes a list of strings and a substring, and returns another list of strings that all have the substring in it. If no element of string_list contains the substring then return an empty list


         Example Output:
       
         >>>listA = ["cat", "bat", "car", "dog", "spat"]
         >>>string_search(listA, "a")
         [ 'cat', 'bat', 'car', 'spat' ]
         >>>string_search(listA, "at")
         [ 'cat', 'bat', 'spat' ]
         >>>string_search(listA, "l")
         []