CS 111
Summer 2 2018

Problem Set 3

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.


due by 9:00 p.m. on Saturday, July 07, 2018


Problem 1: Thinking recursively

10 points; individual-only

Try to do this part before class!

Put your answers for this problem in a plain-text file named ps3pr1.txt.

Consider the following recursive function:

def mystery(a, b):
    if a == b:
        return a
    else:
        return b + mystery(a + 1, b - 2)
  1. Trace the execution of mystery(1, 7). You may use any reasonable approach, provided that you show all of the calls to the function.

  2. What is the value returned by mystery(1, 7)?

  3. During the execution of mystery(1, 7), stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to mystery(1, 7) is made from the global scope, and you should include the stack frame for the global scope in your count.

  4. Give an example of specific values of a and b that would produce infinite recursion, and explain why it would occur.

You may find it helpful to use the Python Tutor visualizer to build intuition about how recursion works, to check your answers to parts 1-3 of this problem, and to test and debug the functions that you write in the later problems. For example, to test the mylen function that we discussed in lecture, you could paste the following into the visualizer:

def mylen(s):
    if s == '':
        return 0
    else:
        len_rest = mylen(s[1:])
        return 1 + len_rest

test = mylen('cs111')
print('test is', test)


Problem 2: Fun with recursion, part I

40 points; pair-optional
See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

In this problem you will write several functions that employ the power of recursion!

In IDLE, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name ps3pr2.py. Make sure to specify the .py extension.

Important guidelines:

Here are the descriptions of the functions:

  1. Write a function copy(s, n) that takes as inputs a string s and an integer n, and that uses recursion to create and return a string in which n copies of s have been concatenated together.

    To force you to use recursion, you may not use the multiplication operator (*). Rather, you should use recursion to add together n copies of s. For example, 'hello'*3 is equivalent to 'hello'+'hello'+'hello', and you will need to use recursion to compute that sum.

    If n is less than or equal to 0, the function should return the empty string (i.e., the string '', which does not have any spaces between the quotes).

    Here are some test cases:

    >>> copy('da', 2)
    'dada'
    >>> copy('Go BU!', 4)
    'Go BU!Go BU!Go BU!Go BU!'
    >>> copy('hello', 1)
    'hello'
    >>> copy('hello', 0)
    ''
    >>> copy('hello', -7)
    ''
    

    This function is similar to the power function from lecture.

  2. Write a function compare(list1, list2) that takes as inputs two lists of numbers, list1 andlist2, and that uses recursion to compute and return the number of values in list1 that are larger than their corresponding value in list2. In other words, the function should compare list1[0] with list2[0], list1[1] with list2[1], list1[2] with list2[2], etc, and it should return the number of positions at which the value from list1 is larger than the value from list2. For example:

    >>> compare([5, 3, 7, 9], [2, 4, 7, 8])
    2
    

    The above call returns 2, because:

    • in position 0, 5 > 2
    • in position 1, 3 < 4
    • in position 2, 7 == 7
    • in position 3, 9 > 8

    Thus, there are two positions (0 and 3) at which the value from list1 is larger than the value from list2.

    Note that it is possible for the two lists to have different lengths, in which case the function should only compare the positions at which the two lists both have values.

    >>> compare([4, 2, 3, 7], [1, 5])      # 4 > 1; 2 < 5; can't compare 3 or 7
    1
    >>> compare([4, 2, 3], [1, 5, 0, 8])   # 4 > 1; 2 < 5; 3 > 0; can't compare 8
    2
    >>> compare([5, 3], [])
    0
    >>> compare([], [5, 3, 7])
    0
    

    This function is somewhat similar to the mylen function from lecture, but it needs to deal with lists instead of strings, and it needs to process two lists at the same time. You can find a modified version of mylen that handles both strings and lists here.

  3. Write a function letter_score(letter) that takes a lowercase letter as input and returns the value of that letter as a scrabble tile. If letter is not a lowercase letter from ‘a’ to ‘z’, the function should return 0. This function does not require recursion.

    Here is the mapping of letters to scores that you should use:

    letter scores

    For example:

    >>> letter_score('w')
    4
    >>> print(letter_score('q'))
    10
    >>> letter_score('%')      # not a letter
    0
    >>> letter_score('A')      # not lower-case
    0
    

    We encourage you to begin with the following template:

    def letter_score(letter):
        """ your docstring goes here """
        assert(len(letter) == 1)
    
        # put the rest of your function here
    

    Note that we begin with an assert statement that validates the input for the parameter letter. If the condition given to assert is not true–in this case, if the input provided for letter has a length other than 1–then assert will cause your code to crash with an AssertionError. Using assert in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

    Hints:

    • You will need to use conditional execution (if-elif-else) to determine the correct score for a given letter.

    • You can greatly reduce the number of cases if you use the in operator, which tests for the presence of one string in another. For example:

      >>> letter = 'a'
      >>> letter in 'happy'       # 'happy' does have an 'a'
      True
      >>> letter in 'recursion'   # 'recursion' does not have an 'a'
      False
      

      More generally, the in operator can be used to test for the presence of an element in any sequence – including a list. For example, given the variable letter above we could do:

      >>> letter in ['a', 'b', 'c']
      True
      
  4. Write a function scrabble_score(word) that takes as input a string word containing only lowercase letters, and that uses recursion to compute and return the scrabble score of that string – i.e., the sum of the scrabble scores of its letters. For example:

    >>> scrabble_score('python')
    14
    >>> scrabble_score('a')
    1
    >>> scrabble_score('quetzal')
    25
    

    Use your letter_score function and recursion to solve this problem. You may find it helpful to use the num_vowels function from lecture as a model. In that function, every vowel essentially had a value of 1, and every consonant had a value of 0. In this function, each letter has its letter score as its value.

  5. At the bottom of your ps3pr2.py file, add at least one test call for each of the functions that you wrote for this problem. For example:

    test1 = copy('da', 2)
    print('the first test returns', test1)
    


Problem 3: Fun with recursion, part II

50 points; individual-only

This problem provides more practice in writing recursive functions.

In IDLE, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name ps3pr3.py. Make sure to specify the .py extension. Follow the same guidelines that we gave you for problem 3, and make sure that all of your functions except one_dna_to_rna use recursion.

  1. Write a function double(s) that takes an arbitrary string s as input, and that uses recursion to construct and return the string formed by doubling each character in the string. Here are three examples:

    >>> double('hello')
    'hheelllloo'
    >>> double('python')
    'ppyytthhoonn'
    >>> double('')
    ''
    
  2. Write a function weave(s1, s2) that takes as inputs two strings s1 and s2 and uses recursion to construct and return a new string that is formed by “weaving” together the characters in the strings s1 and s2 to create a single string. In other words, the new string should alternate characters from the two strings: the first character from s1, followed by the first character from s2, followed by the second character from s1, followed by the second character from s2, etc. If one of the strings is longer than the other, its “extra” characters – the ones with no counterparts in the shorter string – should appear immediately after the “woven” characters (if any) in the new string.

    >>> weave('aaaaaa', 'bbbbbb')
    'abababababab'
    >>> weave('abcde', 'VWXYZ')
    'aVbWcXdYeZ'
    >>> weave('aaaaaa', 'bb')    # four extra 'a' characters at the end
    'ababaaaa'         
    >>> weave('aaaa', 'bbbbbb')  # two extra 'b' characters at the end
    'ababababbb'       
    >>> weave('aaaa', '')        # all of the 'a' characters are extra!
    'aaaa'       
    >>> weave('', 'bbbb')        # all of the 'b' characters are extra!
    'bbbb'       
    >>> weave('', '')        
    ''
    

    Hint: You will need more than one base case.

  3. Write a function index(elem, seq) that takes as inputs an element elem and a sequence seq, and that uses recursion to find and return the index of the first occurrence of elem in seq. The sequence seq can be either a list or a string. If seq is a string, elem will be a single-character string; if seq is a list, elem can be any value. Don’t forget that the index of the first element in a sequence is 0.

    Important notes:

    • If elem is not an element of seq, the function should return the special value None, which does not have any quotes around it.

    • You may not use the in operator in this function.

    Here are some examples:

    >>> index(5, [4, 10, 5, 3, 7, 5])
    2
    >>> index('hi', ['well', 'hi', 'there'])
    1
    >>> index('b', 'banana')
    0
    >>> index('a', 'banana')
    1
    >>> index('i', 'team')
    >>>
    

    Important: If you call your index function from the Shell and the function returns None, you will not actually see the None value after the function call. Instead, you will just see another Shell prompt, as shown above. To make sure that your function is returning None, you can either make the call as part of a print statement or compare the return value to None:

    >>> print(index('i', 'team'))
    None
    >>> index('i', 'team') == None
    True
    

    We recommend that you try both of these tests. Here are some other examples:

    >>> print(index('hi', ['hello', 111, True]))
    None
    >>> print(index('a', ''))      # the empty string 
    None
    >>> print(index(42, []))       # the empty list
    None
    

    Hints:

    • The closest model for this problem is the version of the mylen function that is able to handle both lists and strings.
    • You will need more than one base case for this function.
    • In the recursive case, the decision about what to return will need to take into account the result of the recursive call. As a result, it is especially important that you store in a variable the value that is returned by the recursive call.

DNA transcription! The last two functions are based on an incredible molecular feat called transcription, in which your cells create molecules of messenger RNA that mirror the sequence of nucleotides in your DNA. The RNA is then used to create proteins that do the work of the cell.

  1. Write a function called one_dna_to_rna(c) that takes as input a single-character string c representing a DNA nucleotide and returns the corresponding messenger-RNA nucleotide. Here are the DNA-to-RNA conversions:

    'A' in DNA becomes 'U' in RNA.
    'C' in DNA becomes 'G' in RNA.
    'G' in DNA becomes 'C' in RNA.
    'T' in DNA becomes 'A' in RNA.

    Any other input should return the empty string (''). This function does not require recursion.

    Here are some examples:

    >>> one_dna_to_rna('C')
    'G'
    >>> print(one_dna_to_rna('T'))
    A
    >>> one_dna_to_rna('X')
    ''
    >>> one_dna_to_rna('c')       # lower-case letters don't count
    ''
    

    We encourage you to begin with the following template:

    def one_dna_to_rna(c):
        """ your docstring goes here """
        assert(len(c) == 1)
    
        # put the rest of your function here
    

    Here again, we begin with an assert statement that validates the input for the parameter c. If the condition given to assert is not true–in this case, if the input provided for c has a length other than 0–then assert will cause your code to crash with an AssertionError. Using assert in this way can help you to find and debug situations in which you accidentally pass in incorrect values for the parameter of a function.

  2. Write a function called transcribe(s) that takes as input a string s representing a piece of DNA, and that uses recursion to construct and return a string representing the corresponding RNA. Any characters in the input that don’t correspond to a DNA nucleotide should not appear in the returned RNA string. (Note that if you implemented the previous function correctly, you shouldn’t need to do anything special here to ensure that non-DNA characters are removed.) For example:

    >>> transcribe('ACGT TGCA')
    'UGCAACGU'
    >>> transcribe('GATTACA')
    'CUAAUGU'
    

    Use your one_dna_to_rna function and recursion to solve this problem. As with the scrabble_score function, you may find it helpful to use the num_vowels function from lecture as a model, but in this case you will be adding together strings instead of numbers!

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3. In particular, you are encouraged to add test calls to the bottom of the file, although doing so is not required for this problem.


Submitting Your Work

You should use Apollo to submit the following files:

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.

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

Here are the steps:

  1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
  2. Find the appropriate problem set section on the main page and click “Upload files”.
  3. 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.
  4. Click the “Upload” button at the bottom of the page.
  5. 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.
  6. 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 above.

Note: If you encounter problems with Apollo, 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.