Exam 3

3 minute read

Type: Individual Assignment
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):
        if kiwi < len(banana) or False:
        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

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

        val: an object
        sorted_lst: a list

        index: an int

        * val < x is defined for each x in sorted_lst
        * sorted_lst is sorted using < (ascending order)

        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)
>>> binary_search_lt(1000, lst)
>>> binary_search_lt(100, lst)

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])

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)

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

        delimiter, a string
        list_of_strings, a list of strings

        joined_string, a string

        * if list_of_strings = [s1, s2, s3, ..., sn], then
            joined_string = s1 + delimiter + ... + sn
    if _________:
        return _________
        return _________ + _________ + string_join(_________)