CS 111
Summer 2 2018

Problem Set 4

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

Make sure to submit your work on Apollo, following the procedures found at the end of the assignment.


due by 9:00 p.m. on Tuesday, July 10, 2018

Problem 1: List comprehensions

50 points; individual-only

Begin by downloading the file ps4pr1.py and opening it in IDLE.

  1. LC puzzles! You will see that the file includes several incomplete list comprehensions. Complete them by filling in the blanks to produce the results specified below.

    1. Complete the following list comprehension

      lc1 = [            for x in range(5)]
      

      so that it produces the list [0, 2, 4, 6, 8].

    2. Complete the list comprehension shown below

      words = ['hello', 'world', 'how', 'goes', 'it?']
      lc2 = [            for w in words]
      

      so that it produces the list ['e', 'o', 'o', 'o', 't'].

    3. Complete the following list comprehension

      lc3 = [            for word in ['hello', 'bye', 'no']]
      

      so that it produces the list ['olleholleh', 'eybeyb', 'onon']. Hint: Use skip-slicing plus one other operator.

    4. Complete the following list comprehension

      lc4 = [            for x in range(1, 10) if               ]
      

      so that it produces the list [4, 16, 36, 64]. Note that you need to fill in two blanks for this one: the expression before the for, and the expression after the if.

    5. Complete the following list comprehension

      lc5 = [            for c in 'bu be you']
      

      so that it produces the list [True, True, False, True, False, False, False, False, True]. Note that the expression 'bu be you' is a string, not a list.

    Test your list comprehensions by running ps4pr1.py and checking the correct values that are printed.

The next two parts of the problem involve writing functions. You should continue to follow the guidelines from problem 3, but you should use list comprehensions instead of recursion.

  1. Write a function called powers_of(base, count) that takes as inputs a number base and a positive integer count, and that uses a list comprehension to construct and return a list containing the first count powers of base, beginning with the 0th power. For example:

    >>> powers_of(2, 5)        
    [1, 2, 4, 8, 16]
    

    Don’t forget to include a docstring!

  2. Write a function called ends_with(suffix, wordlist) that takes as inputs a string suffix and a list of strings wordlist, and that uses a list comprehension to construct and return a list consisting of all words from wordlist that end with suffix. For example:

    >>> ends_with('ly', ['only', 'really', 'funny', 'lyrics'])
    ['only', 'really']
    >>> ends_with('on', ['only', 'recursion', 'on', 'the', 'brain'])
    ['recursion', 'on']       
    >>> cities = ['Boston', 'Chicago', 'Washington', 'Houston']
    >>> ends_with('ton', cities)
    ['Boston', 'Washington', 'Houston']
    >>> ends_with('ston', cities)
    ['Boston', 'Houston']
    >>> ends_with('ford', cities)
    []
    

    Hints:

    • Your list comprehension will need an if clause.

    • In Problem Set 2, Problem 5, you wrote a function called ends_with that determined if a single word ended with a specified suffix. You will need to use similar logic here as part of the if clause of your list comprehension.

    • Make sure that you only include words that end with the specified prefix. For instance, in the first example above, the string 'lyrics' is not included in the return value, because the string 'ly' is at the start of 'lyrics', rather than at the end. As a result, you won’t be able to use the in operator to test for the presence of the suffix in a word.

Don’t forget to test your functions using the approaches mentioned at the start of Problem 2. In particular, you are encouraged to add test calls to the bottom of the file, although doing so is not required for this problem.


Problem 2: Tracing list comprehensions and recursion

50 points; individual-only

Put your answers for this problem in a plain-text file named ps4pr2.txt.

  1. Consider the following Python program:

    def mystery1(x):
        lc = [2*y - 1 for y in range(x)]
        return sum(lc)
    
    x = 5
    y = 4
    y = mystery1(y)
    print(x, y)
    x = mystery1(x)
    print(x, y)
    

    Trace the execution of this program. Your answer should include:

    • a table for the variables in the global scope that illustrates how their values change over time. You can begin it as follows:

        x  |  y
      -----------
        5  |  4
      
    • one or more separate tables that illustrate the changes in the local variables that belong to the function; you can either use a different table for each function call, or one table for the function as a whole.

      Your table(s) for the function should have the following columns:

        x  |  y  |  lc
      ------------------
           |     |
      

      In the column for lc, you should show the how the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

      We included a similar table for a method called myst as part of the solution to a clicker question in the lecture notes on Recursive Design.

    • a separate section that specifies the output of the program (i.e., the values that are printed).

  2. Consider the following Python function:

    def mystery2(vals):
        """ takes a list of numbers and does something with them """
        scored_vals = [[x**2, x] for x in vals]
        best_pair = max(scored_vals) 
        return best_pair[1]
    

    Trace the execution of the following call to this function.

    mystery2([-2, 1, -5, 4])
    

    Your answer should include:

    1. a table that illustrates the changes in the values of x and scored_vals as the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

    2. the value assigned to the variable bestpair

    3. the return value of the function call

  3. Briefly describe what the function mystery2 (from the previous part of this problem) does in general. In other words, for an arbitrary list of numbers vals, what will mystery2 return?

  4. Consider the following recursive function:

    def mystery4(s):
        """ takes a string s and does something with it """
        if len(s) <= 1:
            return ''      # the empty string, with nothing between the quotes
        else:
            result_rest = mystery4(s[1:])
            if s[0] == s[-1]:
                return result_rest
            else:
                return result_rest + s[0]
    

    Trace the execution of the following call to this function.

    mystery4('banana')
    

    Your answer should illustrate the sequence of function calls that are made – from the initial call to the base case. Include a separate section for each call, taking an approach that is similar to the one we have often used in lecture. Begin each section with the call itself (e.g., `mystery4(‘banana’)). Then include a line that explicitly states the value assigned to the parameter. Next, if the call is a base case, you can just show the value that is returned. If the call is a recursive case, you should show the recursive call and its result, along with the value that is ultimately returned. We also encourage you to use indenting to emphasize the way in which one call occurs in the context of prior calls.

    For example, recall the num_vowels function from lecture. When tracing the call num_vowels('ate'), you would start by getting all the way down to the base case:

    num_vowels('ate')
    -----------------
        s = 'ate'
        num_in_rest = num_vowels('te')
    
        num_vowels('te')
        ----------------
            s = 'te'
            num_in_rest = num_vowels('e')
    
            num_vowels('e')
            ---------------
                s = 'e'
                num_in_rest = num_vowels('')
    
                num_vowels('')
                --------------
                    s = ''
                    return 0
    

    Note that we have left blank lines between sections. Then, once you have reached the base case, you can go back and add in both the results of the recursive calls and the values returned by the earlier calls, using the space provided by the blank lines:

    num_vowels('ate')
    -----------------
        s = 'ate'
        num_in_rest = num_vowels('te') = 1
        return 1 + 1 = 2
    
        num_vowels('te')
        ----------------
            s = 'te'
            num_in_rest = num_vowels('e') = 1
            return 0 + 1 = 1
    
            num_vowels('e')
            ---------------
                s = 'e'
                num_in_rest = num_vowels('') = 0
                return 1 + 0 = 1
    
                num_vowels('')
                --------------
                    s = ''
                    return 0
    

    Take this same approach when tracing mystery4('banana').

  5. What is the final result of the call mystery4('banana')?


Submitting Your Work

You should use Apollo to submit the following files:

Warnings

  • Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

  • If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

  • If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

Here are the steps:

  1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
  2. Find the appropriate problem set section on the main page and click “Upload files”.
  3. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
  4. Click the “Upload” button at the bottom of the page.
  5. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
  6. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.

Warning

Apollo will automatically close submissions for a given file when its final deadline has passed. We will not accept any file after Apollo has disabled its upload form, so please check your submission carefully following the instructions above.

Note: If you encounter problems with Apollo, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs111-staff@cs.bu.edu.