Problem Set 4

Part I due by 11:59 p.m. on Thursday, October 9, 2025.
Part II due by 11:59 p.m. on Sunday, October 12, 2025.

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: Practicing function calls, conditional execution and variable scope

10 points; individual-only

Midterm 1 is coming up in just over two weeks. To help you begin to review, we’re including this problem on topics from earlier in the semester.

First, create the necessary file for your answers by taking the following steps:

1. Make sure you are signed into your Google Drive account. Note that signing into BU Google Mail should accomplish the same thing.

2. Access the template that we have created by clicking on this link.

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

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

Consider the following Python program:

def foo(a, b):
    a = a + 4
    b = b * 2
    c = mystery(a)
    print('foo', a, b, c)
    c = c + mystery(b)
    print('foo', a, b, c)
    return c

def mystery(c):
    a = c + 3
    if c > 8:
        a = a // 2
        if a > 6:
            c = c - 2
    elif c < 20:
        a = a + 1
        if a == 5:
            c = c + 1
    else:
        c = c - 3
    return a

a = 3
b = 5
c = 2

print(a, b, c)
a = foo(b, c)
print(a, b, c)

In ps4pr0, we have provided tables for you to complete, and we have started some of the tables for you. You should:

• complete the variable tables so that they illustrate how the values of the variables change over time
• complete the output table so that it shows the output of the program (i.e., the values that are printed).

You may not need all of the rows provided in the tables.

Important: Please review the Midterm 1 info page carefully, and begin preparing for the exam. In addition to doing practice problems, we highly recommend that you review the relevant sections of the coursepack and make a summary of the key points in your own words. “Boiling down” the material in this way is a great way to ensure that you really understand the key concepts.

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

Please make sure to read and follow the guidelines given above in the section labeled Important.

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 pow_bin(b, e) that takes as inputs two strings b and e that represent binary integers. The function should determine the result of raising b to the e power and return the result in the form of a string that represents a binary number. For example:

   >>> pow_bin('11', '10')      # 3 ** 2 = 9
   result: '1001'
   
   >>> pow_bin('1001', '11')    # 9 ** 3 = 729
   result: '1011011001'
   

   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 b and e to decimal, compute the power using the resulting decimal numbers, and then convert the result back to binary! Here is the pseudocode:

   base = the decimal value of the input string b (use one of your conversion functions!)
   exp = the decimal value of the input string e (use that function again!)
   pow = the binary value of (base ** exp) (use your other function!)
   return pow
   

2. Write a function smallest_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 smallest binary number. For example:

   >>> smallest_bin(['1100', '110', '101', '10000'])
   result: '101'
   

   The above call returns '101' because the binary number 101 has the smallest 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

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

You will make submissions to two separate assignments on Gradescope. The steps needed for the two submissions are different, so please make sure to follow carefully the procedures outlined below.

PS 4: Problem 0

Submit your ps4pr0.pdf file using these steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps4 folder.

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

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

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

PS 4: Problems 1 and 2

IMPORTANT: If you chose to work on these pair-optional problems with a partner, only one person from the pair should submit the files, and that person should add the other person as a group member following step 6 below.

Submit your ps4pr1.py and ps4pr2.py files under the assignment labeled PS 4: Problems 1 and 2 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 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.

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 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.

6. If you worked with a partner and you are the one who is submitting the files:

   • Click on the Add Group Member link that appears below your name above the results of the Autograder.

   • In the pop-up box that appears, click on the Add Member link.

   • Type your partner’s name or choose it from the drop-down menu.

   • Click the Save button.

   • Check to ensure that your partner’s name now appears below your name above the results of the Autograder.

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

50 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 double_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 a new list in which all of the binary numbers have been doubled. For example:

   >>> double_rec(['1100', '10011', '101', '010'])
   result: ['11000', '100110', '1010', '0100']
   
   >>> double_rec(['01', '100', '11'])
   result: ['010', '1000', '110']
   

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

   Hint: Although you could in theory use your base-conversion functions as part of your solution, it isn’t necessary to do so. Rather, you should be able to easily double each bitstring by keeping in mind what you learned about left shifts.

2. Write a function double_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 a new list in which all of the binary numbers have been doubled. 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:

   >>> double_lc(['1100', '10011', '101', '010'])
   result: ['11000', '100110', '1010', '0100']
   
   >>> double_lc(['01', '100', '11'])
   result: ['010', '1000', '110']
   

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

3. Write a function num_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 bitstrings in the list that represent an even number. For example:

   >>> num_evens_rec(['1100', '10011', '101', '010', '110'])
   result: 3
   

   The above call returns 3 because two of the bitstrings in the list ('1100', '010' and '110') 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.

4. Write a function num_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:

   >>> num_evens_lc(['1100', '10011', '101', '010', '110'])
   result: 3
   

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

5. 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 6, 2025.