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

In Spyder, use the File->New File menu option to open a new editor window for your code, and save it using the name ps4pr1.py.

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.

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, use the File->New File menu option to open a new editor window for your code, and save it using the name ps4pr2.py.

The guidelines that we gave you for Problem Set 2, Problem 3 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.

1. Write a function add(b1, b2) that takes as inputs two strings b1 and b2 that represent binary numbers. The function should compute the sum of the numbers, and return that sum in the form of a string that represents a binary number. For example:

   >>> add('11', '1') result: '100' >>> add('11100', '11110') result: '111010' 

   In this function, you should not need to use recursion or to perform any binary arithmetic. Rather, you must 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, add the resulting decimal numbers, and then convert the resulting sum 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_sum = the binary value of (n1 + n2) (use your other function!) return b_sum 

2. Write a function increment(b) that takes an 8-character string representation of a binary number and returns the next larger binary number as an 8-character string. For example:

   >>> increment('00000000') result: '00000001' >>> increment('00000111') result: '00001000' >>> increment('11111111') result: '00000000' 

   Notes/hints:

   • As shown in the last example above, you will need a special case for when the input is '11111111'. This is the largest binary number that can be represented using 8 bits, so incrementing it causes the value to wrap around to give you '00000000'. Your function should start by testing for this special input, and it should handle it by simply returning the appropriate value.

   • Here again, you should not use recursion or perform any binary arithmetic. Rather, you must make use of the conversion functions that you wrote for Problem 1.

   • 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 result, and store that result in a variable.

     • Determine the length of the result and store that length in a variable.

     • If the length of the result is less than 8 bits, 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.