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

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

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')`?

You should use Apollo to submit the following files:

• your `ps4pr1.py` file containing your answers for Problem 1
• your `ps4pr2.txt` file containing your code for Problem 3

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:

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`.