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.

Part I

due by 11:59 p.m. on Thursday, February 15, 2018

Problem 0: Reading and response

5 points; individual-only

This week, we will begin a unit on the lower layers of abstraction within a computer. The unit will include a look at how circuits are designed to handle binary inputs and outputs. However, this approach–in which information is represented in binary within silicon circuits–is only one possible approach.

This week’s reading is an article from The Economist that provides a brief overview of the current state of the art in DNA-based computation.

The reading is available here.

After you have read the article, write a response that addresses–at least to some extent–both of the following prompts. Put your response in a file named ps3pr0.txt. Don’t forget that the file that you submit must be a plain-text file.

1. What was the most interesting or important idea in this article for you – and why?

2. Which homework problem that we’ve done so far would you describe as being closest to the kinds of problems solved by the DNA computers mentioned in the article? Why?

Once again, you only need to write a short paragraph (4-6 sentences). The important thing is that your response shows you have thought critically about the article and added your own experience or insights to its ideas.

Problem 1: Tracing list comprehensions and recursion

15 points; individual-only

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

1. Consider the following Python program:

   def mystery1(x):
       lc = [2*y - 1 for y in range(x)]
       return sum(lc)
   
   x = 5
   y = 4
   y = mystery1(y)
   print(x, y)
   x = mystery1(x)
   print(x, y)
   

   Trace the execution of this program. Your answer should include:

   • a table for the variables in the global scope that illustrates how their values change over time. You can begin it as follows:

       x  |  y
     -----------
       5  |  4
     

   • one or more separate tables that illustrate the changes in the local variables that belong to the function; you can either use a different table for each function call, or one table for the function as a whole.

     Your table(s) for the function should have the following columns:

       x  |  y  |  lc
     ------------------
          |     |
     

     In the column for lc, you should show the how the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

     We included a similar table in Problem Set 2.

   • a separate section that specifies the output of the program (i.e., the values that are printed).

2. Consider the following Python function:

   def mystery2(vals):
       """ takes a list of numbers and does something with them """
       scored_vals = [[x**2, x] for x in vals]
       best_pair = max(scored_vals)
       return best_pair[1]
   

   Trace the execution of the following call to this function.

   mystery2([-2, 1, -5, 4])
   

   Your answer should include:

   1. a table that illustrates the changes in the values of x and scored_vals as the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

   2. the value assigned to the variable bestpair

   3. the return value of the function call

3. Briefly describe what the function mystery2 (from the previous part of this problem) does in general. In other words, for an arbitrary list of numbers vals, what will mystery2 return?

4. Consider the following recursive function:

   def mystery3(s):
       """ takes a string s and does something with it """
       if len(s) <= 1:
           return ''      # the empty string, with nothing between the quotes
       else:
           result_rest = mystery3(s[1:])
           if s[0] == s[-1]:
               return result_rest
           else:
               return result_rest + s[0]
   

   Trace the execution of the following call to this function.

   mystery3('banana')
   

   Your answer should illustrate the sequence of function calls that are made – from the initial call to the base case. Include a separate section for each call, taking an approach that is similar to the one we have often used in lecture. Begin each section with the call itself (e.g., `mystery3(‘banana’)). Then include a line that explicitly states the value assigned to the parameter. Next, if the call is a base case, you can just show the value that is returned. If the call is a recursive case, you should show the recursive call and its result, along with the value that is ultimately returned. We also encourage you to use indenting to emphasize the way in which one call occurs in the context of prior calls.

   For example, recall the num_vowels function from lecture. When tracing the call num_vowels('ate'), you would start by getting all the way down to the base case:

   num_vowels('ate')
   -----------------
       s = 'ate'
       num_in_rest = num_vowels('te')
   
       num_vowels('te')
       ----------------
           s = 'te'
           num_in_rest = num_vowels('e')
   
           num_vowels('e')
           ---------------
               s = 'e'
               num_in_rest = num_vowels('')
   
               num_vowels('')
               --------------
                   s = ''
                   return 0
   

   Note that we have left blank lines between sections. Then, once you have reached the base case, you can go back and add in both the results of the recursive calls and the values returned by the earlier calls, using the space provided by the blank lines:

   num_vowels('ate')
   -----------------
       s = 'ate'
       num_in_rest = num_vowels('te') = 1
       return 1 + 1 = 2
   
       num_vowels('te')
       ----------------
           s = 'te'
           num_in_rest = num_vowels('e') = 1
           return 0 + 1 = 1
   
           num_vowels('e')
           ---------------
               s = 'e'
               num_in_rest = num_vowels('') = 0
               return 1 + 0 = 1
   
               num_vowels('')
               --------------
                   s = ''
                   return 0
   

   Take this same approach when tracing mystery3('banana').

5. What is the final result of the call mystery3('banana')?

Problem 2: Algorithm design

25 points; pair-optional

This is the only problem of the 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 provides additional practice with list comprehensions and recursion. It also provides an opportunity to use the list-of-lists technique that we discussed in lecture.

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

The guidelines that we gave you for Problem Set 2, problem 2 also apply here, except that you will be using list comprehensions for some of the functions. In particular, make sure that you use the exact function names that we have specified.

1. Write a function abs_list_lc(values) that takes as input a list of numbers called values, and that uses a list comprehension to create and return a list containing the absolute values of the numbers in values. For example:

   >>> abs_list_lc([-2, 5, 8, -3])
   [2, 5, 8, 3]
   

   Use the built-in abs function (which returns the absolute value of a single number), in conjunction with a list comprehension. This version of the function may not use recursion.

2. Write a function abs_list_rec(values) that takes as input a list of numbers called values, and that uses recursion to create and return a list containing the absolute values of the numbers in values. In other words, this function will do the same thing as the previous function, but it must use recursion instead of a list comprehension. For example:

   >>> abs_list_rec([-2, 5, 8, -3])
   [2, 5, 8, 3]
   

   Here again, you should use the built-in abs function, but in conjunction with recursion. This version of the function may not use a list comprehension.

For the following two functions of this problem set, one function must be written using a list comprehension and one function must be written using recursion. It is up to you to decide which technique you want to use for which function, but you cannot choose to implement both functions using the same technique.

3. Write a function called most_vowels(words) that takes a list of strings called words and returns the string in the list with the most vowels. You may assume that the strings only contain lowercase letters. For example:

   >>> most_vowels(['vowels', 'are', 'amazing', 'things'])
   'amazing'
   >>> most_vowels(['obama', 'bush', 'clinton'])
   'obama'
   

   The function that you write should use the num_vowels function from lecture as a helper function. Copy num_vowels into your ps3pr2.py file, adjusting the indentation as needed.

   Note: You don’t need to worry about cases in which two or more words are tied for the most vowels.

4. Write a function called num_multiples(m, values) that takes an integer m and a list of integers values and returns the number of integers in values that are multiples of m. For example:

   >>> num_multiples(5, [2, 15, 10])      # 2 of the values (15 and 10) are multiples of 5
   2
   >>> num_multiples(3, [12, 3, 6, 7, 9]) # 12, 3, 6 and 9 are multiples of 3
   4
   >>> print(num_multiples(9, [15, 18]))  # only 18 is a multiple of 9
   1
   

The last function of this problem does not require the use of either recursion or a list comprension. The implementation of this function only requires the use of conditional logic and variable assignment.

5. Write a function message(name, age) that takes a string name and an integer age and returns a string that is a personalized message based on the values of the two parameters.

   The string returned should begin with the value of name, and it should continue with a message that depends on the value of age as follows:

   age              message
   ---              -------
   < 1              very funny!
   1 - 9            you should not be using a computer!
   10 - 14          welcome to the dweeb years!
   15 - 17          get ready for the college essays!
   18 - 20          you have to wait x more years to be legal!
                    (where x is based on age -- see below)
   21 exactly       congrats! But be smart!
   22 - 29          downhill from here!
   >= 30            stinks for you!
   

   Examples:

   >>> message('Chris', 54)
   'Chris stinks for you!'
   >>> message('Mike', 18)
   'Mike you have to wait 3 more years to be legal!'
   >>> message('Jill', 20)
   'Jill you have to wait 1 more year to be legal!'
   >>> message('Perry', 17)
   'Perry get ready for the college essays!'
   

Part II

due by 11:59 p.m. on Sunday, October 18, 2018

Problem 3: Caesar cipher and decipher

25 points; individual-only

This problem asks you to write two functions using aspects of functional programming that we have covered in class: conditionals, recursion, and/or list comprehensions. The guidelines that we gave you for [Problem Set 2, problem 3][ps2pr3] also apply here, except you are allowed to use list comprehensions instead of recursion. In particular, make sure that you use the exact function names that we have specified.

Begin by downloading the file ps3pr3.py and opening it in IDLE. We have given you:

• a template for a helper function called rot that we recommend that you write in conjunction with your work on the first function below.
• another (already completed) helper function called letter_prob that you may find useful when writing the second function.

Here are the descriptions of the two functions:

1. Write a function encipher(s, n) that takes as inputs an arbitrary string s and a non-negative integer n between 0 and 25, and that returns a new string in which the letters in s have been “rotated” by n characters forward in the alphabet, wrapping around as needed. For example:

   >>> encipher('hello', 1)
   'ifmmp'
   >>> encipher('hello', 2)
   'jgnnq'
   >>> encipher('hello', 4)
   'lipps'
   

   Upper-case letters should be “rotated” to upper-case letters, even if you need to wrap around. For example:

   >>> encipher('XYZ', 3)
   'ABC'
   

   Lower-case letters should be “rotated” to lower-case letters:

   >>> encipher('xyz', 3)
   'abc'
   

   Non-alphabetic characters should be left unchanged:

   >>> encipher('#caesar!', 2)
   '#ecguct!'
   

   Hints/reminders:

   • You can use the built-in functions ord and chr convert from single-character strings to integers and back:

     >>> ord('a')
     97
     >>> chr(97)
     'a'
     

   • You can use the following test to determine if a character is between 'a' and 'z' in the alphabet:

     if 'a' <= c <= 'z':
     

     A similar test will work for upper-case letters.

   • We recommend writing a helper function rot(c, n) that rotates a single character c forward by n spots in the alphabet. We have given you a template for this helper function in ps3pr3.py that checks to ensure that c is a single-character string. We wrote rot13(c) in lecture; rot(c, n) will be very close to rot13(c)! You can test your rot(c, n) as follows:

     >>> rot('a', 1)
     'b'
     >>> print(rot('a', 1))
     b
     >>> rot('y', 2)
     'a'
     >>> rot('A', 3)
     'D'
     >>> rot('Y', 3)
     'B'
     >>> rot('!', 4)
     '!'
     

   • Once you have rot(c, n), you can write a recursive encipher function.

   Once you think you have everything working, here are three more examples to try:

   >>> encipher('xyza', 1)
   'yzab'
   >>> encipher('Z A', 2)
   'B C'
   >>> encipher('Caesar cipher? I prefer Caesar salad.', 25)
   'Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.'
   

2. Write a function decipher(s) that takes as input an arbitrary string s that has already been enciphered by having its characters “rotated” by some amount (possibly 0). decipher should return, to the best of its ability, the original English string, which will be some rotation (possibly 0) of the input string s. For example:

   >>> decipher('Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.')
   'Caesar cipher? I prefer Caesar salad.'
   

   Note that decipher does not take a number specifying the amount of rotation! Rather, it should determine the rotation (out of all possible rotations) that produces the most plausible English string. We have given you a helper function called letter_prob(c) that takes a single-character string c and returns a value that is based on the frequency with which that character appears in English texts. That function provides the basis for a number of possible approaches for judging the “Englishness” of a given rotation, but you are welcome to try an alternative approach. Use a short comment above your decipher function to describe your overall approach.

   Your function does not need to be perfect. Some strings have more than one English “deciphering.” In addition, it’s difficult if not impossible to handle very short strings correctly. However, your function should work almost all of the time on long stretches of English text (e.g., sentences of 8 or more words). You will not lose any credit for not getting the correct deciphering of a single word or short phrase.

   Here are two more examples:

   >>> decipher('Hu lkbjhapvu pz doha ylthpuz hmaly dl mvynla lclyfaopun dl ohcl slhyulk.')
   'An education is what remains after we forget everything we have learned.'
   >>> decipher('python')
   'eniwdc'
   

   Note that our version of decipher gets the second example wrong! (When you provide English text as the input, you should ideally get back the text itself–i.e., a string that has been deciphered using a rotation of 0–but that didn’t happen in this case, which is completely okay!) It’s possible that your version of decipher will return a different value here. It might even return 'python', but it’s okay if it doesn’t.

   Hints/reminders:

   • Since deciphering involves rotating the characters, you already have the function needed to create each of the possible decipherings!

   • We recommend that you start by using a list comprehension to create a list of all possible decipherings. You will consider all possible shifts – from 0 to 25 – that could be used to create a deciphering. Assign the result of this list comprehension to a variable.

   • Next, you should use the “list-of-lists” technique that we discussed in lecture to give each possible deciphering a score. The best_word function from lecture is a good example of this technique.

     As discussed above, the score that you assign to a given deciphering should provide some measure of its “Englishness.” You are welcome to write additional helper functions to assist you in the scoring and in the other steps involved.

   • After you have scored all of the options, you should choose the option with the highest score. Here again, the best_word function from lecture is a good model for this.

   • Once you think you have a working decipher, try it on the following string:

     'kwvozibctibqwva izm qv wzlmz nwz iv mfkmttmvb rwj'
     

Problem 4: More algorithm design!

30 points; individual-only

This problem asks you to write three additional functions using the functional-programming techniques that we have discussed in lecture.

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

In writing the functions described below, you should continue to follow the guidelines from problem 2.

Here are the descriptions of the functions:

1. Write a function rem_last(elem, values) that takes as inputs a value elem and a list values and that uses recursion to create and return a version of values in which the last occurrence of elem (if any) has been removed. For example:

   >>> rem_last(3, [2, 3, 1, 3, 4, 3, 5])
   [2, 3, 1, 3, 4, 5])
   >>> rem_last(0, [1, 0, 1, 0, 0])
   [1, 0, 1, 0]
   >>> rem_last(1, [1, 0, 1, 0, 0])
   [1, 0, 0, 0]
   >>> rem_last(2, [1, 0, 1, 0, 0])    # no occurrences
   [1, 0, 1, 0, 0]
   >>> rem_last(2, [])
   []
   

   Notes:

   • In the recursive call, you will need to take a different approach to reducing the problem than we have typically taken when recursively processing a list.

   • To figure out the logic of the function, we strongly encourage you to begin by considering concrete cases. Ask yourself the types of design questions that we have asked in lecture and lab, and use the answers to those questions to determine what the function should do.

   • This function is somewhat similar to the rem_first function that we discussed in lecture, although that function removed the first occurrence of an element rather than the last. If you base your code on rem_first, make sure to change its name to rem_last – both in the function header, and in the recursive call!

2. Write a function jscore(s1, s2) that takes two strings s1 and s2 as inputs and returns the Jotto score of s1 compared with s2 – i.e., the number of characters in s1 that are shared by s2. The positions and the order of the shared characters within each string do not matter. Repeated letters are counted multiple times, as long as they appear multiple times in both strings. For example:

   >>> jscore('diner', 'syrup')            # just the 'r'
   1
   >>> jscore('always', 'bananas')         # two 'a's and one 's'
   3
   >>> jscore('always', 'walking')         # one 'a', 'l', and 'w'
   3
   >>> jscore('recursion', 'excursion')    # everything but the 'r' in s1 is shared by s2
   8
   >>> jscore('recursion', '')             # 0 because s2 is empty
   0
   

   Notes/hints:

   • Unlike the words in traditional Jotto, which always have five letters, there are no restrictions on the lengths of the input strings s1 and s2.

   • If either s1 or s2 is the empty string, the Jotto score is 0.

   • You can write the function any way you like as long as you use functional programming.

   • We encourage you to consider using one or more helper functions. In particular, one possible approach involves using a function like the rem_first function that we considered in lecture. However, you would need to rework that function so that it operates on a string rather than a list.

   • This line turns out to be useful:

     if s1[0] in s2:
     

3. Write a function lcs(s1, s2) that takes two strings s1 and s2 and returns the longest common subsequence (LCS) that they share. The LCS is a string whose letters appear in both s1 and s2; these letters must appear in the same order in both s1 and s2, but not necessarily consecutively. For example:

   >>> lcs('human', 'chimp')          # 'h' comes before 'm' in both strings
   'hm'
   >>> lcs('gattaca', 'tacgaacta')
   'gaaca'
   >>> lcs('wow', 'whew')
   'ww'
   >>> lcs('', 'whew')                 # first string is empty
   ''
   >>> lcs('abcdefgh', 'efghabcd')     # tie! 'efgh' would also be fine
   'abcd'
   

   Notes/hints:

   • If either s1 or s2 is the empty string, the LCS is also the empty string.

   • If there are ties for the LCS, any one of the ties is acceptable. In the last example above, a return value of 'efgh' would also have been fine, because both 'abcd' and 'efgh' are common subsequences of the two strings, and both of these subsequences have a length of 4.

   • Here’s one possible strategy for the recursive case (after you have checked for your base case(s)):

     • If the first characters in the two strings match, include that character in the LCS, and process the remaining characters of the two strings.

     • If the first characters don’t match, make two recursive calls: one that eliminates the first character in s1, and one that eliminates the first character in s2. Your code will look something like this:

       result1 = lcs(s1[1:], s2)
       result2 = lcs(___, ___)
       

       where you should fill in the blanks in the appropriate way.

     • Return the better of these two results.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps3pr0.txt file containing your response to the reading for Problem 0
• your ps3pr1.txt file containing your answers for Problem 1
• your ps3pr2.py file containing your code for Problem 2; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner
• your modified ps3pr3.py file containing your code for Problem 3
• your ps3pr4.py file containing your code for Problem 4

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. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. 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.
5. Click the Upload button at the bottom of the page.
6. 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.
7. 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.