Old version
This is the CS 111 site as it appeared on December 20, 2022.
If you haven’t already created a folder named cs111 for your
work in this course, follow these
instructions to do so.
Then create a subfolder called lab4 within your cs111 folder,
and put all of the files for this lab in that folder.
Access the template that we have created by clicking on this link and signing into your Google account as needed.
When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.
Select File->Rename, and change the name of the file to
lab4_tasks12.
Put your work for Tasks 1 and 2 in this file.
Consider the following function, which uses a list comprehension to process a list of numbers:
def lc_mystery1(vals): """ takes a list of numbers vals and does something with them! """ lc = [x**2 for x in vals] return sum(lc)
Trace the execution of the following call to this function
lc_mystery([2, 3, 5])
In the Task 1 section of lab2_tasks12, we have given you a table
that you should complete to illustrate the execution of the list
comprehension. You may not need all of the rows in the table.
More specifically, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension. For example, if we were tracing the list comprehension
lc = [2*x for x in [3, 5, 7]]
the table would look like this:
x | lc ------------ 3 | [6, 5 | [6, 10, 7 | [6, 10, 14]
What is the return value of the call that you just traced?
What does this function do in general?
Now consider the following function, which uses the list-of-lists technique that we discussed in lecture:
def lc_mystery2(vals): """ takes a list of numbers vals and does something with them! """ lc = [[x**2, x] for x in vals] bestpair = max(lc) return bestpair[1]
Trace the execution of the following call to this function
lc_mystery2([-2, 1, -4, 3])
In the Task 2 section of lab2_tasks12, we have given you a table
that you should complete to illustrate the execution of the list
comprehension. You may not need all of the rows in the table.
What value is assigned to the variable bestpair during the call
to lc_mystery2 that you just traced?
What is the return value of the call that you just traced?
What does this function do in general?
In this task, we will design and implement a function negate_evens(vals)
that takes list vals and that uses recursion to construct and return
a new list in which all of the even numbers have been negated (i.e.,
multiplied by -1).
For example:
>>> negate_evens([2, 3, 5, 8]) result: [-2, 3, 5, -8] >>> negate_evens([1, -4, -7, 6]) result: [1, 4, -7, -6]
Let’s start by determining the base case(s). When is the problem simple/small enough to be solved directly (without first solving a smaller subproblem)?
Next, we need to design the recursive case. In doing so, it helps to consider some concrete cases. For example:
case 1: the first element is even
negate_evens([2, 3, 5, 8])
case 2: the first element is odd
negate_evens([1, -4, -7, 6])
Note that for this problem we need two concrete cases: one in which the first element is even, and one in which the first element is not even. That’s because what we do after the recursive call depends on whether the first element is even.
Now implement the function by taking the following steps:
In Spyder, open a new editor window using File -> New File,
and save it to your lab4 folder using the name lab4.py.
Define negate_evens in lab4.py. Remember to include a
docstring that describes the behavior of the function, its
parameters, and its return value.
Once you think the function is ready, run your lab4.py
file and test the function from the console.
Debug the function as needed until it works correctly. Don’t forget that you need to re-run the file after making changes to the function.
If you need help with debugging, ask a staff member! You can also take advantage of the Debugging Tips page.
Important!
Passing one or more of the provided test calls does not mean that a function is fully correct! Make sure to fully read the description of what a given function is supposed to do, and carry out whatever additional tests are needed to convince yourself that it works correctly in all cases.
Begin by entering the following list comprehension from the console:
>>> [-1*x for x in [1, -4, -7, 6]]
Does the result make sense?
Now try entering the following list comprehension:
>>> [abs(x) for x in [1, -4, -7, 6]]
It calls the abs function, which is a built-in Python function that
computes the absolute value of a number. Does the result make sense?
Let’s say that we want to write a version of the negate_evens
function called negate_evens_lc that uses a list comprehension
rather than recursion.
At first, it might seem as though we could adapt the list
comprehension from part 1 above by adding a filter (i.e., an if
clause), but that won’t work! To see why, try entering the
following from the console:
>>> [-1*x for x in [1, -4, -7, 6] if x % 2 == 0]
Instead, we need to write a helper function that can be called
from within the list comprehension that negate_evens_lc will
use. The helper function should take a single integer and process
it.
To figure out what this helper function should do, ask yourself:
What needs to be done to each integer in vals so that
negate_evens_lc can return the appropriate list?
Then go ahead and write the necessary helper function, adding it
to your lab4.py file. Give it a name that describes what it is
supposed to do.
Once you think the helper function is ready, run your lab4.py
file and test the function from the console.
Now write negate_evens_lc by completing the following template:
def negate_evens_lc(vals): """ uses a list comprehension to return a version of the list vals in which all even numbers have been multiplied by -1. input: vals is a list of arbitrary of integers """ return ____________
Fill in the blank with the necessary list comprehension. Make sure
that you call the helper function from within the list comprehension
– just as the list comprehension from part 2 above called
the built-in abs function.
Finally, run your lab4.py file and test your function. For example:
>>> negate_evens_lc([1, -4, -7, 6]) result: [1, 4, -7, -6]
In this optional challenge problem, we will implement a recursive function that has the same behavior as the list slice operator.
More specifically, we will write a function myslice(values, start, stop)
that takes list values and two index values start and stop, and that
uses recursion to construct and return the equivalent of
values[start:stop] – i.e., the slice of values that begins
with the element at index start and that goes up to but not including the
element at index stop.
For example:
>>> values = ['a', 'b', 'c', 'd', 'e'] >>> myslice(values, 2, 4) # should return equivalent of values[2:4] result: ['c', 'd'] >>> myslice(values, 1, 5) # should return equivalent of values[1:5] result: ['b', 'c', 'd', 'e'] >>> myslice(values, 3, 3) # should return equivalent of values[3:3] result: []
Your implementation must be recursive, and the only list operations you are
allowed to use are accessing the first element of the list (values[0]) and
accessing all elements except the first (values[1:]).
You do not need to worry about negative or omitted index values or the use of a stride length.
Start by determining the base case(s). When is the problem simple/small enough to be solved directly (without first solving a smaller subproblem)?
Next, design the recursive case by considering concrete cases.
In doing so, it’s important to realize that when you reduce the list to a smaller list, you also need to adjust one or both of the index values! For example, the problem
myslice(['a', 'b', 'c', 'd', 'e'], 2, 4)
is equivalent to
myslice(['b', 'c', 'd', 'e'], 1, 3)
Note that because the list has been shortened, we need to adjust
the index values in order to continue getting the result
['c', 'd'].
Here are some other concrete cases for you to think through:
myslice(['to', 'be', 'or', 'not', 'to', 'be'], 1, 4)
myslice([6, 5, 4, 3, 2, 1], 0, 3)
Implement the myslice(values, start, stop) function and store it
in your lab4.py. Remember to add a docstring to the function
that describes its behavior, its parameters, and its return value.
If you need help debugging your function, remember to take a look at the Debugging Tips page.
Last updated on January 6, 2023.