Problem Set 2

Part I due by 11:59 p.m. on Thursday, September 26, 2024
Part II due by 11:59 p.m. on Sunday, September 29, 2024

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

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

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 = 3
b = 7
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 b * 2
    else:
        myst_rest = mystery(a * 2, b - 2)
        return a + 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.

You may find it helpful to use the Python Tutor visualizer to strengthen your 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 compare(s1, s2) that takes as inputs two string values s1 and s2, and that uses conditional execution to determine and return the string that comes later in the dictionary (i.e., the string that is greater according to the > operator).

   For example:

   >>> compare('program', 'code')   # 'program' > 'code'
   result: 'program'
   
   >>> compare('code', 'guru')      # 'guru' > 'code'
   result: 'guru'
   

   If the two inputs represent the same string, the function should return it:

   >>> compare('hey', 'hey')
   result: 'hey'
   

   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 combine(s1, s2, n) that takes as inputs two strings s1 and s2 and an integer n, and that returns a new string in which the last n characters of s1 are followed by the first n characters of s2. For example:

   >>> combine('computer', 'science', 3)
   result: 'tersci'
   
   >>> combine('python', 'code', 2)
   result: 'onco'
   

   If either string (s1 or s2) does not have at least n characters, you should use all of its characters:

   >>> combine('amazing', 'you', 4)
   result: 'zingyou'
   
   >>> combine('go', 'terriers', 5)
   result: 'goterri'
   

   Hint: 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:

   >>> combine('computer', 'science', 3)
   'tersci'
   

   In this test case, the function needs to take the strings 'computer' and 'science' and create the string 'tersci'. In order to do so, it needs to extract substrings of the original strings 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 s1 (which in this case is the string 'computer') and the input string s2 (which in this case is the string 'science')?
   • How are those expressions related to the value of the third input n (which in this case is 3)?

   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 reverse_n(vals, n) that takes as inputs a list vals and an integer n, and that constructs and returns a new list in which the first n values of vals are reversed and all other values from vals remain in their original positions. For example:

   >>> reverse_n([1, 2, 3, 4, 5, 6], 3)
   result: [3, 2, 1, 4, 5, 6]    # reversed the first 3 values
   
   >>> reverse_n([1, 2, 3, 4, 5, 6], 4)
   result: [4, 3, 2, 1, 5, 6]    # reversed the first 4 values
   
   >>> reverse_n([10, 20, 30, 40], 2)
   result: [20, 10, 30, 40]      # reversed the first 2 values
   

   If n is greater than or equal to the length of vals, the entire list should be reversed:

   >>> reverse_n([10, 20, 30, 40], 6)
   result: [40, 30, 20, 10]      # 6 >= 4, so reversed entire list
   

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 sum_squares(vals) that takes as input a list of numbers vals and uses recursion to compute and return the sum of the squares of the individual numbers in the list. For example:

   sum_squares([2, 5, 3])
   

   should recursively compute

   2*2 + 5*5 + 3*3
   

   and return the resulting value of 38.

   Here are two more examples:

   >>> sum_squares([1, 2, 3, 4])
   result: 30
   
   >>> sum_squares([6, 8])
   result: 100
   

   If the list is empty, the function should return 0:

   >>> sum_squares([])
   result: 0
   

   Hints:

   • This function is somewhat similar to the mylen function from lecture, but it needs to deal with a list instead of a string, and it needs to add the squares of the numbers in the list instead of just adding 1 for each character in the string. You can find a modified version of mylen that handles both strings and lists here.

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

     def sum_squares(vals):
         """ docstring goes here """
         if the list vals is empty:
             return _____
         else:
             sum_rest = sum_squares(______)
             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 sum_squares([2, 5, 3]) should call sum_squares([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 sum_squares([5, 3]) to figure out what sum_squares([2, 5, 3]) should return?

2. Write a function count_bu(s) that takes as input a string of 0 or more lower-case letters and uses recursion to compute and return the total number of times that the letters 'b' and 'u' appear in s. For example:

   >>> count_bu('bubby')     # 3 b's and 1 u
   result: 4
   
   >>> count_bu('be you')    # 1 b and 1 u
   result: 2
   
   >>> count_bu('terriers')  # no b's or u's
   result: 0
   

   You may assume that the string is composed of only lower-case letters.

   This function is similar to the num_vowels function from lecture.

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 double(s, c) that takes as input an arbitrary string s and and a single-character string c, and that uses recursion to determine and return a new string in which all occurrences of c in s are doubled/repeated. For example:

   >>> double('program', 'r')
   result: 'prrogrram'
   
   >>> double('program', 'o')
   result: 'proogram'
   
   >>> double('banana', 'a')
   result: 'baanaanaa'
   

   Hints:

   • This function is similar to the replace function from lecture.

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

     def double(s, c):
         """ docstring goes here """
         if the string s is empty:
             return _____
         else:
             double_rest = double(_____, _____)
             if _________________:           
                 return ____________
             else:
                 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 a reminder of how to do so, see question 8 in the section on General Questions in the FAQ.

2. Write a function process(vals, x) that takes as input a list of 0 or more integers vals and a single integer x, and that uses recursion to create and return a new list in which each element of the original list that is larger than x is replaced with a 0. For example:

   >>> process([5, 8, 3, 12], 6)
   result: [5, 0, 3, 0]
   

   Note that the two numbers from the original list that are greater than 6 (the 8 and 12) have been replaced with 0. The other two numbers (5 and 3) have been left unchanged because they are not greater than 6.

   Here are some other examples:

   >>> process([5, 8, 3, 12], 4)
   result: [0, 0, 3, 0]
   
   >>> process([5, 8, 3, 12], 15)
   result: [5, 8, 3, 12]
   
   >>> process([], 2)
   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.

   • Important: In the recursive case, when you use concatenation to build a larger list, make sure that both of the operands are lists. For example, if x is an integer and vals is a list, the following will produce an error:

     x + vals     # error: cannot add an integer to a list
     

     Instead, you would need to turn x into a list before adding it:

     [x] + vals   # correct!
     

3. Write a function mul_pairs(vals1, vals2) that takes as inputs two lists of numbers, vals1 and vals2, and that uses recursion to construct and return a new list in which each element is the product of the elements at the corresponding positions in the original lists. For example:

   >>> mul_pairs([7, 2, 3], [4, 5, 6])
   result: [28, 10, 18]
   

   Note that the elements in the result are obtained by multiplying the corresponding elements from the original lists (7*4, 2*5, and 3*6).

   Base cases: If the two lists do not have the same length or if either list is empty, the function should return an empty list ([]). These are the only base cases that you need!

   Here are some other examples:

   >>> mul_pairs([5, 3], [6, 4])
   result: [30, 12]
   
   >>> mul_pairs([5, 2, 3, 4], [20, 30, 50, 80])
   result: [100, 60, 150, 320]
   
   >>> mul_pairs([5, 3], [6])   # lists with different lengths
   result: []
   

   Hints:

   • Base cases: If the two lists do not have the same length or if either list is empty, the function should return an empty list ([]).

     Although you could combine these cases into one if statement, we recommend that you check for them separately.

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

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

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

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

   • See the FAQ for more help with this problem.

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 BUtify(s) that takes as input an arbitrary string s and uses recursion to determine and return a new string in which all lower-case bs are replaced by upper-case Bs and all lower-case us are replaced by upper-case Us. For example:

   >>> BUtify('you be you')
   result: 'yoU Be yoU'
   
   >>> BUtify('beautiful')
   result: 'BeaUtifUl'
   
   >>> BUtify('unbelievable')
   result: 'UnBelievaBle'
   

4. Write a function diff(vals1, vals2) that takes as inputs two arbitrary lists of non-negative integers vals1 and vals2 and uses recursion to construct and return a new list in which each element is the the absolute value of the difference of the corresponding elements from the original lists. For example:

   >>> diff([3, 4, 2, 5], [7, 2, 9, 5])
   result: [4, 2, 7, 0]
   

   In the return value for this case:

   • The first element is 4, because the difference of the first elements in the original lists is 3 - 7 = -4, and we multiply by -1 to get the absolute value.

   • The second element is 2, because the difference of the second elements in the original lists is 4 - 2 = 2, and we don’t need to adjust it because 2 is already non-negative.

   • The third element is 7, because 2 - 9 = -7, and we multiply by -1 to get the absolute value.

   • The fourth element is 0, because 5 - 5 = 0.

   Important

   You may not use Python’s built-in function for computing the absolute value of a number. Rather, you will need to use conditional execution to determine whether you need to adjust the result of subtracting a given pair of elements.

   Here are two other examples:

   >>> diff([5, 6, 2], [1, 9, 15])        
   result: [4, 3, 13]
   
   >>> diff([], [])        
   result: []
   

   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 differences (if any) in the returned list. For example:

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

   Hints:

   • You will probably 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 September 25, 2024.