Problem Set 2

Part I due by 11:59 p.m. on Thursday, February 13, 2025
Part II due by 11:59 p.m. on Sunday, February 16, 2025

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 Gradescope, following the procedures found at the end of Part I and Part II.

Part I

Creating the necessary folder

1. If you haven’t already created a folder named cs111 for your work in this course, follow these instructions to do so.

2. Then create a subfolder called ps2 within your cs111 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

Problems 0, 1 and 2 will all be completed in a single PDF file. To create it, you should do the following:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps2pr012.

4. Add your work for Problems 0, 1 and 2 to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps2 folder. The resulting PDF file (ps2pr012.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

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 recently there has a great deal of focus on generative AI – the technology behind ChatGPT and other similar tools.

This week’s reading is a New York Times article about chatbots like ChatGPT. The reading is available here. If you can’t access the Times site, you can find a PDF version here.

After you have read the article, write a response that addresses the following prompt: What was the most interesting or important idea in this article for you – and why?

Important: Put your response in the copy of the ps2pr012 template that you created on Google Drive (see above).

As usual, 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

10 points; individual-only

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

Tracing Function Calls

Consider the following Python program:

def foo(a, b):
    c = bar(b + 1) 
    a = c + bar(a)
    return a

def bar(a):
    b = a - 2
    print('bar', a, b)
    return a + 1

a = 5
b = 2
print(a, b)
bar(a)
print(a, b)
b = foo(b, a)
print(a, b)

In the Problem 1 section of ps2pr012, we have provided tables for you to complete. We have started some of the tables for you. You should:

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

You may not need all of the rows provided in the tables.

Problem 2: Thinking recursively

10 points; individual-only

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, complete the template that we have provided in section 2-1 of ps2pr012. In particular, you should:

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

   • Begin each frame 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 frames 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.

Note: The original version of the template for ps2pr01 included a spot for an answer to problem 2-4 (i.e., part 4 of this problem). There is no problem 2-4 this semester, and we have updated the template accordingly. If you made a copy of the original template, you can simply ignore the section for problem 2-4.

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 3: More practice writing non-recursive functions

18 points; individual-only

This problem involves more practice in writing non-recursive functions. These functions should be written without the use of recursion.

In Spyder, open a new editor window using File -> New File, and save it to your ps2 folder using the name ps2pr3.py.

1. Write a function longer(s1, s2) that takes as inputs two string values s1 and s2, and that returns the string with
   the longer length. If the two strings have the same length, the function should return the first string. For example:

   >>> longer('computer', 'compute')
   result: 'computer'
   
   >>> longer('hi', 'hello')
   result: 'hello'
   
   >>> longer('begin', 'again')
   result: 'begin'
   

   Warning

   Make sure that your function returns the correct value rather than printing it. If your function is printing the return value, you won’t see an output prompt (the result: prompt above) before the return values. If you don’t see that prompt, 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, with the exception of the optional test functions that you may include for testing your code.

2. Write a function swap_halves(s) that takes a string input s and returns a string whose first half is s's second half and whose second half is s's first half. If len(s) (the length of s) is odd, the first half of the input string should have one fewer character than the second half, and thus the second half of the output string will be one character shorter in such cases. For example:

   >>> swap_halves('homework')
   result: 'workhome'
   
   >>> swap_halves('carpets')
   result: 'petscar'
   

   Hints:

   • We strongly recommend computing len(s)//2 (using the integer-division operator //) and storing the result in an appropriately named variable. You will need to use that value twice in your function, and using the variable in both places with save you from recomputing it.

   • We encourage you to use concrete cases to determine the logic of what the function needs to do. For example, consider the first test above:

     >>> swap_halves('homework')
     result: 'workhome'
     

     In this test case, the function needs to take the string 'homework' and create the string 'workhome'. In order to do so, it needs to extract substrings of the original string and concatenate them together.

     • What are the substrings that the function needs to extract in this concrete case?
     • What Python expressions would extract those substrings from the input string s (which in this case is the string 'homework')?
     • How are those expressions related to the value of len(s)//2 (which in this case is 4)?

     By asking questions like these for this test case and other concrete cases, you should be able to come up with the general expressions that you can use to construct the necessary substrings, and then use those substrings to construct the final return value.

3. Write a function repeat_one(values, index, num_times) that takes as inputs a list values, an integer index (which you may assume is a valid index for one of the elements in values), and a positive integer num_times, and that returns a new list in which the element at position index of values has been repeated num_times times. For example:

   >>> repeat_one([10, 11, 12, 13], 2, 4)   
   result: [10, 11, 12, 12, 12, 12, 13]
   

   In the above example, the second input is 2 and the third input is 4, so we take the element at position 2 of the original list (the 12) and repeat it 4 times.

   Other examples:

   >>> repeat_one([10, 11, 12, 13], 2, 6)    # repeat element 2 six times
   result: [10, 11, 12, 12, 12, 12, 12, 12, 13]
   
   >>> repeat_one([5, 6, 7], 1, 3)    # repeat element 1 three times
   result: [5, 6, 6, 6, 7]
   

   Here again, you should use concrete cases to figure out the logic!

Problem 4: Fun with recursion, part 1

12 points; individual-only

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

In Spyder, open a new editor window using File -> New File, and save it to your ps2 folder using the name ps2pr4.py.

Here are the descriptions of the functions:

1. Write a function mult(vals) that takes as input a list of one or more numbers vals and uses recursion to compute and return the value obtained by multiplying together all of the numbers in the list. For example:

   >>> mult([5, 3, 2])     # 5*3*2 = 30
   result: 30
   
   >>> mult([1, 2, 3, 4])  # 1*2*3*4 = 24
   result: 24
   
   >>> mult([3])
   result: 3
   

   You should assume that vals will never be empty.

   Hints:

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

   • The base case of the mylen function is an empty string or empty list. In this problem, we are assuming that the list that is passed into mult is never empty, and thus the base case is when the list has a length of 1, which is the smallest or simplest case.

   • Here is some pseudocode (i.e., a mixture of Python code and descriptive text) for this function:

     def mult(vals):
         """ docstring goes here """
         if the list vals has a length of 1:
             return _____
         else:
             mult_rest = mult(______)
             return ____________
     

     You should turn this pseudocode into Python code. In particular, you will need to turn the pseudocode for the original if statement into Python code, and replace the blanks that we have included with appropriate Python expressions.

   • To figure out the logic for what you need to do after the recursive call, use concrete cases! For example:

     • We know that mult([2, 5, 3]) should call mult([5, 3]).

     • What should each of these calls return, based on what this function is supposed to do?

     • How can we use the value returned by mult([5, 3]) to figure out what mult([2, 5, 3]) should return?

2. Write a function add_stars(s) that takes an arbitrary string s as input and uses recursion to form and return the string formed by adding a star (i.e., an asterisk character '*') between each pair of adjacent characters in the string. If the string has fewer than two characters, it should be returned without any changes. Here are three examples:

   >>> add_stars('hello')
   result: 'h*e*l*l*o'
   
   >>> add_stars('hangman')
   result: 'h*a*n*g*m*a*n'
   
   >>> add_stars('x')
   result: 'x'
   

   This function is somewhat similar to the remove_spaces function from Lab 3, because it needs to recursively create a new string from an existing string. However, your function will be simpler, because it won’t need to decide what to do after the recursive call returns.

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3.

Submitting your work for Part I

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

You will make submissions to two separate assignments on Gradescope. The steps needed for the two submissions are different, so please make sure to follow carefully the procedures outlined below.

PS 2: Problems 0-2
Submit your ps2pr012.pdf file using these steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file in your ps2 folder.

2. Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work.

PS 2: Problems 3 and 4
Submit your ps2pr3.py and ps2pr4.py files using these steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add both files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

Part II

Problem 5: Fun with recursion, part 2

20 points; pair-optional

This is the only problem 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 provides more practice in writing recursive functions.

In Spyder, open a new editor window using File -> New File, and save it to your ps2 folder using the name ps2pr5.py.

Follow the same guidelines that we gave you for Problems 3 and 4.

1. Write a function dot(vals1, vals2) that takes as inputs two lists of numbers, vals1 and vals2, and uses recursion to compute and return the dot product of those lists – i.e., the sum of the products of the elements in the same positions in the two lists. For example, the dot product of [1, 2, 3] and [4, 5, 6] is

   1*4 + 2*5 + 3*6 = 32
   

   If the two lists do not have the same length or if either list is empty, dot should return 0.0.

   Here are some other examples:

   >>> dot([5, 3], [6, 4])     # get a decimal because the base case returns 0.0
   result: 42.0
   
   >>> dot([1, 2, 3, 4], [10, 100, 1000, 10000])
   result: 43210.0
   
   >>> dot([5, 3], [6])
   result: 0.0
   

   Hints:

   • Here is some pseudocode (i.e., a mixture of Python code and descriptive text) that shows our recommended approach to this problem:

     def dot(vals1, vals2):
         """ docstring goes here """
         if the lists don't have the same length:
             return 0.0
         elif either list is empty:
             return 0.0
         else:
             dot_rest = dot(_____, ______)
             return ________________
     

   • To figure out the logic for what you need to do after the recursive call, use concrete cases! For a reminder of how to do so, see question 8 in the section on General Questions in the FAQ.

2. Write a function any_odd(vals) that takes as input a list of 0 or more numbers vals and uses recursion to determine if vals includes any odd numbers. It should return the boolean literal True if vals includes one or more odd numbers, and False otherwise. For example:

   >>> any_odd([6, 5, 2, 4])
   result: True
   
   >>> any_odd([6, 8, 3, 2, 7])
   result: True
   
   >>> any_odd([6, 8, 2])
   result: False
   
   >>> any_odd([])
   result: False
   

   Warning

   Your function must return a boolean value – either True or False, without any quotes around them. If you see quotes around the result when you make the calls above from the console, you must fix your function to return a boolean and not a string.

   Hints:

   • You will need two base cases:

     1. one base case for the smallest possible input

     2. one base case for when the first element of the list is odd; this case is a base case because you don’t need to reduce the problem any further in order to know what value to return.

     You must check for these base cases in the order given above. Otherwise, you can end up with an error!

   • Don’t forget that you can use the modulus operator (%) to test if an integer is odd or even.

3. Write a function process(vals) that takes as input a list of 0 or more integers vals and uses recursion to create and return a new list in which each odd element of the original list has been replaced with its square and each even element has been left unchanged. For example:

   >>> process([5, 4, 3, 2])
   result: [25, 4, 9, 2]
   

   Note that the two odd numbers from the original list (5 and 3), have been replaced with their squares (25 and 9). The other two numbers (4 and 2) have been left unchanged because they are even.

   Here are some other examples:

   >>> process([6, 3, 7])
   result: [6, 9, 49]
   
   :::python
   >>> process([])
   result: []
   

   Hints:

   • This function is somewhat similar to the replace function from lecture. That function recursively creates a new string from an existing string, whereas this function will recursively create a new list from an existing list.

   • In the recursive case, when you use concatenation to build a larger list, make sure that both sides of the + operator are lists. For example, if vals1 and vals2 are both lists of numbers, the following will not work:

     vals1[0] + vals2    # error: cannot add int to list
     

     Instead, you would need to do something like the following:

     [vals1[0]] + vals2
     

   • To figure out the logic for what you need to do after the recursive call, use concrete cases! For a reminder of how to do so, see question 8 in the section on General Questions in the FAQ.

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3.

Problem 6: Fun with recursion, part 3

25 points; individual-only

This problem provides more practice in writing functions, including three recursive functions.

In Spyder, open a new editor window using File -> New File, and save it to your ps2 folder using the name ps2pr6.py.

Follow the same guidelines that we gave you for Problems 3 and 4. For parts 2, 3 and 4, 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')
   result: 4
   
   >>> letter_score('q')
   result: 10
   
   >>> letter_score('%')      # not a letter
   result: 0
   
   >>> letter_score('A')      # not lower-case
   result: 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. For example:

     if letter in ['b', 'c', 'm', 'p']:   # letters with a score of 3
         return 3
     elif letter in ...
     

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')
   result: 14
   
   >>> scrabble_score('a')
   result: 1
   
   >>> scrabble_score('quetzal')
   result: 25
   

   In addition to calling itself recursively, the function must also call your letter_score function to determine the score of a given letter. Doing so will allow you to avoid repeating the long if-elif-else statement that is already present in letter_score. Indeed, the only if-else statement that you should need is the one that determines whether you have a base case or recursive case.

   See the FAQ for more help with this problem.

3. Write a function compare(s1, s2) that takes as inputs two strings s1 and s2 (which you can assume have the same length) and uses recursion to compare two strings and to return the number of positions at which they have different characters. For example:

   >>> compare('alien', 'allen')     # only position 2 is different
   result: 1
   
   >>> compare('alien', 'alone')     # the last 3 positions all differ
   result: 3
   
   >>> compare('same', 'same')       # no differences!
   result: 0
   

4. Write a function weave(vals1, vals2) that takes as inputs two lists vals1 and vals2 and uses recursion to construct and return a new list that is formed by “weaving” together the elements in the lists vals1 and vals2 to create a single list. The new list should alternate elements from the two lists: the first element from vals1, followed by the first element from vals2, followed by the second element from vals1, followed by the second element from vals2, etc. For example:

   >>> weave([1, 1, 1], [2, 2, 2])
   result: [1, 2, 1, 2, 1, 2]
   
   >>> weave([3, 4, 5, 6], [7, 8, 9, 0])
   result: [3, 7, 4, 8, 5, 9, 6, 0]
   

   If one of the lists is longer than the other, its “extra” elements – the ones with no counterparts in the shorter list – should appear immediately after the “woven” elements (if any) in the new list. For example:

   >>> weave([0, 0, 0, 0], [1, 1])     # two extra elements in first list
   result: [0, 1, 0, 1, 0, 0]
   
   >>> weave([2, 1, 0], [3, 4, 5, 6])  # one extra element in second list
   result: [2, 3, 1, 4, 0, 5, 6])
   
   >>> weave([1, 2], [])     # all of the first list's values are extra!
   result: [1, 2]
   
   >>> weave([], [3, 4, 5])  # all of the second list's values are extra!
   result: [3, 4, 5]
   
   >>> weave([], [])        
   result: []
   

   Hints:

   • You will need more than one base case.

   • Here again, when you use concatenation to build a larger list, make sure that both sides of the + operator are lists. See the note that accompanies the process function in the previous problem for more detail.

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3.

Submitting your work for Part II

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

Submit your ps2pr5.py and ps2pr6.py files using these steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add both files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.

Last updated on February 10, 2025.