Old version
This is the CS 111 site as it appeared on May 10, 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.
Problems
Part I
due by 11:59 p.m. on Thursday, February 22, 2018
Problem 0: Reading and response
5 points; individual-only
Your work thus far in CS 111 has probably given you many opportunities to deal with bugs in your code! Some bugs are obvious, while others can only be discovered with careful testing.
In a large, complex software system, it can be difficult to find every bug, and the failure to do so can sometimes result in catastrophic consequences. This week’s reading involves just such a catastrophic bug–one that led to the destruction of an expensive rocket known as the Ariane 5. And it turns out that the bug in question was directly related to the bit-level representation of data that we have been covering in class.
The article, by historian of science James Gleick, is available here.
After you have read it, write a response that addresses–at least
to some extent–both of the following prompts. Put your response
in a file named ps4pr0.txt
. Don’t forget that the file that you submit
must be a plain-text file.
-
Which contributing factor within the bug’s origins (there are many!) strikes you as the “most preventable” and why? Of course, this will be in hindsight.
-
The investigative report that uncovered the bug stated that software “does not fail in the same sense as a mechanical system.” Do you agree or disagree with this statement? Explain briefly.
As always, a few carefully considered sentences that reflect your critical thinking about the article will more than suffice.
Problem 1: From binary to decimal and back!
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.
This problem asks you to write functions related to the binary
represention of integers. We will use strings consisting of '0'
s
and '1'
s for the binary numbers. For example, the binary representation
of the integer 5 would be the string '101'
.
In IDLE, use the File -> New Window menu option to open a new editor
window for your code, and save it using the name ps4pr1.py
.
Make sure to specify the .py
extension.
The guidelines that we gave you for Problem Set 2, problem 2 also apply here. In addition, you must use recursion in your solutions, and you may not use loops or list comprehensions.
-
Write a function
dec_to_bin(n)
that takes a non-negative integern
and uses recursion to convert it from decimal to binary – constructing and returning a string version of the binary representation of that number. For example:>>> dec_to_bin(5) '101' >>> dec_to_bin(12) '1100'
Notes/hints:
-
The function must use the recursive, right-to-left approach that we discussed in the lecture on binary numbers.
-
You will need two base cases: one for when
n
is 0, and one for whenn
is 1. Remember that you should always check for the base cases first. -
In lecture, we gave you an example of how the function should recursively process a number. You should use that example to determine the appropriate logic for the recursive case.
-
Because we’re taking a right-to-left approach, the input to the recursive call should be the decimal number that’s produced when you remove the rightmost bit from
n
‘s binary representation. For example, ifn
is9
(which has the binary representation'1001'
), the recursive call should be on the number4
(which has the binary representation'100'
). In lecture, we discussed two options for obtaining the necessary number. -
We encourage you to make the recursive call at the start of the recursive case and store its return value in a variable. Then you can use that variable to construct the string that you will return.
-
Remember that the rightmost bit of
n
‘s binary representation depends on whethern
is even or odd. You can use the%
operator to figure this out. -
Here are some additional test cases:
>>> dec_to_bin(0) '0' >>> dec_to_bin(1) '1' >>> dec_to_bin(4) '100' >>> dec_to_bin(7) '111' >>> dec_to_bin(10) '1010' >>> dec_to_bin(111) '1101111'
-
-
Write a function
bin_to_dec(b)
that takes a stringb
that represents a binary number and uses recursion to convert the number from binary to decimal, returning the resulting integer. For example:>>> bin_to_dec('101') 5 >>> bin_to_dec('1100') 12
Notes/hints:
-
The function must use the recursive, right-to-left approach that we discussed in the lecture on binary numbers.
-
You will again need two base cases: one for the string
'0'
, and one for the string'1'
. You may assume that the string passed in forb
will never be empty. -
In lecture, we gave you an example of how the function should recursively process a string. You should use that example to determine the appropriate logic for your recursive case.
-
You should use slicing to obtain the string needed for the recursive call. Because we’re taking a right-to-left approach, the slice should give you everything but the rightmost bit. Here again, we encourage you to make the recursive call at the start of the recursive case and store its return value in a variable. Then you can use that variable to construct the value that you will return.
-
Don’t forget that the value obtained from the recursive call will be the decimal value of a smaller number, and you will need to adjust it accordingly. See the lecture notes for a reminder of how to do this.
-
Here are some additional test cases:
>>> bin_to_dec('0') 0 >>> bin_to_dec('1') 1 >>> bin_to_dec('100') 4 >>> bin_to_dec('111') 7 >>> bin_to_dec('1110') 14 >>> bin_to_dec('00011010') 26 >>> bin_to_dec('1111111') 127
-
Problem 2: Using your conversion functions
20 points; individual-only
In IDLE, use the File -> New Window menu option to open a new editor
window for your code, and save it using the name ps4pr2.py
.
Make sure to specify the .py
extension.
The guidelines that we gave you for Problem Set 2, problem 2 also apply here. You should not use recursion in these functions.
Important: Your should include the following line at the top of the file, after your initial comments:
from ps4pr1 import *
Doing so will allow you to use the dec_to_bin()
and bin_to_dec()
functions that you wrote for problem 1, provided that your ps4pr1.py
file is in the same folder as your ps4pr2.py
file.
-
Write a function
mul_bin(b1, b2)
that takes as inputs two stringsb1
andb2
that represent binary numbers. The function should multiply the numbers and return the result in the form of a string that represents a binary number. For example:>>> mul_bin('11', '10') # 3 * 2 = 6 '110' >>> mul_bin('1001', '101') # 9 * 5 = 45 '101101'
In this function, you should not use recursion or perform any binary arithmetic. Rather, you should make use of the conversion functions that you wrote for problem 1. If you included the line mentioned above to import your code from
pr4pr1.py
, you should be able to call yourdec_to_bin
andbin_to_dec
functions from within this function. Convert bothb1
andb2
to decimal, multiply the resulting decimal numbers, and then convert the resulting product back to binary! Here is the pseudocode:n1 = the decimal value of the input string b1 (use one of your conversion functions!) n2 = the decimal value of the input string b2 (use that function again!) b = the binary value of (n1 * n2) (use your other function!) return b
-
Write a function
add_bytes(b1, b2)
that takes as inputs two stringsb1
andb2
that represent bytes (i.e., 8-bit binary numbers). The function should compute the sum of the two bytes and return that sum in the form of a string that represents an 8-bit binary number. For example:>>> add_bytes('00000011', '00000001') '00000100' >>> add_bytes('00011100', '00011110') '00111010'
Note that you will need to ensure that the result is exactly 8 bits long. If the result is too short, you should add 0s on the left-hand side to get a string that is 8 characters long. If the result is too big to be represented in 8 bits, you should return the rightmost 8 bits of the result. For example:
>>> add_bytes('10000011', '11000001') # the result (101000100) has 9 bits, so return the rightmost 8 bits '01000100'
Here again, you should not use recursion or perform any binary arithmetic. Rather, you should make use of the conversion functions that you wrote for problem 1.
Hint: To ensure that your result has the correct length, we encourage you to do the following:
-
Use your conversion functions to determine the binary representation of the sum, and store that result in a variable.
-
Determine the length of the result using the
len()
function, and store that length in a variable. Then you can use conditional execution (if-else
orif-elif-else
) to decide what you should return. -
If the result is less than 8 bits long, precede the result with the correct number of leading
'0'
s. You can use the multiplication operator to produce the necessary string of'0'
s. -
Make sure that you also handle the case in which the result is more than 8 bits long.
-
Part II
due by 11:59 p.m. on Sunday, February 25, 2018
Problem 3: Recursive operations on binary numbers
30 points; individual-only
This problem asks you to write two different recursive functions that manipulate binary numbers.
In IDLE, use the File -> New Window menu option to open a new editor
window for your code, and save it using the name ps4pr3.py
.
Make sure to specify the .py
extension.
The guidelines that we gave you for Problem Set 2, problem 2 also apply here. In addition, you must use recursion in your solutions, and you may not use loops or list comprehensions.
-
The bitwise AND of two binary numbers is formed by considering the bits in the numbers from right to left. As you do so, each pair of corresponding bits is ANDed together to produce the appropriate bit for the result.
For example, to obtain the bitwise AND of
11010
and10011
, we would begin by essentially lining up the two numbers as follows:1 1 0 1 0 1 0 0 1 1 We would then AND together each pair/column of bits from right to left. For example, the rightmost column gives us
(0 AND 1)
which is0
:1 1 0 1 0 1 0 0 1 1 0 The next pair/column of bits gives us
(1 AND 1)
which is1
:1 1 0 1 0 1 0 0 1 1 1 0 Continuing in this way, we get:
1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 And thus the bitwise AND of
11010
and10011
is10010
.If one number has more bits than the other, the extra bits are effectively ANDed with 0s, and thus they lead to 0s in the result. For example:
1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 1 Write a function called
bitwise_and(b1, b2)
that takes as inputs two stringsb1
andb2
that represent binary numbers. The function should use recursion to compute the bitwise AND of the two numbers and return the result in the form of a string. For example:>>> bitwise_and('11010', '10011') '10010' >>> bitwise_and('1001111', '11011') '0001011'
Notes/hints:
-
Base cases: Because the function will be called recursively on smaller and smaller strings, you will eventually get down to an empty string for one or both of the inputs.
-
If both inputs are the empty string, the function should return the empty string.
-
If only one of the inputs is the empty string, the function should return a string that represents the result of ANDing the other input with 0s.
For example:
>>> bitwise_and('', '') '' >>> bitwise_and('101', '') '000' >>> bitwise_and('', '11010') '00000'
Hint: Use string multiplication to obtain a string with the appropriate number of 0s.
-
-
You should use recursion to AND the rest of the bits in the two numbers. When you do so, make sure that you end up considering the bits from right to left, rather than from left to right.
-
As usual, we recommend making the recursive call at the start of the recursive case and storing its return value in a variable. Then you can use that variable to construct the value that you will return.
-
You will need to use conditional execution (
if-else
orif-elif-else
) to decide what to return, based on the bits that are being ANDed by the current call of the function. Use concrete cases as needed to figure out the logic.
-
We will discuss the following function in lecture on Wednesday, 2/21.
-
Write a function called
add_bitwise(b1, b2)
that adds two binary numbers. This function should use recursion to perform the bitwise, “elementary-school” addition algorithm that we discussed in lecture, and it should return the result. It should not perform any base conversions, and it should not call theadd_bytes
function from Problem 2.Your function should add one pair of bits at a time, working from right to left and including any necessary “carry” bits, as discussed in lecture. For example, when adding
101110
and100111
, you end up with 3 carry bits, as shown in blue below:1 1 1 1 0 1 1 1 0 + 1 0 0 1 1 1 1 0 1 0 1 0 1 Notes/hints:
-
Base cases: Because the function will be called recursively on smaller and smaller strings, you will eventually get down to an empty string for one or both of the inputs. If either of the strings (
b1
orb2
) is the empty string, your function should return the other string. -
You should use recursion to add the rest of the numbers. Here again, we recommend making the recursive call at the start of the recursive case and storing its return value in a variable. Then you can use that variable to construct the value that you will return.
-
You will need to use conditional execution (
if-elif-else
) to decide what to return, based on the bits that are being added by the current call of the function. -
Handling cases that require a carry bit can be the most difficult part of this problem. The trick is to call the function recursively a second time to add in the carry bit!
-
Here are some test cases:
>>> add_bitwise('11100', '11110') '111010' >>> add_bitwise('10101', '10101') '101010' >>> add_bitwise('11', '1') '100' >>> add_bitwise('11', '100') '111' >>> add_bitwise('11', '') '11' >>> add_bitwise('', '101') '101'
-
Submitting Your Work
You should use Apollo to submit the following files:
- your
ps4pr0.txt
file containing your response to the reading for Problem 0 - your
ps4pr1.py
file containing your code for Problem 1; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner - your
ps4pr2.py
file containing your code for Problem 2 - your
ps4pr3.py
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.
-
Before submitting your files, make sure that your BU username is visible at the top of the Apollo page. If you don’t see your username, click the Log out button and login again.
-
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.
-
If you encounter problems with Apollo, click the Log Out button, 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
Here are the steps:
- Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
- Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
- Find the appropriate problem set section on the main page and click Upload files.
- 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.
- Click the Upload button at the bottom of the page.
- 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.
- 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 in Step 7 above.