Due: before class on Thursday, April 29, 2021
Before You Begin
Start by reading the exam procedures page. It covers important policies that are in place during an exam week.
Part 1: Reflection Questions
This part of the exam includes two essay questions. You will need to download the following text file, open it in your text editor of choice, type your answers to each of the questions into the file, save it, and upload it with your Exam 3 submission on codePost.
Part 2: Programming Problems
This part of the exam includes several programming problems.
Problem 1: Whatzitdo?
Sometimes programmers write functions that are difficult to read. Let’s take a look at the following function.
def apple(orange, banana): """Given an orange and a banana, will return a pear""" pear, kiwi = , 0 while kiwi < len(orange) or kiwi < len(banana): mango = pear +  if kiwi < len(orange) and len(mango) > len(pear): pear.append(orange[kiwi]) if kiwi < len(banana) or False: pear.append(banana[kiwi]) kiwi = kiwi * 1 + (17 - 4*4) return pear
a. Determine what the function is doing and give it a more appropriate name.
b. The variable names aren’t very helpful. Give them names that are more descriptive of what they are.
c. Clean up the function by removing any unnecessary code that does not serve a purpose.
d. Write a more appropriate docstring for the function and include the following sections
- A short one-line purpose statement
- A Parameters section listing the types of the parameters
- A Returns section briefly summarizing the return value and its type
- A Preconditions section if there are more restrictions on the input other than their type
- A Postconditions section that describes, in more detail, the exact relationship between the output and the inputs
e. Place the updated function from parts a-c above, along with its documentation in a file named
Problem 2: Binary Search
Recall that binary search is an algorithm for quickly finding an element in a list, given that the list is sorted. We implemented it as a function named
binary_search(val, sorted_lst) that returns the index of
val if it appears in
lst and return
In this problem, your task is to implement a variant of binary search that returns the index of the largest element less than
-1 if there is no such element.
Here is a docstring for the function:
def binary_search_lt(val, sorted_lst): """Finds the index of the largest element less than val in sorted_lst or -1 if no such element exists Parameters: val: an object sorted_lst: a list Returns: index: an int Preconditions: * val < x is defined for each x in sorted_lst * sorted_lst is sorted using < (ascending order) Postconditions: if sorted_lst contains an element that is < val then sorted_lst[index] = the largest such element if sorted_lst does not contain an element < val then index = -1 """ # TODO: Your solution goes here
Here are a few example executions demonstrating how
binary_search_lt should work:
# indices 0 1 2 3 4 >>> lst = [100, 123, 407, 502, 731] >>> binary_search_lt(502, lst) 2 >>> binary_search_lt(1000, lst) 4 >>> binary_search_lt(100, lst) -1
In the last example above, notice that
100 is in the list but there is no element less than it, so the function returns -1.
Another case you need to watch out for is this:
>>> binary_search_lt(200, [100, 200, 200, 200, 200, 200]) 0
When you are finished, save your code in a file named
Problem 3: String Join
Recall that Python has a built-in method for joining a list of strings together:
>>> delimiter = "," >>> list_of_strings = ["abc", "def", "ghi"] >>> delimiter.join(list_of_strings) 'abc,def,ghi'
In this problem, you implement the above procedure but as a function named
The key constraint in this problem is that your implementation must be recursive. To help you with the recursion, you may find it easier to fill in the blanks below:
def string_join(delimiter, list_of_strings): """Joins the strings together with the delimiter Parameters: delimiter, a string list_of_strings, a list of strings Returns: joined_string, a string Postconditions: * if list_of_strings = [s1, s2, s3, ..., sn], then joined_string = s1 + delimiter + ... + sn """ if _________: return _________ else: return _________ + _________ + string_join(_________)