Problem Set 2

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 8, 2018

Problem 0: Reading and response

5 points; individual-only

Artificial intelligence (AI for short) is one of the many subfields of computer science. Researchers in AI focus on many different types of problems, but one of the goals of AI since its inception has been to build machines that can interact “intelligently” with human beings.

This week’s reading is a New York Times article about IBM’s Watson, a system that defeated two human champions at “Jeopardy!” in 2011.

The reading is available here. If you can’t access the Times site, you can find a PDF version here. We also encourage you to play against Watson yourself!

After you have read the article and interacted with Watson, write a response that addresses–at least to some extent–all of the following prompts. Put your response in a file named ps2pr0.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. What is an application that (in your opinion) Watson’s technology might be able to contribute to? Alternatively, do you feel Watson’s capabilities will not make much of an impact?

3. Whether or not you had the chance to interact with Watson, comment on your sense of the similarities and/or differences between Watson-style and human-style thinking.

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 function calls and conditional execution

15 points; individual-only

To prepare for this problem, we encourage you to review the following videos as needed:

• Tracing Function Calls
• Conditional Execution

Put your answers in a plain-text file named ps2pr1.txt.

1. Consider the following Python program:

   def decide(a, b, c):
       if a <= c:
           if b > c:
               a = a * 3
           else:
               b = b + 4
       elif b <= c:
           if b == a:
               c = c + 2
           else:
               a = a + 3
       b = b * 5
       print('decide', a, b, c)
       return b
   
   a = 1
   b = 3
   c = 2
   print(a, b, c)
   decide(a, b, c)
   print(a, b, c)
   c = decide(b, a, a)
   print(a, b, c)
   

   Copy the tables shown below into your text file for this problem, and complete them to illustrate the execution of the program.

   global variables (ones that belong to the global scope)
     a  |  b  |  c
   -----------------
     1  |  3  |  2   
        |     |
   
   local variables (ones that belong to the decide function)
     a  |  b  |  c
   -----------------
        |     |  
        |     |
   
   output (the lines printed by the program)
   ------
   1 3 2
   

   Note that you must include three tables: one for the global variables (the ones that belong to the global scope), one for the local variables (the ones that belong to the function decide), and one for the output of the program. Don’t forget to follow the rules for variable scope.

   We have started the first and third tables for you. You should:

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

   You should add rows to the tables as needed.

2. Consider the following Python program:

   def mystery(vals):
       a = vals[0]
       b = vals[1]
       c = vals[2]
       if a >= b:
           if b < c:
               print('round')
           else:
               print('found')
       elif b >= c:
           print('mound')
           if b < a:
               print('pound')
           elif a < c:
               print('ground')
           elif b == c:
               print('wound')
       else:
           if a == c:
               print('hound')
           print('zounds')
       print('redound')
   

   State the output that would result from each of the following function calls:

   1. mystery([5, 7, 1])
   2. mystery([4, 4, 6])
   3. mystery([8, 6, 3])
   4. mystery([1, 2, 3])
   5. mystery([2, 8, 8])

   Note: You can check your answers by copying the program into a new window in IDLE, saving it, and running it. However, make sure that you understand why you end up with the outputs that you do!

Problem 2: More practice with writing functions

10 points; individual-only

This problem involves more practice in writing non-recursive functions. These functions should be written without the use 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 ps2pr2.py. Make sure to specify the .py extension.

1. Write a function mirror(s) that takes as input a string s and returns a mirrored version of s that is twice the length of the original string. For example:

   >>> mirror('bacon')
   'baconnocab'
   >>> print(mirror('XYZ'))
   XYZZYX
   

   Hint: Use skip-slicing!

2. Write a function is_mirror(s) that takes as input a string s and returns True if s is a mirrored string (i.e., a string that could have been produced by your mirror function) and False otherwise. Examples:

   >>> is_mirror('baconnocab')
   True
   >>> print(is_mirror('baconnoca'))
   False
   

   Warning

   Your function should return a boolean value – either True or False, without any quotes around them. If you see quotes around the result when you make the first call above from the Shell, you must fix your function to remove the quotes.

Problem 3: Thinking recursively

10 points; individual-only

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

Consider the following recursive function:

def mystery(a, b):
    if a == b:
        return a
    else:
        myst_rest = mystery(a + 1, b - 2)
        return b + myst_rest

1. Trace the execution of the following call to this function

   mystery(1, 7)
   

   To do so, begin by copying the following template into that file:

   mystery(1, 7)
   -------------
       a = 1
       b = 7
       myst_rest = mystery(..., ...) = ...
       return ...
   
       mystery(..., ...)
       -----------------
           a = ...
           b = ...
           myst_rest = ...
           return ...
   

   Complete this template so that it traces the series of recursive calls. In particular, you should:

   • Include a separate section for each call. We have filled in some of the components of the first two calls for you. You should replace each ... with the appropriate integer, and you should add sections for additional calls as needed, until you reach the base case.

   • Begin each section with lines that explicitly state the values assigned to the parameters, as we have done for the first call.

   • Next, if the call is a base case, you can simply show the value that is returned (omitting the line for myst_rest). If the call is a recursive case, you should show the recursive call on the line for myst_rest.

   • Once you have reached the base case, you should work your way back through the sections for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_rest) and the value returned by the call itself.

   We took a similar approach to tracing recursion in Lab 3.

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 4: Fun with recursion, part I

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

In this problem you will write two 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 ps2pr4.py. Make sure to specify the .py extension.

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

   Warning

   Remember that your functions should return the correct value rather than printing it. If your function is printing the return value, you won’t see the quotes around the returned strings when you call the function on its own from the Shell, and you will see the word None as part of the output for the second test above. If this happens, you must fix your function so that it uses a return statement rather than a print statement. This same warning applies to all of the functions that you will write for this assignment unless we explicitly say otherwise.

2. Write a function sum(values) that takes as an input a list of integers values, and that uses recursion to compute and return the sum of all the integers in the list:

   >>> sum([1, 2, 3, 4, 5])
   15
   >>> sum([3, 5, 4])
   12
   >>> sum([])
   0
   

3. At the bottom of your ps2pr4.py file, add a test() function that includes at least one test call for each of the functions that you wrote for this problem. For example:

   def test():
       """ test function for the function(s) above """
       test1 = copy('da', 2)
       print('the first test returns', test1)
   

   This function does not require recursion. Also, remember that a test function like this one does not need to return anything itself, because its only purpose is to call the other functions and print the results of those calls. Calling this test function from the Shell will allow you to see the results of the test calls and ensure that they are correct.

Part II

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

Problem 5: Tracing functions and list comprehensions

10 points; individual-only

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

1. Consider the following Python program:

   def foo(a):
       b = bar(a) + bar(a - 2)
       print('foo:', a, b)
       return b
   
   def bar(b):
       a = b * 2
       print('bar:', a, b)
       return a
   
   a = 3
   b = 2
   print(a, b)
   bar(b)
   print(a, b)
   a = foo(a)
   print(a, b)
   

   Copy the tables shown below into your text file for this problem, and complete them to illustrate the execution of the program.

   global variables (ones that belong to the global scope)
     a  |  b
   -----------
     3  |  2
        |
   
   foo's local variables
     a  |  b
   -----------
        |
        |
   
   bar's local variables
     a  |  b
   -----------
        |
        |
        |
   
   output (the lines printed by the program)
   ------
   3 2
   

Note that you must include four tables: one for the global variables (the ones that belong to the global scope), one for the local variables that belong to the function foo, one for the local variables that belong to the function bar, and one for the output of the program. Don’t forget to follow the rules for variable scope.

We have started the first and fourth tables for you. You should:

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

You should add rows to the tables as needed.

2. Consider the following Python program:

   def mystery(x):
       lc = [y % 3 for y in range(x)]   
       return sum(lc)
   
   x = 6
   y = 2
   print(x, y)
   y = mystery(y)
   print(x, y)
   x = mystery(x)
   print(x, y)
   

   Copy the tables shown below into your text file for this problem, and complete them to illustrate the execution of the program.

   global variables (ones that belong to the global scope)
     x  |  y  
   -----------
     6  |  2  
        |
   
   local variables (ones that belong to the mystery1 function)
     x  |  y  |  lc
   -----------------
        |     |  
        |     |
   
   output (the lines printed by the program)
   ------
   6 2
   

Note: that you must include three tables: one for the global variables (the ones that belong to the global scope), one for the local variables (the ones that belong to the function mystery1), and one for the output of the program. Don’t forget to follow the rules for variable scope.

We have started the first and third tables for you. You should:

• complete the first table so that it illustrates how the values of the global variables change over time

• complete the second table so that it illustrates how the values of the local variables change over time. 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. For example, if we were tracing the list comprehension

  lc = [2*x for x in range(3)]
  

  the table would look like this:

    x  |  lc
  ------------
    0  | [0,
    1  | [0, 2,
    2  | [0, 2, 4]
  

• complete the last table so that it shows the output of the program

You should add rows to the tables as needed.

Problem 6: Writing list comprehensions

15 points; individual-only

Begin by downloading the file ps2pr6.py and opening it in IDLE.

1. LC puzzles! You will see that the file includes several incomplete list comprehensions. Complete them by filling in the blanks to produce the results specified below.

   1. Complete the following list comprehension

      lc1 = [            for x in range(5)]
      

      so that it produces the list [0, 2, 4, 6, 8].

   2. Complete the list comprehension shown below

      words = ['hello', 'world', 'how', 'goes', 'it?']
      lc2 = [            for w in words]
      

      so that it produces the list ['e', 'o', 'o', 'o', 't'].

   3. Complete the following list comprehension

      lc3 = [            for word in ['hello', 'bye', 'no']]
      

      so that it produces the list ['olleholleh', 'eybeyb', 'onon']. Hint: Use skip-slicing.

   4. Complete the following list comprehension

      lc4 = [            for x in range(1, 10) if               ]
      

      so that it produces the list [4, 16, 36, 64]. Note that you need to fill in two blanks for this one: the expression before the for, and the expression after the if.

   5. Complete the following list comprehension

      lc5 = [            for c in 'bu be you']
      

      so that it produces the list [True, True, False, True, False, False, False, False, True]. Note that the expression 'bu be you' is a string, not a list.

   Test your list comprehensions by running ps2pr6.py and checking to see that the correct values are printed.

The next two parts of the problem involve writing functions. You should continue to follow the guidelines from problem 2, but you should use list comprehensions and not recursion.

2. Write a function called powers_of(base, count) that takes as inputs a number base and a positive integer count, and that uses a list comprehension to construct and return a list containing the first count powers of base, beginning with the 0th power. For example:

   >>> powers_of(2, 5)        
   [1, 2, 4, 8, 16]
   >>> print(powers_of(3, 4))
   [1, 3, 9, 27]
   

   Warning

   Make sure that your function returns the correct value rather than printing it. If your function is printing the return value, you will see the word None as part of the output for the second test above. If you are seeing None in your output, you must fix your function so that it uses a return statement rather than a print statement.

   Don’t forget to include a docstring!

3. Write a function called shorter_than(n, wordlist) that takes as inputs an integer n and a list of strings wordlist, and that uses a list comprehension to construct and return a list consisting of all words from wordlist that are shorter than n. For example:

   >>> shorter_than(4, ['only', 'recursion', 'on', 'the', 'brain'])
   ['on', 'the']       
   >>> cities = ['Boston', 'Chicago', 'Washington', 'Houston']
   >>> shorter_than(7, cities)
   ['Boston']
   >>> shorter_than(6, cities)
   []
   

   Hint: Your list comprehension will need an if clause.

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

Problem 7: Fun with recursion, part II

20 points; individual-only

This problem provides more practice in writing functions, including two 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 ps2pr7.py. Make sure to specify the .py extension.

Follow the same guidelines that we gave you for Problem 2. For parts 2 and 3, you must use recursion.

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

   

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

   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
     

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

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

   • 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')
   -1
   >>> print(index('hi', ['hello', 111, True]))
   -1
   >>> print(index('a', ''))      # the empty string 
   -1
   >>> print(index(42, []))       # the empty list
   -1
   

   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.

4. At the bottom of your ps2pr7.py file, add a test() function that includes at least one test call for each of the functions that you wrote for this problem. For example:

   def test():
       """ test function for the functions above """
       test1 = letter_score('w')
       print('the first test returns', test1)
   

   This function does not require recursion. Also, remember that a test function like this one does not need to return anything itself, because its only purpose is to call the other functions and print the results of those calls. Calling this test function from the Shell will allow you to see the results of the test calls and ensure that they are correct.

Don’t forget that you can also test your functions using the other approach mentioned at the start of Problem 2. You may also find it helpful to use the Python Tutor Visualizer to trace through the execution of your functions, as described at the end of Problem 3.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps2pr0.txt file containing your response to the reading for Problem 0
• your ps2pr1.txt file containing your answers for Problem 1
• your ps2pr2.py file containing your answers for Problem 2
• your ps2pr3.txt file containing your code for Problem 3
• your ps2pr4.py file containing your answers for Problem 4 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 as well as their lecture section if different from yours
• your ps2pr5.txt file containing your code for Problem 5
• your modified ps2pr6.py file containing your code for Problem 6
• your ps2pr7.py file containing your code for Problem 7

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.