Problem Set 4 FAQ

General questions
Problem 1
Problem 3

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

You may also find it helpful to consult the general questions from the FAQs for PS 1-3, and the page we have assembled with info about common Python errors.

General questions

One of my functions that processes a string seems to have the correct logic, but it returns the wrong answer. Do you have any suggestions?

We’ve noticed many problems that stem from comparisons involving the wrong type of value. Python will not throw an error in these cases, which can make the problem especially difficult to diagnose.

In general, if you’re checking the elements of a string, you must compare them to other string values as well. A common problem that we’ve seen is that people will check to see if a character in the string is either a 0 or a 1 with code that looks like this:
```
# this is incorrect!
if b[0] == 0:        # is the first character in b a zero?
    return ...
```
This is incorrect because we’re comparing a string with an integer. The string '0' will never equal the integer 0, so the boolean expression will never return True.

Instead, we need to compare the first character of b with a string. The following code shows the correct way to check a character in b.
```
# this is correct
if b[0] == '0':      # note the quotes around the 0
    return ...
```
Make sure that all comparisons you make with strings are done with strings and not integers.
How can I figure out where the problem is in one of my recursive methods?

Here are three things that can help:
- Use the Python Tutor visualizer to step through your function as it executes on one or more test cases. See our description of how to use this tool at the end of Problem Set 1, problem 3.
- Add temporary print statements to your function. It helps if you can put a print statement at the very beginning of the function to print the values of the inputs, and then another print statement before each return statement to print the value being returned. For example, here is a version of the mylen function from lecture that does this:
```
def mylen(s):
    """ returns the length of the sequence s
        input: s is a sequence (a string or list)
    """
    print('starting the call mylen(' + s + ')')    # add one print at the start
    if s == '' or s == []:
        print('mylen(' + s + ') is returning 0')   # print before returning
        return 0
    else:
        len_rest = mylen(s[1:])
        print('mylen(' + s + ') is returning', 1 + len_rest)   # here, too!
        return 1 + len_rest
```
  Make sure to remove the print statements before you submit your work!
- Trace through concrete cases. For example, let’s say that you’re trying to determine the logic for the recursive case of bin_to_dec. We have required that you process the input string from right-to-left. That means that you should be making your recursive call on a slice that includes everything but the last digit.
  
  Consider the initial call bin_to_dec('1101'). It will result in a series of calls:
```
bin_to_dec('1101')
bin_to_dec('110')
bin_to_dec('11')
bin_to_dec('1')      # base case
```
  And because each of these calls must return the correct value for its input, you can write down the correct return value for each call:
```
bin_to_dec('1101') --> 13
bin_to_dec('110')  --> 6
bin_to_dec('11')   --> 3
bin_to_dec('1')    --> 1
```
  Given these return values, ask yourself what you need to do with the value that is returned by the recursive call. How can you use the solution to the smaller subproblem to to determine the solution to the original problem? For the example above, how could you use the solution to bin_to_dec('11') to determine the solution to bin_to_dec('110')? How could you use the solution to bin_to_dec('110') to determine the solution to bin_to_dec('1101')?
  
  A similar procedure can be followed for any recursive function. Once you have determined the base cases and the way in which you plan to reduce the original problem to one or more subproblems, write down the series of calls that will result from concrete cases, and ask yourself the types of questions that we mentioned above.

Problem 1

How do I get started on dec_to_bin?

Remember that dec_to_bin is a function that takes an integer n and returns a string of ‘0’ and ‘1’ characters that represents n in binary. This means you should build your result by concatenating strings, not by adding integers together. Remember also that you can’t add an integer to a string.
```
'0101' +  0   # wrong
'0101' + '0'  # correct
```
You should start with base case(s) that handle an n value of either 0 or 1, because you already know the binary string that each of those values maps to. Make sure that you return a string in these cases and not an integer.

For the recursive case, review the lecture notes on binary numbers to see the algorithm we can use to compute the binary string. This can be done by computing only the right-most digit and then delegating the rest of the work to recursion. What number can you pass to the recursive call to dec_to_bin so that you get the binary string representing the rest of n? You can determine this number by reviewing the material in the lecture notes on binary shifts and the decimal-to-binary algorithm.
How do I get started on bin_to_dec?

The lecture notes on binary numbers will help for bin_to_dec as well. In this function, you will want to set up your base case(s) to check for the strings '0' or '1', and then handle all other numbers in your recursive case.

Remember that we want to work on the binary string from the right to the left. This means that in your recursive case you need to determine the rightmost bit of the number and compute the decimal number belonging to the rest of the bits in the string. With these two numbers, you can make the decimal representation of the binary string you are given.

Problem 3

One of my functions for this problem seems to have the correct logic, but it returns the wrong answer. Do you have any suggestions?

Check to make sure that your boolean expressions are correct. In particular, if you are using the and operator or the or operator, make sure that both sides of the operator are true boolean expressions – i.e., expressions that evaluate to True or False.

For example, let’s say that we wanted to check if variables x and y are both 10. The following does not work:
```
if x and y == 10:           # wrong!
```
Although Python doesn’t complain about this code, the expression after the if doesn’t actually check if both x and y are 10, because the left-hand side of the and operator just includes the variable x, which doesn’t compare x to anything.

Here’s a corrected version:
```
if x == 10 and y == 10:     # correct!
```
Note that both sides of the and operator are now expressions that evaluate to True or False, as they should be.

You may also want to review the answer to the first general question at the start of this FAQ.
I’m having trouble getting started on the bitwise_and problem. Do you have any suggestions?

Take a look at the optional Lab 4b, which includes a similar problem.
How can we handle the case of add_bitwise in which we need to carry a one?

In add_bitwise you add two binary strings together one digit at a time. In the case that the rightmost bits of both strings are ‘1’ and ‘1’, you will need to carry a one to the next column. Since we are implementing add_bitwise recursively, we can only work on one column at a time.

To see how to add the one to the result, consider an example of using elementary-school arithmetic with binary numbers:
```
  1011
+ 0101
------
```
When we add the two ones on the right together, we get 0, but we have to carry the 1 to the next column. If you did this by hand, you would probably write the following.
```
    1
  101 1
+ 010 1
-------
      0
```
When doing things by hand, this is fine, but it doesn’t really work recursively.

Let’s rearrange the addition to something we could do in our situation. That is, we first call add_bitwise to sum the rest of the binary strings without the carry bit, and then we can use a second call to add_bitwise to add in the carry bit.
```
  101 1
+ 010 1
-------
  111 0
+   1 
-------
 1000 0
```
This adds the carry bit to the rest of the binary result, and so we can just concatenate our zero bit to that string, and we’re done!

We provided additional detail about this problem in lecture.
I’m still having trouble with add_bitwise(). Any other suggestions?

First, we strongly recommend that you make the initial recursive call–the one that adds everything but the rightmost bits–at the very start of your recursive case, and store its return value in a variable. It should look something like this:
```
def add_bitwise(b1, b2):
    """ your docstring goes here """
    if ...   
        # handle your base case(s) here
    else:
        sum_rest = add_bitwise(..., ...)

        # now decide what you will return
```
Note that we make the recursive call as the first statement in the recursive case, and store its return value in the variable sum_rest. You can then decide what you will return, building the return value on the value of sum_rest.

As the problem set suggests, adding the carry bit should be done using a second recursive call. In the example from the previous question, we saw that we needed to add a carry bit of '1' to the value '111'. How could you construct a recursive call to add_bitwise() to add those two numbers? Now modify that specific recursive call so that it works whenever you have a carry bit. What should you replace the '111' with in the recursive call to make it work for any situation involving a carry bit?