CS 111
Fall 2018

Problem Set 1

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, September 20, 2018

Problem 0: Reading and response

5 points; individual-only

Using folders

We strongly encourage you to create a separate folder for each assignment, so that you can more easily keep track of your work. For example, you could create a folder called ps1 for your work on this assignment, and put all of the files for PS 1 in that folder.

In class, we’ve been exploring various types of data in Python. As you’ve probably heard, we’re currently living in the age of big data, in which massive amounts of data are being collected, analyzed, and used to guide decisions in a wide range of occupations and fields of study. This week’s reading, which comes from Wired, discusses the ways in which data is affecting science.

The reading is available here.

After you have read the article, write a response that addresses only one of the following prompts. (Important: Put your response in a file named ps1pr0.txt. Don’t forget that the file that you submit must be a plain-text file.)

  1. The author refers to one’s “MySpace” page. This is a clear, if superficial, way in which this article (which was written in 2008) shows its age. What is a deeper way in which the ideas of this article betray thinking that has moved on since 2008? Contrast one of its ideas with more recent thinking, which can be your own, others’, or both.

  2. The article states that, whether in science or business, we “don’t have to settle for models at all.” Do you agree or disagree with this statement? How? And why? Certainly feel free to articulate a more nuanced or hybrid view, if you’d like.

You only need to write a short paragraph (4-6 sentences). The important thing is that your response uses and extends (or alters or refutes) ideas from the article.

Problem 1: Indexing and slicing puzzles

15 points; individual-only

This problem will give you practice with indexing and slicing. Begin by downloading this file: ps1pr1.py. Open it in IDLE, following the procedure outlined in Task 2 of Lab 1.

Highly recommended

  • Use the screen layout mentioned in Lab 1, which we’ve reproduced below.
  • Modify IDLE’s settings following the instructions from Task 6 of Lab 0. Doing so will allow you to use the Up Arrow and Down Arrow keys to scroll through the expressions that you’ve already entered in the Shell, and will thus save you a lot of unnecessary typing!

IDLE

List puzzles
The first half of the problem focuses on lists. In particular, you will be constructing new lists from the following:

pi = [3, 1, 4, 1, 5, 9]
e = [2, 7, 1]

We’ve given you these lines in ps1pr1.py. In addition, we’ve provided the answer to the first puzzle (puzzle 0). You should add in the answers for the remaining puzzles, following the format that we’ve given you for puzzle 0.

The expressions that you construct must only use pi and e and the following list operations:

We encourage you to try using as few operations as possible, to keep your answers elegant and efficient. However, you will get full credit for any expression that follows the rules above and produces the correct result.

Before getting started, you should run ps1pr1.py in IDLE using F5. This will make the lists pi and e available to you in the Python Shell.

Here are the puzzles:

  1. Use pi and/or e to create the list [3, 7, 1], and assign it to the variable answer0. We’ve given you the following code for this puzzle:

    # Example puzzle (puzzle 0):
    # Creating the list [3, 7, 1] from pi and e
    answer0 = [pi[0]] + e[-2:]     
    print(answer0)
    

    Note that our answer involves four operations: one use of indexing (pi[0]), one slice (e[-2:]), one list construction (the use of brackets around pi[0]) and one concatenation with +.

  2. Use pi and/or e to create the list [1, 5, 9] and assign it to the variable answer1. Your answer should follow the format that we’ve given you for puzzle 0. In other words, it should look like this:

    # Puzzle 1:
    # Creating the list [1, 5, 9] from pi and e
    answer1 = 
    print(answer1)
    

    where you put the appropriate expression to the right of the assignment operator (=). Please leave a blank line between puzzles to make things more readable.

  3. Use pi and/or e to create the list [3, 4, 5], and assign it to the variable answer2. Here again, make sure to follow the correct format, and to leave a blank line between puzzles.

  4. Use pi and/or e to create the list [9, 1, 1, 1], and assign it to the variable answer3. (Optional challenge: See if you can do this with just two list operations!)

String puzzles
The second half of the problem focuses on strings. In particular, you will be working with the following strings:

b = 'boston'
u = 'university'
t = 'terriers'

We’ve given you these lines in ps1pr1.py, along with the answer to the first string puzzle (puzzle 5). Run the file as needed so that the strings will be available for you to experiment with in IDLE.

The expressions that you construct for the remaining puzzles must only use the above strings and the following string operations:

Here again, you will get full credit for any expression that follows the rules above and produces the correct result, but we encourage you to try using as few operations as possible.

Here are the puzzles:

  1. Use b, u, and/or t to create the string 'bossy', and assign it to the variable answer5. We’ve given you the following code for this puzzle:

    # Puzzle 4:
    # Creating the string 'bossy'
    answer4 = b[:3] + t[-1] + u[-1]
    print(answer4)
    

    Note that our answer involves 5 operations: 2 uses of indexing, 1 slice, and 2 concatenations with +. (It’s actually possible to solve this puzzle using only 3 operations. Give it a try if you have time!)

  2. Use b, u, and/or t to create the string 'vest', and assign it to the variable answer5. (Our best answer uses 3 ops.) Here again, make sure to follow the correct format, and to leave a blank line between puzzles.

  3. Use b, u, and/or t to create the string 'revisit', and assign it to the variable answer6. (Our best: 3 ops.)

  4. Use b, u, and/or t to create the string 'booooooo', and assign it to the variable answer7. (Our best: 4 ops.)

  5. Use b, u, and/or t to create the string 'borris', and assign it to the variable answer8. (Our best: 3 ops.)

After finishing all of the puzzles, make sure to run your ps1pr1.py file to check that the correct outputs are printed.

Problem 2: Statements, expressions and conditional execution

15 points; individual-only

Open up a text editor (e.g., Notepad or TextEdit) and create a plain-text file named ps1pr2.txt. Put all of your work for this problem in that file.

  1. Consider the following Python program:

    a = 10
    b = 3
    c = b + 5
    b = b ** 2
    a = a // 4
    b = b % 4
    

    Copy the table shown below into your text file for this problem, and fill in the missing values to illustrate how the values of the variables change over the course of the program. We’ve given you the values of the variables after the first two lines of code. You should complete the remaining rows of the table.

    line of code   | a  | b  | c  |
    --------------------------------
    a = 10         | 10 |    |    |
    b = 3          | 10 | 3  |    |   
    c = b + 5      |    |    |    |
    b = b ** 2     |    |    |    |
    a = a // 4     |    |    |    |
    b = b % 4      |    |    |    |
    
  2. Assume that you have two variables x and y that have each been assigned an integer value. Construct the assignment statements and expressions specified below.

    Important: Assignment statements should assign a value to a variable using the assignment operator (=). Expressions should not assign anything.

    Sample assignment statements include:

    • x = y * 2
    • y = y + 1
    • x = x + 2

    Sample expressions include:

    • x < y
    • x * y

    Here are your tasks:

    1. Write an assignment statement that gives x a value that is 10 more than the value of y.

    2. Write an expression that tests if y is equal to twice the value of x.

      • Hint: For problems like this one, you should not include an if statement. Simply provide an appropriate boolean expression.
    3. Write an assignment statement that triples the value of y.

    4. Write an expression that computes the cube of y (i.e., that raises y to the third power).

    5. Write an expression that tests if x is inside the set of integers from 3 to 15 inclusive. Your expression should use one of the logical operators (and, or, or not).

  3. Consider the following Python program:

    def mystery(vals):
        a = vals[0]
        b = vals[1]
        c = vals[2]
        if a > b:
            if b > c:
                print('wow')
            else:
                print('tow')
        elif b > c:
            if a >= c:
                print('mow')
            if a < b:
                print('low')
            elif c == b:
                print('dow')
            print('pow')
        else:
            print('now')
            if a == b:
                print('how')
            else:
                print('bow')
        print('row')
    

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

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

    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 3: Functions with numeric inputs

20 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 a collection of simple functions that operate on numeric inputs.

Begin by downloading this file: ps1pr3.py. Open it in IDLE, following the procedure outlined in Task 2 of Lab 1. Here again, we encourage you to use the screen layout mentioned in that lab.

Important guidelines:

  • You may find it helpful to review the example functions from lecture so you can use them as models for what you need to do.

  • Your functions must have the exact names that we have specified, or we won’t be able to test them. Note in particular that the case of the letters matters (all of them should be lowercase), and that you should use an underscore character (_) wherever we have specified one (e.g., in larger_gap).

  • If a function takes more than one input, you must keep the inputs in the order that we have specified.

  • Each of your functions should include a docstring that describes what your function does and what its inputs are. See our example functions from lecture for models.

  • Make sure that your functions return the specified value, rather than printing it. None of these functions should use a print statement.

  • You should not use any Python features that we have not discussed in lecture or read about in the textbook.

  • Your functions do not need to handle bad inputs – inputs with a type or value that doesn’t correspond to the description of the inputs provided in the problem.

  • Test each function after you write it. Here are two ways to do so:

    • Run your ps1pr3.py file after you finish a given function. Doing so will bring you to the Shell, where you can call the function using different inputs and check to see that you obtain the correct outputs.
    • Add test calls to the test function that we have provided at the bottom of your ps1pr3.py file. We have given you an example of one such test call in the starter file. After running your ps1pr3.py file, you can call the test function (by entering test()) to see the results of all of the test calls.
  • To facilitate grading, please put any test code inside a function like the test function that we have given you. Do not add any lines of code that belong to the global scope of the program (i.e., lines that are outside of any function).

Here are the descriptions of the functions:

  1. (example) Write a function opposite(x) that takes a number x as its input and returns the opposite of its input. We have given you this example function in the starter file.

  2. Write a function root(x) that takes a number x as its input and returns the square root of its input. For example:

    >>> root(25)
    5.0
    >>> print(root(64))
    8.0
    

    Hint: The square root of a number can be found by raising it to a power of 0.5, and you can use the ** operator for this purpose.

    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. This same warning applies to all of the functions that you will write for this assignment.

    Note: You should leave one or two blank lines between functions to make things more readable, and make sure to include a docstring like the one in our example function.

    Warning

    Make sure that you use the correct amount of indentation. In particular, your docstrings should be indented by 4 spaces as shown in our code for opposite, so that they line up with the code inside the function.

  3. Write a function gap(num1, num2) that takes two numeric inputs num1 and num2 and returns the “gap” between the two numbers. More specifically, it should:

    • return num1 - num2 if num1 is greater than num2

    • return num2 - num1 if num1 is less than num2

    • return 0 if num1 is equal to num2

    Your function must use conditional execution, and it should not use any of Python’s built-in functions. In particular, it should not use the abs function.

    Here are some examples of how it should work:

    >>> gap(5, 2)     
    3
    >>> gap(2, 5)     
    3
    >>> gap(2, 2)     
    0
    >>> print(gap(4, 6))
    2
    

    Note that the return value should always be non-negative.

  4. Write a function larger_gap(a1, a2, b1, b2) that takes four numeric inputs a1, a2, b1, and b2. It should:

    • compute the gap between a1 and a2
    • compute the gap between b1 and b2
    • return the larger of the two gaps.

    Your function must use conditional execution, and it should not use any of Python’s built-in functions. In particular, it should not use the max function.

    Examples:

    >>> larger_gap(3, 2, 4, 7)     # gap(4, 7) (which is 3) > gap(3, 2)
    3
    >>> larger_gap(7, 2, 3, 4)     # gap(7, 2) (which is 5) > gap(3, 4)
    5
    >>> print(larger_gap(2, 3, 5, 4))  # both pairs have a gap of 1
    1
    

    Recommended approach:

    • Start by making two calls to the gap function that you wrote earlier—one call to compute the gap between a1 and a2, and one to compute the gap between b1 and b2–and store the results of those calls in variables.

    • Use conditional execution to return the larger of the two gaps. Note that you can return either gap if they are equal.

  5. Write a function distance(x1, y1, x2, y2) that takes four numeric inputs that specify the coordinates of two points (x1, y1) and (x2, y2) in the Cartesian plane, and that returns the distance between those two points. Recall that distance is given by the following formula:

    distance formula

    Examples:

    >>> distance(2, 3, 5, 7)     # distance between (2,3) and (5,7)
    5.0
    >>> distance(0, 0, 5, 12)    # distance between (0,0) and (5,12)
    13.0
    >>> print(distance(1, -1, 0, 0))
    1.4142135623730951
    

    Hint: You can use your root function to compute the square root required by the distance formula.

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

You may also find it helpful to use the Python Tutor Visualizer to trace through the execution of your functions – either to verify that they’re working as expected, or to determine why they’re not working! Paste your function definition into the Visualizer’s code box, and follow the definition with code that calls the function. Then click the Visualize Execution button below the code box to begin the visualization. For example, to test the circle_area function that we discussed in lecture, you could paste the following into the Visualizer:

def circle_area(diam):
    radius = diam / 2
    area = 3.14159 * (radius**2)
    return area

test = circle_area(10)
print('test is', test)

Part II

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

Problem 4: Program flow and variable scope

10 points; individual-only

Open up a text editor (e.g., Notepad or TextEdit) and create a plain-text file named ps1pr4.txt. Put all of your work for this problem in that file.

  1. Consider the following Python program:

    def foo(a, b):
        b = b - 2
        a = a - b
        print('foo', a, b)
        return a
    
    a = 7
    b = 4
    print(a, b)
    a = foo(a, b)
    print(a, b)
    foo(b, 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  
    -----------
      7  |  4     
         |
    
    local variables (ones that belong to foo)
      a  |  b  
    -----------
         |       
         |
    
    output (the lines printed by the program)
    ------
    7 4
    

    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 foo), and one for the output of the program. Don’t forget that the global variables and local variables are two separate sets of variables, even though they happen to have the same names.

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

    For an example of how to approach this problem, and of what your answer should look like, we encourage you to review the video called Tracing Function Calls that can be found on Blackboard in the lecture folder for 9/18 (if you are in the C lecture) or 9/19 (if you are in the A or B lecture).

  2. Consider the following Python program:

    def wow(a):
        b = a * 2
        print('wow:', a, b)
        return b
    
    def yay(b):
        a = wow(b) + wow(b + 2)
        print('yay:', a, b)
        return a
    
    a = 3
    b = 2
    print(a, b)
    b = wow(b)
    print(a, b)
    yay(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     
         |
    
    wow's local variables
      a  |  b  
    -----------
         |       
         |
    
    yay'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 wow, one for the local variables that belong to the function yay, 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.

Problem 5: Functions on strings and lists, part I

15 points; individual-only

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 ps1pr5.py. Make sure to specify the .py extension.

Include comments at the top of the file that are similar to the ones that we gave you at the top of ps1pr3.py.

Follow the same guidelines that we gave you for problem 3.

  1. Write a function outer_vals(values) that takes a list values and returns a new list containing only the outer values (i.e., the first and last elements) of the original list. You may assume that the original list has at least one value.

    Although this function could be completed in one line, you must use the following template:

    def outer_vals(values):
        """ put your docstring here """
        first = ________ 
        last = ________
        return [first, last]
    

    Here are some examples of how the function should work:

    >>> outer_vals([1, 2, 3, 4, 5, 6, 7])
    [1, 7]
    >>> outer_vals(['red', 'orange', 'yellow', 'green'])
    ['red', 'green']
    >>> print(outer_vals([111]))
    [111, 111]              # 111 is both the first and the last!
    

    Warning

    Remember that your functions should return 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 last 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. 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 ends_match(s) that takes a string input s and returns True if the first character in s matches the last character in s, and False otherwise. It does not have to work on the empty string (the string '', which has no characters – not even a space). Here are some examples:

    >>> ends_match('no match')         # 'n' does not match 'h'
    False
    >>> ends_match('hah! a match')     # 'h' matches 'h'
    True
    >>> print(ends_match('q'))         # 'q' is both first and last!
    True
    

    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 two calls above from the Shell, you must fix your function to remove the quotes.

    One straightforward way to write this function is to use an if-else statement, although it’s also possible to write a version that doesn’t need that type of statement.

  3. Write a function every_other(values) that takes as input a list values and returns a list containing every other value from the original list. Here are some examples:

    >>> every_other([1, 2, 3, 4, 5, 6, 7])
    [1, 3, 5, 7]
    >>> print(every_other(['red', 'orange', 'yellow', 'green']))
    ['red', 'yellow']
    

    Hint: Use skip-slicing!

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3. 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.

Problem 6: Functions on strings and lists, part II

20 points; individual-only

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 ps1pr6.py. Make sure to specify the .py extension.

Follow the same guidelines that we gave you for problem 3.

  1. Write a function reverse(s) that takes a string input s and returns a string in which the characters of s have been reversed. For example:

    >>> reverse('abcdef')
    'fedcba'
    >>> print(reverse('howdy'))
    ydwoh
    

    Hint: Use skip-slicing!

  2. Write a function begins_with(word, prefix) that takes as inputs two string values word and prefix, and that returns True if the string word begins with the string prefix, and False otherwise. For example:

    >>> begins_with('computer', 'comp')
    True
    >>> begins_with('computer', 'come')
    False
    >>> begins_with('begin', 'beg')
    True
    >>> print(begins_with('begin', 'big'))
    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 three calls above from the Shell, you must fix your function to remove the quotes.

    Hint: Begin by computing the length of prefix and storing it in an appropriately named variable. Then use that variable as part of a test to determine if word begins with prefix.

  3. Write a function flipside(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:

    >>> flipside('homework')
    'workhome'
    >>> print(flipside('carpets'))
    petscar
    

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

  4. Write a function adjust(s, length) that takes as inputs a string s and an integer length, and that returns a string in which the value of s has been adjusted as necessary to produce a string with the specified length.

    If s is too short, the value that is returned should be “padded” with spaces on the left-hand side:

    >>> adjust('alien', 6)
    ' alien'                 # pad with 1 space to get a length of 6
    >>> adjust('compute', 10)
    '   compute'             # pad with 3 spaces to get a length of 10
    

    If s is either the correct length or too long, the value that is returned should consist of the first length characters of s:

    >>> adjust('alien', 4)
    'alie'                   # return the first 4 characters
    >>> print(adjust('compute', 7))
    compute                  # return the first 7 characters -- all of it!
    

Don’t forget to test your functions using the approaches mentioned at the start of Problem 3. 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:

Warnings

  • Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

  • Before submitting your files, make sure that your BU username is visible at the top of the Apollo page. If you don’t see your username, click the Log out button and login again.

  • If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

  • If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

  • If you encounter problems with Apollo, click the Log Out button, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs111-staff@cs.bu.edu

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.

Warning

Apollo will automatically close submissions for a given file when its final deadline has passed. We will not accept any file after Apollo has disabled its upload form, so please check your submission carefully following the instructions in Step 7 above.