Problem Set 4

Part I due by 11:59 p.m. on Thursday, October 10, 2024.
Part II due by 11:59 p.m. on Sunday, October 13, 2024.

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 Gradescope, following the procedures found at the end of Part I and Part II.

---

Part I

Creating the necessary folder

Create a subfolder called ps4 within your cs111 folder, and put all of the files for this assignment in that folder.

Problem 0: Reading and response

5 points; individual-only

In lecture, we will be focusing briefly on what happens at the hardware level when we use a computer. This week’s reading considers one man’s vision of the future of computation hardware and, more generally, of humanity itself!

Begin by reading a profile of inventor and futurist Ray Kurzweil from The Guardian.

Next, create the necessary file for your response by taking the following steps:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps4pr0.

In your copy of ps4pr0, write a response that addresses the following prompt:

Kurzweil views technology as a fundamentally positive force in human development. Is his vision of the future one that you would look forward to? Why or why not?

As always, you only need to write a short paragraph that reflects your critical thinking about the article.

Once you have completed your response, choose File→Download→Plain Text, and save the file on your machine. The resulting file (ps4pr0.txt) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: From binary to decimal and back!

20 points; pair-optional

This is one of only two problems from this 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'.

The guidelines that we gave you for Problem Set 2, Problem 3 also apply here. In addition, you must use recursion in your solutions, and you may not use loops or list comprehensions.

Getting started

1. If you haven’t already done so, create a folder named ps4 for your work on this assignment. You can find instructions for doing so here.

2. In Spyder, open a new editor window using File -> New File, and save it to your ps4 folder using the name ps4pr1.py.

The functions

1. Write a function dec_to_bin(n) that takes a non-negative integer n 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)
   result: '101'
   
   >>> dec_to_bin(12)
   result: '1100'
   
   >>> dec_to_bin(0)
   result: '0'
   

   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.

   • Make sure that all return statements return a string and not an integer.

   • In lecture, we gave you an example of how the function should recursively process a number. You should use that example and other concrete cases to determine the appropriate logic for the recursive case.

   • In addition to the test cases provided above, make sure to try other test cases to ensure that your function works correctly in all cases!

2. Write a function bin_to_dec(b) that takes a string b 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')
   result: 5
   
   >>> bin_to_dec('1100')
   result: 12
   
   >>> bin_to_dec('0')
   result: 0
   

   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. You may assume that the string passed in for b will never be empty.

   • Make sure that all return statements return an integer and not a string.

   • In lecture, we gave you an example of how the function should recursively process a string. You should use that example and other concrete cases to determine the appropriate logic for your recursive case.

   • In addition to the test cases provided above, make sure to try other test cases to ensure that your function works correctly in all cases!

Problem 2: Using your conversion functions

20 points; pair-optional

This is one of only two problems from this 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 for your program, and save it to your ps4 folder using the name ps4pr2.py.

The guidelines that we gave you for Problem Set 2, Problem 3 also apply here.

1. Write a function mul_bin(b1, b2) that takes as inputs two strings b1 and b2 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
   result: '110'
   
   >>> mul_bin('1001', '101')    # 9 * 5 = 45
   result: '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 your dec_to_bin and bin_to_dec functions from within this function. Convert both b1 and b2 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
   

2. Write a function largest_bin(binvals) that takes a list binvals of 1 or more strings – each of which represents a binary number – and that finds and returns the string in binvals that represents the largest binary number. For example:

   >>> largest_bin(['1100', '10011', '101', '10000'])
   result: '10011'
   

   The above call returns '10011' because the binary number 10011 has the largest value of any of the binary numbers in the list.

   Your function must make use of one of the conversion functions that you wrote for Problem 1. In addition, we encourage you to use the list-of-lists technique that we covered in lecture and used in Problem Set 3, but you may use recursion instead if you prefer.

Submitting your work for Part I

Important: You should submit a plain-text file for Problem 0, not a PDF. See Step 1 below as needed.

Submit all three of your files for Part I under the assignment labeled PS 4: Problems 0-2 using these steps:

1. If you still need to create a text file for Problem 0, open your file on Google Drive, choose File->Download->Plain Text, and save the file in your ps4 folder.

2. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

4. Click the Upload button.

5. You should see a box saying that your submission was successful. Click the (x) button to close that box.

6. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

7. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

8. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

---

Part II

Problem 3: Functions that process binary numbers

30 points; individual-only

This problem asks you to write functions that process one or more binary numbers represented as bitstrings – i.e., as strings of 0s and 1s.

In Spyder, open a new editor window for your program, and save it to your ps4 folder using the name ps4pr3.py.

The guidelines that we gave you for Problem Set 2, Problem 3 also apply here.

1. Write a function count_evens_rec(binvals) that takes a list binvals of 0 or more strings – each of which represents a binary number – and that uses recursion to compute and return the number of the bitstrings in the list that represent an even number. For example:

   >>> count_evens_rec(['1100', '10011', '101', '010'])
   result: 2
   

   The above call returns 2 because two of the bitstrings in the list ('1100' and '010') represent even numbers.

   This version of the function must use recursion and it may not use a list comprehension.

   Hint: Although you could in theory use one of your base-conversion functions as part of your solution, it isn’t necessary to do so. Rather, you should be able to easily determine if a bitstring represents an even number by checking one of the bits in the string.

2. Write a function count_evens_lc(binvals) that takes a list binvals of 0 or more strings – each of which represents a binary number – and that uses a list comprehension to compute and return the number of bitstrings in the list that represent an even number. In other words, this function should do the same thing as the previous function, but it must use a list comprehension instead of recursion. For example:

   >>> count_evens_lc(['1100', '10011', '101', '010'])
   result: 2
   

   This version of the function must use a list comprehension and it may not use recursion.

3. Write a function called add_bitwise(b1, b2) that adds two binary numbers. This function must use recursion to perform the bitwise, “elementary-school” addition algorithm that we discussed in lecture, and it should return the result. It must not perform any base conversions.

   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 and 100111, you end up with 3 carry bits, as shown in blue below:

   

   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 or b2) is the empty string, your function should return the other string.

   • 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! We discussed this in lecture.

   • Here are some test cases:

     >>> add_bitwise('11', '100')
     result: '111'
     
     >>> add_bitwise('11', '1')
     result: '100'
     
     >>> add_bitwise('', '101')
     result: '101'
     
     >>> add_bitwise('11100', '11110')
     result: '111010'
     

     Make sure to try other test cases to ensure that your function works correctly in all cases!

Submitting your work for Part II

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

Submit your ps4pr3.py file under the assignment labeled PS 4: Problem 3 using these steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add your file to the box labeled DRAG & DROP. You can either drag and drop the file from its folder into the box, or you can click on the box itself and browse for the file.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your file. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work.

7. Near the top of the page, click on the box labeled Code. Then click on the name of your file to view its contents. Check to make sure that the file contains the code that you want us to grade.

Last updated on October 8, 2024.