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 of 0 or more integers 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]
When we use recursion to process a list of 0 or more values, and we need to consider every value in the list, we typically use an approach that looks something like this:
def negate_evens(vals): if vals == []: return # add the appropriate return value else: rest_negated = negate_evens(vals[1:]) # add code that handles vals[0] and that returns a value # that is based on the result of the recursive call
Function templates like this one can help you to more easily solve a problem that involves recursion – so we encourage you to commit them to memory!
Here are the steps you should take to complete the function:
In Spyder, open a new editor window using File -> New File,
and save it to your lab4 folder using the name lab4.py.
Copy and paste the above template into your file.
Add the correct return value for the base case. What result makes sense when the input to this function is an empty list?
Next, we need to determine what should happen after the recursive call. 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.
Here are some concrete cases you can use:
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])
Use your reasoning about these concrete cases to complete the function.
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 adding the following function to your lab4.py file:
def mult10(x): return x*10
Run your lab4.py file, and then enter the following list comprehension
from the console:
>>> [mult10(x) for x in [1, 4, 7, 6]]
Does the result make sense? Note that the list comprehension is using
the mult10 function as a helper function.
Now 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. To do so, we need to write a
new helper function that can be called from within the list
comprehension.
Like mult10, the new helper function should take a single
integer and process it. Unlike mult10, your new function will
need to decide what to return, based on whether the input is even
or odd.
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 mult10 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 September 30, 2024.