Part I due by 11:59 p.m. on Thursday, October 31, 2024.
Part II due by 11:59 p.m. on Sunday, November 3, 2023.
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 Gradescope, following the procedures found at the end of Part I and Part II.
Create a subfolder called ps6 within your
cs111 folder, and put all of the files for this assignment in that
folder.
Problems 0, 1 and 2 will all be completed in a single PDF file. To create it, you should do the following:
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
ps6pr012.
Add your work for Problems 0, 1 and 2 to this file.
Once you have completed all of these problems, choose
File->Download->PDF document, and save the PDF file in your ps6
folder. The resulting PDF file (ps6pr012.pdf) is the one that you
will submit. See the submission guidelines at the end of Part I.
Consider the following function, which uses a for loop to
process a list of numbers:
def foo1(vals): for x in vals: if x % 4 == 0: return True return False
a. Trace the execution of the following call to this function
foo1([9, 10, 11])
To do so, complete the template that we have provided in
section 0-3a of ps6pr012 to show how the values of the
loop variable and the if condition change over time,
and the final return value of the function. Note: It’s possible
that the function won’t end up processing all of the numbers
in the list vals, so you may not need all of the rows of
the table.
b. Now trace the execution of the following call to this function
foo1(range(1, 6))
To do so, complete the template that we have provided in
section 0-3b of ps6pr012 to show how the values of the
loop variable and the if condition change over time,
and the final return value of the function. Here again,
you may not need all of the rows of the table.
Consider the following function foo2. It is similar to the
foo1 function above, but with an important difference!
def foo2(vals): for x in vals: if x % 4 == 0: return True else: return False
a. Trace the execution of the following call to this function
foo2(range(1, 6))
To do so, complete the template that we have provided in
section 0-4a of ps6pr012 to show how the values of the
loop variable and the if condition change over time,
and the final return value of the function. Here again,
you may not need all of the rows of the table.
b. Now consider the following call to this function:
foo2(range(500))
The expression range(500) produces 500 integers. When
that range of integers is passed into foo2, how many
repetitions will the for loop perform? Explain your
answer briefly.
10 points; individual-only
Consider the following Python program, which uses a nested loop:
for p in ['super', 'sub']: for w in ['class', 'sonic', 'group']: print(p + w) print(p[-1] + w[0]) print(p)
In section 1-1 of ps6pr012, we have given you a template that you
should complete to specify how the variables change over time
and what the program outputs. You may not need all of the rows
in the table.
Consider the following Python program, which uses also uses a nested loop:
for x in [2, 4, 6]: for y in range(1, x): print(x + y) print(x, y)
In section 1-2 of ps6pr012, we have given you a template that you
should complete to specify how the variables change over time
and what the program outputs. You may not need all of the rows
in the table.
Hint: The lecture and lab exercises include similar traces.
10 points; individual-only
Consider the following Python program
def mystery(x, vals): for i in range(len(vals)): vals[i] *= 2 x += 5 # what do things look like in memory at this point? return x x = 2 v1 = [1, 2, 3] v2 = v1[:] v3 = v1 mystery(x, v1) print(x) print(v1) print(v2) print(v3)
In section 2-1 of ps6pr012, we have given you the beginnings of
a memory diagram. It includes:
two stack frames: one for the global scope, and one for
the call mystery(x, v1)
the list to which the variable v1 refers.
Complete the provided memory diagram so that it shows what things
look like in memory at the end of the call to
mystery—just before it returns.
To do so, you should:
Click on the diagram and then click the Edit link that appears below the diagram.
Make whatever changes are needed to the diagram. Below the thick horizontal line, we have given you a set of extra components that you can use as needed by dragging them above the thick line and putting them in the correct position. You may not need all of the provided components.
You can also edit the value inside of any cell by clicking on that cell and making whatever change is needed.
Once you have made all of the necessary changes, click the Save & Close button.
What is the output of the program?
20 points; pair-optional
This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.
In Spyder, open a new editor window using File -> New File,
and save it to your ps6 folder using the name ps6pr3.py.
Important guidelines
Here are the guidelines that you should follow for this and all remaining Python problems over the course of the semester:
Include comments at the top of the file
that are similar to the ones that we gave you at the top of
ps1pr3.py.
Your functions must have the exact names specified below,
or we won’t be able to test them. Note in particular that the
case of the letters matters (all of them should be lowercase),
and that some of the names include an underscore character (_).
As usual, each of your functions should include a docstring that describes what your function does and what its inputs are. In addition, you should include any other comments that might be necessary to explain your code. More generally, you should aim to make your code easy to read. For example, you should choose descriptive names for your variables. In addition, we encourage you to leave a blank line between logical parts of your function.
If a function is supposed to return a value, make sure that it actually returns the specified value, rather than printing it.
You should not use any Python features that we have not discussed in lecture or read about in the textbook.
Your functions do not need to handle bad inputs – inputs with a type or value that doesn’t correspond to the description of the inputs provided in the problem – unless the problem explicitly states otherwise.
Leave one or two blank lines between functions to make things more readable.
If you want to add test calls to this or any other Python file,
please do so in appropriate test function like the one that we
gave you at the bottom of the
ps1pr3.py starter file for Problem
Set 1. After running your Python file, you can call the
test function (by entering test()) to see the results of
all of the test calls.
Do not add any lines of code that belong to the global scope of the program (i.e., lines that are outside of any function).
Write a function repeat(s, n) that takes a string s and an
integer n, and that uses a loop to create and
return a string in which n copies of s have been
concatenated together.
To force you to use a loop, you may not use the
multiplication operator (*). Rather, you should use a loop to
add together n copies of s. For example, 'hello'*3 is
equivalent to 'hello'+'hello'+'hello', and you will need to use
a loop to compute that sum.
If n is less than or equal to 0, the function should return the
empty string (i.e., the string '', which does not have any
spaces between the quotes).
Here are some test cases:
>>> repeat('da', 2) result: 'dada' >>> repeat('Go BU!', 4) result: 'Go BU!Go BU!Go BU!Go BU!' >>> repeat('hello', 1) result: 'hello' >>> repeat('hello', 0) result: ''
Write a function contains(s, c) that takes an arbitrary string
s and a single-character c as inputs and uses a loop
to determine if s contains the character c, returning
True if it does and False if it does not.
To force you to use a loop, you may only use the in operator
in your loop header. You may not use it to check for the
presence of a character in the string. Rather, you should use a
loop to process s one character at a time and determine if c
is contained in s.
For example:
>>> contains('hello', 'e') result: True >>> contains('hello', 'l') result: True >>> contains('hello', 'x') result: False >>> contains('', 'x') result: False
You solved this problem using recursion in Problem Set 2, but for this problem set you must use a loop.
Warning
Your function should return a boolean value – either True
or False, without any quotes around them. If you see
quotes around the result when you make the calls above
from the console, you must fix your function to remove the
quotes.
Hint: One way to solve this problem is to have two return
statements: one inside the loop, and one after the loop has completed.
Write a function add(vals1, vals2) that takes as inputs two
lists of numbers, vals1 and vals2, and that uses
a loop to construct and return a new list in which
each element is the sum of the elements at the corresponding positions
in the original lists. For example:
>>> add([1, 2, 3], [4, 5, 6]) result: [5, 7, 9] >>> add([5, 3], [6, 4]) result: [11, 7] >>> add([1, 2, 3, 4], [20, 30, 50, 80]) result: [21, 32, 53, 84]
Special case: If the two lists do not have the same length, the function should begin by padding the beginning of the shorter list with the necessary number of 0s so that the two lists have the same length. For example:
>>> add([7, 5, 3], [6]) result: [7, 5, 9]
Note that the result in this case is the same as the result that we would get from the call
>>> add([7, 5, 3], [0, 0, 6])
Thus, the function can obtain the correct result by changing
vals2 from [6] to [0, 0, 6] before attempting to add the
corresponding pairs of elements from the two lists.
Hints:
You will need to use an index-based loop so that you can access the corresponding elements from each input at the same time. We took a similar approach in problem 9-4 of Problem Set 5.
When the lists don’t have the same length, you can use list multiplication to create the necessary padding. For example:
>>> [0] * 3 result: [0, 0, 0]
Write a function replace(vals, old, new) that takes a list of
integers called vals and two integers old and new, and
that modifies the list so that all occurrences of old are
replaced with new, and all other elements are left unchanged.
This function should not return a value. Rather,
it should use an index-based loop to modify the internals of the
original list as needed. For example, to modify element i of the
list vals, you should perform an assignment that looks like
this:
vals[i] = expression
where expression is replaced with an appropriate expression for the
new value of vals[i]. We performed this type of item assignment
in this week’s lectures and lab.
For reasons that we discussed in lecture, any changes that the function makes to the internals of the list using item assignment will still be there after the function returns.
For example:
>>> vals1 = [6, 2, 3, 4, 2, 5, 2] >>> replace(vals1, 2, 7) >>> vals1 result: [6, 7, 3, 4, 7, 5, 7] >>> vals2 = [3, 4, 5, 6] >>> replace(vals2, 5, 0) >>> vals2 result: [3, 4, 0, 6]
Note: As shown above, when you call the function from the console, you should not see a result. That’s because your function should not return a value.
Coming soon!
30 points; individual-only
This problem involves using loops to process a list of stock prices. You will also gain experience in writing a program that involves repeated user interactions.
The premise behind this problem is that you have been hired by an investment firm called Time Travel Securities, Inc. (also known as TT Securities or TTS). They want you to write a program that will perform a variety of tasks involving a list of stock prices.
We will discuss this application in lecture and look at an example user-interaction loop. Begin by downloading the following file:
Begin by downloading this file: ps6pr4.py
Make sure to put the file in your ps6 folder. If your browser
doesn’t allow you to specify where the file should be saved, try
right-clicking on the link above and choosing Save as... or
Save link as..., which should produce a dialog box that allows you
to choose the correct folder for the file.
Open the file in Spyder. You should see some starter code that is based on the code from lecture. You will add the code needed to support the functionality described below.
Important
You may not use the built-in sum, min, or max functions
for this problem. Instead, you should use loops of your own
construction to compute the necessary values.
You should continue to follow the guidelines that we gave you earlier. Those guidelines apply to this and all remaining Python code that you write for this course!
In particular, do not add any lines of code that belong to the global scope of the program (i.e., lines that are outside of any function).
Running the program
The starter code that we’ve given you includes a function called
tts() that serves as the “main” function–the one that handles the
user interactions.
To run the program, you should call this function. Run ps6pr5.py
in Spyder, and then make the following function call from the console:
>>> tts()
Required functionality
The program should present the user with the following menu of choices:
(0) Input a new list of prices (1) Print the current prices (2) Find the latest price (3) Find the average price (4) Find the max price and its day (5) Find the min single-day change and its day (6) Test a threshold (7) Your investment plan (8) Quit Enter your choice:
Our starter code includes support for a few of these options. You will need to implement the rest of them. In particular, you should perform tasks 0-5 outlined below.
A sample run that illustrates what the behavior of the program should look like is available here.
Read over the starter code that we’ve given you. Make sure that you understand how the various functions work, and how they fit together.
Add support for option 3: finding the average price
First, write a function called avg_price that takes a list of 1
or more prices and computes and returns the average price.
Don’t forget that you cannot use the built-in sum, min, or
max functions. Instead, you should use a loop of your own
construction to perform the necessary computations.
Here are two examples:
>>> avg_price([10, 20, 18]) result: 16.0 >>> avg_price([5, 8, 5, 3]) result: 5.25
Next, you should integrate this function into the overall program by doing the following:
Update the display_menu function to print the description
of this menu option.
Add code to the tts function to call your avg_price
function whenever the user chooses option 3, and to print the
result that it returns. See the sample run
for an example of what the output of this option should look like.
Important: The printing of the result should be done in
tts. Your avg_price function should not do any
printing. In general, none of the new functions that you
write should do any printing. Rather, you should add code
to tts to print the results in the proper format.
Add support for option 4: finding the maximum price and its day
Write a function called max_day that takes a list of 1 or more
prices and computes and returns the day (i.e., the index) of
the maximum price. Don’t forget that you cannot use the
built-in sum, min, or max functions.
Here are two examples:
>>> max_day([20, 10, 18]) result: 0 >>> max_day([17, 15, 22, 18, 12]) result: 2
Next, you should integrate this function into the overall program,
taking steps similar to the ones that you took above. In
printing the result, tts should print both the day
of the maximum price and the maximum price itself. See the
sample run for an example of what the output should look
like.
Add support for option 5: finding the minimum single-day change and its day
Write a function called min_change_day that takes a list of 2 or more
prices and computes and returns the day (i.e., the index) of
the minimum single-day absolute change in price. For example,
consider the following list of prices:
[10, 30, 80, 70, 50, 10]
The minimum single-day absolute change in this list occurs on day 3, when the price decreases to 70, which is an absolute change of 10 from the price on day 2, and no other single-day absolute change in the list is less than 10. Thus, the function would return 3 (the index of the 70) for this list of prices.
Don’t forget that you cannot use the built-in sum, min, or
max functions. However, you can use the built-in abs function
to compute absolute value.
Here are two example calls:
>>> min_change_day([10, 30, 80, 70, 50, 10]) result: 3 >>> min_change_day([10, 30, 80, 15, 20]) result: 4
Next, you should integrate this function into the overall program,
taking steps similar to the ones that you took above. In
printing the result, tts should print both the day of
the minimum absolute change and the prices before and after the
change. See the sample run for an example of what the
output should look like.
Add support for option 6: testing a threshold
Begin by writing a function called any_above that takes a list of
1 or more prices and an integer threshold, and uses a loop to
determine if there are any prices above that threshold. The
function should return True if there are any prices above the
threshold, and False otherwise. For example:
>>> any_above([30, 20, 15], 35) result: False >>> any_above([10, 20, 15], 12) result: True
Important: Make sure that you return either the boolean
literal True or the boolean literal False. Do not include
quotes around these values.
Next, you should integrate this function into the overall program.
In addition to the types of steps that you’ve taken for the
previous options, you will also need to get the threshold from
the user. Add an input statement to tts that obtains the
threshold, and don’t forget to convert the string that is returned
by input to an integer. See our starter code for an example of
this.
Add support for option 7: the “time travel” investment
strategy discussed in lecture
First, write a function called find_tts that takes a list of 2
or more prices, and that uses one or more loops to find the best
days on which to buy and sell the stock whose prices are given in
the list of prices. The buy and sell days that you determine
should maximize the profit earned, but the sell day must be
greater than the buy day. The function should return a
list containing three integers:
For example:
>>> find_tts([40, 10, 20, 35, 25]) result: [1, 3, 25]
In this case, the function returns a list that indicates that the best investment plan is to buy on day 1 and sell on day 3, which gives a profit of $25. Here’s another example:
>>> find_tts([5, 10, 45, 35, 3]) result: [0, 2, 40]
Hint: In implementing this function, you may find it helpful to
adapt the example diff function that we covered in lecture.
Don’t forget to integrate this function into the overall program, taking similar steps to the ones that you took for the earlier options. See the sample run for an example of what the output of this option should look like.
25 points; individual-only
We will discuss the concepts needed for this problem in Wednesday’s lecture.
This problem involves writing functions that create and manipulate two-dimensional lists of integers. You should continue to follow the guidelines that we gave you earlier.
Getting started
Begin by downloading this file:
ps6pr5.py
Make sure to put the file in your ps6 folder.
Open that file in Spyder, and put your work for this problem in that file.
In ps6pr5.py, we’ve given you the following functions:
create_grid(num_rows, num_cols), which creates and returns a 2-D list
of 0s with the specified dimensions
print_grid(grid), which takes a 2-D list grid and prints it in
2-D form, with each row on its own line
random_grid(num_rows, num_cols), which creates and
returns a 2-D list with the specified dimensions in which
each cell is assigned a random integer between 0 and 9
For example (although the actual values of the cells will vary):
>>> grid = random_grid(4, 5) >>> print_grid(grid) [[0, 0, 3, 1, 9], [2, 8, 1, 3, 3], [7, 5, 2, 4, 9], [1, 8, 8, 7, 3]]
Your tasks
Based on the example of random_grid, write a function
col_index_grid(num_rows, num_cols) that creates and returns
a 2-D list with the specified dimensions in which each cell has
as its value the index of the column to which the cell belongs. For
example:
>>> grid = col_index_grid(5, 4) >>> print_grid(grid) [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] >>> grid = col_index_grid(7, 3) >>> print_grid(grid) [[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
Your function should take the same approach as random_grid:
Call create_grid to create a 2-D list with the specified
dimensions and assign it to a variable.
Use nested loops to modify the internals of the 2-D list. However, instead of assigning a random integer, you should assign the column index of the cell.
Return the modified 2-D list.
Write a function num_between(grid, n1, n2) that takes a 2-D
list of integers grid and two integers n1 and n2, and that
returns the number of values in grid that are between n1 and
n2 – i.e., greater than or equal to n1 and less than or equal
to n2. For example:
>>> grid = [[0, 4, 8], [6, 10, 5]] >>> num_between(grid, 4, 6) result: 3 >>> num_between(grid, 7, 11) result: 2 >>> num_between(grid, 1, 3) result: 0 >>> num_between(grid, 11, 7) result: 0
As we’ve seen in lecture, copying a list variable does not actually copy the list. To see an example of this, try the following commands from the console:
>>> grid1 = [[0, 0], [0, 0]] >>> grid2 = grid1 # copy value of grid1 into grid2 >>> print_grid(grid2) [[0, 0], [0, 0]] >>> grid1[0][0] = 1 >>> print_grid(grid1) [[1, 0], [0, 0]] >>> print_grid(grid2) [[1, 0], [0, 0]]
Note that changing grid1 also changes grid2! That’s because the
assignment grid2 = grid1 did not copy the list represented by
grid1; it copied the reference to the list. Thus, grid1
and grid2 both refer to the same list!
To avoid this problem, write a function copy(grid)
that creates and returns a deep copy of grid–a new, separate
2-D list that has the same dimensions and cell values as grid.
Note that you cannot just perform a full slice on grid (e.g.,
grid[:]), because you would still end up with copies of the
references to the rows! Instead, you should do the following:
Call create_grid to create a new 2-D list with the same dimensions
as grid, and assign it to an appropriately named variable.
(Don’t call your new list grid, since that is the name
of the parameter!) Remember that len(grid) will give you the
number of rows in grid, and len(grid[0]) will give you the
number of columns.
Use nested loops to copy the individual values from the cells of
grid into the cells of your newly created grid.
Make sure to return the newly created grid and not the original one!
To test that your copy function is working properly, try the
following examples:
>>> grid1 = col_index_grid(3, 4) >>> print_grid(grid1) [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] >>> grid2 = copy(grid1) # should get a deep copy of grid1 >>> print_grid(grid2) [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] >>> grid1[0][1] = 7 >>> print_grid(grid1) [[0, 7, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] >>> print_grid(grid2) # should NOT see a 7 in the top row [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
Write a function double_with_cap(grid, cap) that takes a
2-D list of integers grid and a single integer cap,
and that modifies the internals of grid. Specifically, the
function should double the value of each element unless doing so
would cause the value of the element to be greater than cap. If
doubling the element produces a value that is greater than cap,
the element should be replaced with the value of cap instead.
For example:
>>> grid = [[1, 3, 4], [6, 0, 5]] >>> print_grid(grid) [[1, 3, 4], [6, 0, 5]] >>> double_with_cap(grid, 9) >>> print_grid(grid) [[2, 6, 8], [9, 0, 9]]
Note that most of the elements in the grid have been doubled. However, in the bottom row:
doubling 6 gives 12, which is greater than the cap of 9,
so 6 is replaced with 9 instead
doubling 5 gives 10, which is greater than the cap of 9,
so 5 is replaced with 9 instead.
Important notes:
Unlike the functions that you wrote for parts 1 and 3 of this problem, this function should not create and return a new 2-D list. Rather, it should modify the internals of the existing list.
Unlike the previous functions that you wrote for this problem,
this function should not have a return statement,
because it doesn’t need one! That’s because the parameter
grid gets a copy of the reference to the original 2-D
list, and thus any changes that it makes to the internals of
that list will still be visible after the function returns.
Here’s another example that should help to reinforce your understanding of references:
>>> grid1 = col_index_grid(5, 4) >>> print_grid(grid1) [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]] >>> grid2 = grid1 >>> grid3 = grid1[:] >>> double_with_cap(grid1, 5) >>> print_grid(grid1) [[0, 2, 4, 5], [0, 2, 4, 5], [0, 2, 4, 5], [0, 2, 4, 5], [0, 2, 4, 5]]
As you can see above, the value of grid1 has been changed.
What about grid2 and grid3?
Before entering the statements below, see if you can predict
what has happened to grid2 and grid3. If we print
them, will we see the original grid or the modified one?
Test your understanding by first entering the following:
>>> print_grid(grid2)
What do you see? Why does this make sense?
Now enter the following:
>>> print_grid(grid3)
What do you see? Why does this make sense?
(You don’t need to record your answers to these questions, but we strongly encourage you to make sure that you understand what happens here. Feel free to ask for help if you don’t understand.)
Write a function sum_evens_in_col(grid, colnum) that takes a
2-D list of integers grid and an integer colnum, and
that computes and returns the sum of the even values in the column
of grid whose index is colnum.
For example:
>>> grid1 = [[1, 3, 4], [4, 5, 6], [8, 9, 10]] >>> print_grid(grid1) [[1, 3, 4], [4, 5, 6], [8, 9, 10]] >>> sum_evens_in_col(grid1, 0) result: 12 >>> sum_evens_in_col(grid1, 1) result: 0 >>> sum_evens_in_col(grid1, 2) result: 20
Note: Unlike the other functions that you are writing for this problem, this function should not need nested loops. Rather, a single loop should suffice.
Coming soon!
Last updated on October 28, 2024.