Problem Set 6

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, March 22, 2018

Problem 0: Reading and response

5 points; individual-only

Computational models are playing an increasingly important role in a wide range of fields. This week’s reading involves two short pieces about the use of such models:

• an article from Inside Science about the way in which computational models contributed to the financial crisis of 2009

• a piece from The New York Times about the use of computational models to predict climate change.

After reading these two pieces, write a short response that addresses only one of the following questions. Put your response in a file named ps6pr0.txt. Don’t forget that the file you submit must be a plain-text file.

1. In light of the reading, make an argument for how computational models help and/or hurt society. You are welcome to stake out a middle position, or to take a strong stand on either side. Just make sure that your argument is informed by the reading.

2. Based on the information in the articles, how can computer scientists and others who develop computational models ensure that their models are correct? Is it even possible to do so?

For additional information about the use of computational models, here are two optional readings:

• an article about the role of computational models in urban planning
• a piece about the use of such models by the winners of the 2013 Nobel Prize in chemistry.

Problem 1: Practicing function calls and variable scope

10 points; individual-only

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

1. Consider the following Python program:

   def foo(a, b, c):
       a += 4
       c *= b
       print('foo', a, b, c)
       a = bar(c, a)
       print('foo', a, b, c)
       return c
   
   def bar(a, c):
       b = mystery(a)
       print('bar', a, b, c)
       b += mystery(c)
       return b
   
   def mystery(c):
       a = c + 3
       if c > 10:
           a //= 2
       elif c % 3 == 0:
           a += 1
       return a
   
   a = 3
   b = 5
   c = 2
   
   print(a, b, c)
   b = foo(c, a, b)
   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  
   -----------------
     3  |  5  |  2  
        |     |
   
   foo's local variables
     a  |  b  |  c  
   -----------------
        |     |
   
   bar's local variables
     a  |  b  |  c
   -----------------
        |     |
   
   mystery's local variables
     a  |  c  
   -----------
        |
   
   output (the lines printed by the program)
   ------
   3 5 2
   

   Note that you must include five 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, one for the local variables that belong to the function mystery, and one for the output of the program. Don’t forget to follow the rules for variable scope.

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

   • complete the first four 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.

Problem 2: Understanding loops

10 points; individual-only

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

1. Consider the following Python function, which uses an index-based for loop:

   def mystery(values):
        count = 0
        for i in range(len(values)):
            if values[i] < values[i-1]:
                count += 1
        return count
   

   Trace the execution of the following call to this function:

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

   In particular, you should:

   1. Copy the table shown below into your text file for this problem, and complete it to illustrate how the expression at the top of each column changes during the execution of the loop.

        i  | values[i] | values[i-1] | count 
      ---------------------------------------
        -  |     -     |      -      |   0
        0  |           |             | 
           |           |             |
      

      The table begins with a row for the initial value of the variable count. The remaining rows (including ones that you should add as needed) should show what happens for each value of the loop variable i.

   2. State the return value of this function call.

2. Consider the following Python program, which uses a while loop:

   a = 8
   b = 3
   print(a, b)
   
   while a > 2:
       a -= b
       b -= 1
       print(a + b)
   

   Copy the table shown below into your text file for this problem, and complete it (adding rows as needed) to show how the variables change over time and the values that are printed.

     a  |  b  | value printed
   --------------------------
     8  |  3  | 8 3
        |     |
   

Problem 3: Processing sequences with loops

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.

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

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

   >>> double('hello')
   'hheelllloo'
   >>> double('python')
   'ppyytthhoonn'
   >>> print(double('python'))
   ppyytthhoonn
   >>> double('')
   ''
   

   Here is a template that you can use to get started:

   def double(s):
       """ your docstring goes here """
       result = ''
   
       for c in s:
           ...
   

   Hint: This function performs a cumulative computation that gradually builds up a string. We discussed a similar function (a loop-based remove_vowels) in lecture.

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

   Here are some examples:

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

   Hints:

   • You will need to use an index-based loop so that you can access the corresponding characters from both s1 and s2 at the same time. Here is a template that you can use to get started:

     def weave(s1, s2):
         """ your docstring goes here """
         result = ''
         len_shorter = min(len(s1), len(s2))
     
         for i in range(len_shorter):
             ...
     

     Note that we determine the length of the shorter string before beginning the loop, because the loop should only consider the index values that are present in both loops.

   • After the loop, you will need to handle any “extra” characters from the longer string (for cases in which the strings don’t have the same length). One way to do that is to use conditional execution (e.g., an if-else statement), although other approaches may also be possible.

3. Write a function square_evens(values) that takes a list of integers called values, and that modifies the list so that all of its even elements are replaced with their squares, but all of its odd elements are left unchanged.

   This function should not return a value. Rather, it should should use a loop to modify the internals of the original list as needed. For example, to modify element i of the list values, you should perform an assignment that looks like this:

   values[i] = expression
   

   where expression is replaced with an appropriate expression for the new value of values[i]. For reasons that we will discuss in lecture this week, any changes that the function makes to the internals of the list will still be there after the function returns.

   For example:

   >>> vals1 = [1, 2, 3, 4, 5, 6]
   >>> square_evens(vals1)
   >>> vals1
   [1, 4, 3, 16, 5, 36]
   >>> vals2 = [7, 3, 10, 8]
   >>> square_evens(vals2)
   >>> vals2
   [7, 3, 100, 64]
   

4. Write a function index(elem, seq) that takes as inputs an element elem and a sequence seq, and that uses a loop 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 to test for the presence of elem in seq. (However, you are welcome to use in as part of the header of a for loop.) In addition, you may not use any built-in methods (i.e., functions like find or index that are found inside of string or list objects). However, you may use built-in functions like len and range.

   Here are some examples:

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

   You solved this problem using recursion in Problem Set 2, but for this problem set you must use a loop.

   Hint: One way to solve this problem is to have two return statements: one inside the loop, and one after the loop has completed.

Part II

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

Problem 4: Estimating pi

20 points; individual-only

In this problem you will employ loops to estimate the value of the mathematical constant π (3.14159...).

Begin by downloading the file ps6pr4.py and opening it in IDLE. We’ve given you some starter code that you will need for this problem.

Background
The procedure that you will employ to estimate π is one that is discussed in Chapter 1 of CS for All. It’s an example of a more general problem-solving approach known as Monte Carlo simulation.

Imagine that you have a square with sides of length 2 that spans the region of the Cartesian plane in which -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. If you inscribe a circle within that square, the circle will have a radius of 1, and thus its area will be π.

It you were to throw darts at random locations inside the square, some of them would hit the circle, and some would not. The ratio

area of the circle / area of the square

can be estimated by the ratio

# of darts that hit the circle / total # of darts thrown

As the number of darts increases, the second ratio above gets closer and closer to the first ratio. As a result, we can set the two ratios equal to each other and solve for the area:

area of circle = (# of darts that hit the circle * area of square) / total # of darts thrown

We can then use this expression to approximate the area of the circle, and thus the value of π.

Obviously, we won’t actually be throwing darts! Instead, we’ll use Python’s random module to generate random numbers that simulate the dart-throwing process. This use of random numbers (or, to be more precise, pseudorandom numbers) is at the heart of Monte Carlo simulation.

The functions
You will write two different estimation functions for this problem. Both of them will use the throw_dart() function that we have provided.

0. We’ve given you a helper function throw_dart() (with no inputs) that simulates the act of throwing one dart in the square region described above. If the dart hits the circle of radius 1 inscribed in the square, the function returns True. If the dart falls outside the circle, the function returns False.

   Read over this function to see what it does. In particular, notice the following:

   • throw_dart() uses a function called random.uniform() from Python’s random module. It particular, it makes the following function call:

     random.uniform(-1.0, 1.0)
     

     This call chooses a float at random from the range of floating-point numbers between -1.0 and 1.0. Note that throw_dart makes this call twice – once to obtain the x coordinate of the dart throw, and once to obtain its y coordinate.

   • A throw is considered to have hit the circle if the sum of x2 and y2 is less than or equal to 1.0. If it is, the function returns True, otherwise it returns False.

1. Write a function est_pi1(n) that takes a positive integer n and returns an estimate of π that is based on n randomly thrown darts.

   The function should use either a for loop or a while loop. You should decide which loop construct is the better one for this function, based on whether its task lends itself better to a definite loop or an indefinite loop.

   The loop that you write should call the throw_dart() function to throw a single dart, and it should continue looping until it has thrown n darts.

   Important

   For full credit, your function should have exactly one line of code that makes a call to throw_dart(). If you have fewer or more than one line of code that calls throw_dart(), you will lose points.

   In addition, your function should not make its own calls to random.uniform(), and you will lose points if it does so.

   After each dart is thrown, the function should print the following:

   • the number of darts thrown so far
   • the number of the darts that have hit the circle
   • the current estimate of π (computed using the formula given at the start of the problem)

   Then, after all n throws have been made, the function should return the final estimate of π.

   Because the throw_dart function is using random numbers, the results obtained for a given input will vary. However, here’s one example of what the output should look like:

   >>> est_pi1(10)
   1 hits out of 1 throws so that pi is 4.0
   2 hits out of 2 throws so that pi is 4.0
   3 hits out of 3 throws so that pi is 4.0
   4 hits out of 4 throws so that pi is 4.0
   4 hits out of 5 throws so that pi is 3.2
   5 hits out of 6 throws so that pi is 3.33333333333
   6 hits out of 7 throws so that pi is 3.42857142857
   6 hits out of 8 throws so that pi is 3.0
   7 hits out of 9 throws so that pi is 3.11111111111
   8 hits out of 10 throws so that pi is 3.2
   3.2
   

   Notes/hints:

   • You will need accumulator variables for the number of darts thrown and the number of hits. Don’t forget to initialize those variables before the start of the loop.

   • For a given input n, the function should print n lines of output–one for each dart throw. The final number shown above is the return value, which is displayed when you call the function from the Shell. The function should not actually print this value; it should just return it.

2. Write a function est_pi2(error) that takes a positive floating-point input error and returns the number of dart throws needed to produce an estimate of π that is less than error away from the “actual” value of π (i.e., the value given by math.pi in Python’s math module).

   The function should use either a for loop or a while loop. You should decide which loop construct is the better one for this function, based on whether its task lends itself better to a definite loop or an indefinite loop. (If you have made the correct choice of loop for both of the estimation functions, one of them should have used a for loop, and the other should have used a while loop.)

   The loop that you write should call the throw_dart() function to throw a single dart, and it should continue looping until the absolute difference between the function’s current estimate of π and math.pi is less than error.

   Important

   For full credit, your function should have exactly one line of code that makes a call to throw_dart(). If you have fewer or more than one line of code that calls throw_dart(), you will lose points.

   In addition, your function should not make its own calls to random.uniform(), and you will lose points if it does so.

   After each dart is thrown, the function should print the same three values that were printed by your est_pi1 function.

   Once the estimate is accurate enough, the function should return the number of darts thrown in order to achieve that final estimate.

   The results obtained for a given input will vary, but they should look something like this:

   >>> est_pi2(0.1)
   1 hits out of 1 throws so that pi is 4.0
   2 hits out of 2 throws so that pi is 4.0
   3 hits out of 3 throws so that pi is 4.0
   4 hits out of 4 throws so that pi is 4.0
   5 hits out of 5 throws so that pi is 4.0
   5 hits out of 6 throws so that pi is 3.33333333333
   6 hits out of 7 throws so that pi is 3.42857142857
   7 hits out of 8 throws so that pi is 3.5
   7 hits out of 9 throws so that pi is 3.11111111111
   9
   

   Notes/hints:

   • Here again, you will need accumulator variables for the number of darts thrown and the number of hits. Don’t forget to initialize those variables before the start of the loop.

   • We have imported Python’s math module for you, so you can use the expression math.pi when comparing your current estimate to the “actual value” of π.

   • You are welcome to use the built-in abs function, which returns the absolute value of its input.

   • The final number shown in the sample run above is the return value, which is displayed when you call the function from the Shell. The function should not actually print this value; it should just return it.

Problem 5: The Fibonacci sequence in Python

15 points; individual-only

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

The Fibonacci sequence is one of the most famous sequences in mathematics. The first Fibonacci number (F0) is 1, the second Fibonacci number (F1) is also 1, and each of the remaining Fibonacci numbers can be found by adding the previous two numbers in the sequence:

• F0 = 1
• F1 = 1
• F2 = 1 + 1 = 2
• F3 = 1 + 2 = 3
• F4 = 2 + 3 = 5
• F5 = 3 + 5 = 8
• F6 = 5 + 8 = 13
• F7 = 8 + 13 = 21
• etc.

In this problem, you will write two separate functions. Taken together, these functions will serve as an interactive program that allows the user to work with Fibonacci numbers.

1. Write a function fib(n) that takes an integer n as input, and that uses a loop to both:

   • determine and print the first n Fibonacci numbers
   • compute and return the sum of those numbers

   You may assume that the input n is at least 2.

   For example:

   >>> fib(4)
   1
   1
   2
   3
   7
   

   In this case:

   • The first 4 values (the numbers 1, 1, 2, and 3) are the first 4 Fibonacci numbers; they are printed by the function.

   • The final value (the 7) is the sum of those 4 numbers. This sum is returned by the function, which is why we see it when we call the function from the Shell. However, the function itself does not print the sum.

   Here’s another example:

   >>> result = fib(7)
   1
   1
   2
   3
   5
   8
   13
   

   In this case, the call fib(7) prints the first 7 Fibonacci numbers, and it returns their sum. However, because we assign the return value to the variable result, the sum is not displayed at the bottom of the list of numbers. To see the sum, we can print or evaluate the variable result:

   >>> result
   33
   

   Notes/hints:

   • Your function must use either a for loop or a while loop.

   • Because the next Fibonacci number is derived from the two previous numbers, we recommend that you have three different variables for Fibonacci numbers: one for the “current” number (the one that will be printed next) and two variables for the previous two numbers. In addition, you will need a separate variable for the sum of the numbers.

   • At least some of your variables will need to be initialized before you begin looping, and all of them will need to be updated appropriately inside the loop.

   Make sure to test your function for a variety of inputs, starting with n = 2.

2. Write a function main() that takes no inputs. The function should:

   • ask the user how many Fibonacci numbers he or she wants to produce
   • call the fib function to generate and print those numbers
   • print the sum of the numbers (i.e., the value returned by fib).

   The main function itself should not return a value.

   Here is one sample interaction with the user, in which we assume that the user enters 4:

   >>> main()
   How many Fibonacci numbers? 4
   1
   1
   2
   3
   their sum is 7
   

   Notes/hints:

   • To get the integer from the user, you should use the input function that we have discussed in lecture, along with the appropriate conversion function (one that will convert the string returned by input to an integer).

   • fib already prints the requested Fibonacci numbers, so your main function does not need to print them.

Problem 6: The Fibonacci sequence in assembly

15 points; individual-only

Begin by downloading the following file: ps6pr6.txt

Move it into your ps5partII folder from Problem Set 5, and open the file in a text editor.

Your task is to write a Hmmm assembly-language version of the Python program that you wrote in Problem 5.

Your program should begin by reading an integer n from the user. It should then call a separate function to generate and print the first n Fibonacci numbers while also computing their sum. After the function returns, the program should print the sum and halt.

In other words, the start of your assembly-language program should be comparable to the main function that you wrote for Problem 5, and it should call a separate function that has the same functionality as the fib function that you wrote for Problem 5.

Important: For full credit, your assembly-language program must employ a single separate function to generate and print the Fibonacci numbers, and to compute and return their sum. Use call and jumpr instructions as we did in lecture.

Here is a sample run of the program, in which we assume that the user enters 7:

Enter a number: 7
1
1
2
3
5
8
13
33

Note that the first 7 values printed (the numbers 1 through 13) are the first 7 Fibonacci numbers, and the final value (the 33) is the sum of those 7 numbers.

Notes/hints:

• Remember to follow the style guidelines that we specified for assembly code in Problem Set 5. In particular, you must have a comment on every line except for nop and halt statements.

• Make sure that your comments do not include any special characters (e.g., $, quotes, or &).

• As always, you should take one step at a time, and test each new addition or change before continuing. After each change that you make to your assembly code, make sure to resave the file before you assemble and run it.

• Make sure that you use call and jumpr instructions to call and return from the separate function.

• You should decide in advance which registers you will use for the following purposes:

  • the user input to the program

  • the input to the function

  • the return address of the function (we used r14 for this in lecture)

  • the return value of the function (we used r13 for this in lecture)

• You will also need additional registers for other purposes. In particular, we recommend three separate registers for Fibonacci numbers, just as we recommended three variables for Fibonacci numbers in your fib function for Problem 5. In addition, you will need a separate register for the sum of the numbers.

• You should not need to use the stack in this problem.

• Test your program carefully, starting at n = 2.

Submitting Your Work

You should use Apollo to submit the following files:

• your ps6pr0.txt file containing your response to the reading for Problem 0
• your ps6pr1.txt file containing your solutions for Problem 1
• your ps6pr2.txt file containing your solutions for Problem 2
• your ps6pr3.py file containing your code for Problem 3; 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 ps6pr4.py file containing your solution for Problem 4
• your ps6pr5.py file containing your solution for Problem 5
• your modified ps6pr6.txt file containing your solution for Problem 6

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.