Exam 3
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 + [5]
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 mystery_solved.py
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 -1 otherwise.
In this problem, your task is to implement a variant of binary search that returns the index of the largest element less than val or -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 binary_search.py.
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 string_join(delimiter, list_of_strings).
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(_________)