Problem Set 7

Part I due by 11:59 p.m. on Thursday, April 3, 2025.
Part II due by 11:59 p.m. on Sunday, April 6, 2025.

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

Don’t forget to use docstrings and to take whatever other steps are needed to create readable code.

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

Create a subfolder called ps7 within your cs111 folder, and put all of the files for this assignment in that folder.

Problem 0: Reading and response

5 points; individual-only

Earlier in the course, we considered how computers store information as binary numbers that are manipulated using boolean circuits. While this approach to computing is by far the dominant one, there are other, alternative approaches to computing that people have begun to explore.

This week’s reading that provides a brief overview of one such alternative approach: computing with DNA.

The reading is available here.

After you have read the piece, create the necessary file for your response by taking the following steps:

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

In your copy of ps7pr0, write a response that addresses–at least to some extent–both of the following prompts:

1. What was the most interesting or important idea in this article for you – and why?

2. What are some of the limitations of this approach to computing?

As always, you only need to write a short paragraph (4-6 sentences). The important thing is that your response shows you have carefully read the article and digested its main ideas.

Problem 1: String-method puzzles

15 points; individual-only

This problem will give you practice with using the methods that are inside every string object.

Begin by downloading this file, putting it in your ps7 folder:

ps7pr1.py

Open that file in Spyder, and you’ll see that we’ve given you the following strings:

s1 = 'Three little kittens lost their mittens'
s2 = 'Star light, star bright'

We have also given you the solution to the first puzzle.

Warmup
Run ps7pr1.py in Spyder, so that the strings s1 and s2 will be available to you in the IPython console.

Next, enter the following method calls and other expressions from the console, and take note of the values that are returned:

>>> s1.upper()
>>> s1
>>> s2.lower()
>>> s2
>>> s2.count('s')
>>> s2.lower().count('s')
>>> s1.count('tt')
>>> s1.split()
>>> s1.split('t')
>>> s1.upper().split('T')
>>> s1.replace('th', 'f')
>>> s1.lower().replace('th', 'f')
>>> s2.replace('r', 'x')
>>> s2.replace('ar', 'amp')
>>> s1
>>> s2

Make sure that the result of each method call makes sense, and perform whatever additional calls are needed to ensure that you understand what each of these methods does. You may also want to consult the [online documentation][python_strings] for Python’s str class.

The Puzzles
Your task is to add answers to ps7pr1.py for the remaining puzzles, following the format that we’ve given you for puzzle 0.

Here are the puzzles:

0. Use s1 and one or more string methods to count all occurrences of the letter T (both upper-case and lower-case) in s1, and assign the count to the variable answer0. The expected answer is 9. We’ve given you the code for this puzzle.

1. Use s1 and one or more string methods to create the string

   'Three lipple kippens lost their mippens'
   

   Your answer for this and the remaining puzzles should follow the format that we’ve given you for puzzle 0. In other words, it should look like this:

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

2. Use s2 and one or more string methods to create the list

   ['Sta', ' light, sta', ' b', 'ight']
   

   Assign the result to the variable answer2.

3. Use s2 and one or more string methods to create the string

   'NIGHT LIGHT, NIGHT BRIGHT'
   

   Assign the result to the variable answer3.

4. Use s1 and one or more string methods to create the list

   ['', 'ree little kittens lost ', 'eir mittens']
   

   Assign the result to the variable answer4.

5. Use s2 and one or more string methods to create the list

   ['Star look', ' star brook']
   

   Assign the result to the variable answer5.

Problem 2: Our Rectangle class revisited

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

In lecture this week, we are considering a class called Rectangle, which serves as a blueprint for objects that represent rectangles. In this problem, you will add one field and several methods to this class.

0. Begin by downloading the following file, which includes the version of the Rectangle class that we used in lecture:

   ps7pr2.py

   Save the file in your ps7 folder, and open it in Spyder. Make sure to review all of the existing code in this file.

   (Note: two of the methods in this class will be discussed in the pre-lecture and lecture for Wednesday.)

1. Let’s say that we want each Rectangle object to include a new field called unit that stores a string specifying the unit of measurement (e.g., 'feet' or 'cm') for the Rectangle‘s dimensions.

   Update the Rectangle constructor so that it can be used to initialize the value of this new unit field. After making the necessary changes, you should be able to do something like the following from the console:

   >>> r1 = Rectangle(10, 30, 'cm')
   
   >>> r1.unit
   result: 'cm'
   

   Make sure that you:

   • Add a parameter to the header of the constructor for the new input.

   • Perform the necessary assignment within the constructor.

2. Add a method called diagonal that takes no inputs and computes and returns the length of the called Rectangle object’s diagonal – i.e., the square root of the sum of the squares of the Rectangle‘s height and width. For example:

   >>> r1 = Rectangle(30, 40, 'in')
   
   >>> r1.diagonal()
   result: 50.0
   

   Notes:

   • Don’t forget to indent your new method so that it will be considered part of the Rectangle class.

   • You should use the built-in math.sqrt function to compute the necessary square root. We have already included an import statement for the math module at the top of rectangle.py so that you will have access to this function.

3. The pre-lecture and lecture for Wednesday discuss a special method called __repr__, which creates a string representation of an object that can be used when the object is printed or evaluated from the console.

   The existing Rectangle version of this method returns a string that is based solely on the height and width of the rectangle.

   Update the __repr__ method so that it includes the value of the new unit field at the end of the string that is returned. For example:

   >>> r1 = Rectangle(10, 30, 'cm')
   
   >>> print(r1)
   10 x 30 cm
   

4. The pre-lecture and lecture for Wednesday also discuss a special method called __eq__ that is used when two objects are compared using the == operator.

   The current Rectangle version of the __eq__ method only compares the heights and widths of the Rectangle objects. Update this method so that it considers the new unit field as well. Two Rectangle objects should only be considered equal if their widths, heights, and units all match. For example:

   >>> r1 = Rectangle(30, 40, 'in')
   
   >>> r2 = Rectangle(20, 70, 'in')
   
   >>> r3 = Rectangle(20, 70, 'feet')
   
   >>> r4 = Rectangle(20, 70, 'in')
   
   >>> r1 == r2
   result: False
   
   >>> r2 == r3
   result: False
   
   >>> r2 == r4
   result: True
   

5. Add a method called larger_than(other) that takes another Rectangle other as a parameter and that returns True if the called Rectangle object (the object given by self) has a larger area than the area of the Rectangle passed in for other, and False otherwise.

   >>> r1 = Rectangle(30, 40, 'in')
   
   >>> r2 = Rectangle(20, 70, 'in')
   
   >>> r1.larger_than(r2)   # 1200 is not larger than 1400
   result: False
   
   >>> r2.larger_than(r1)   # 1400 *is* larger than 1200
   result: True
   

   Important: For full credit, your larger_than method must make use of the existing area method to compute the areas of the two Rectangle objects. For example, to obtain the area of the called object, you can use the expression self.area()

   Special case: If the two Rectangle objects have different units, the function should return False, regardless of the dimensions. For example:

   >>> r1 = Rectangle(100, 40, 'in')
   
   >>> r2 = Rectangle(20, 70, 'feet')
   
   >>> r1.larger_than(r2)
   result: False
   

Submitting your work for Part I

Important: You should submit a plain-text file for Problem 0, not a PDF. See Step 1 below as needed.

Submit all three of your files for Part I under the assignment labeled PS 7: Problems 0-2 using these steps:

1. If you still need to create a text file for Problem 0, open your file on Google Drive, choose File->Download->Plain Text, and save the file on your machine.

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

3. Add your 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.

4. Click the Upload button.

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

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

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

8. 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 3: Images as 2-D lists

30 points; individual-only

Getting started
Begin by downloading the following zip file: ps7image.zip

Unzip this archive, and you should find a folder named ps7image, and within it several files, including ps7pr3.py. Open that file in Spyder, and put your work for this problem in that file. You should not move any of the files out of the ps7image folder. Keeping everything together will ensure that your functions are able to make use of the image-processing module that we’ve provided.

Among the files in the ps7image folder are several PNG images that you can use when testing your functions. They include the following:

test.png:

spam.png:

Important: Both of these images have a one-pixel border; test.png has a blue border, and spam.png has a red one. When you create a new image that is based on one of these images, these borders should help you to ensure that you are transforming the entire image.

Loading and saving pixels
At the top of ps7pr3.py, we’ve included import statements for the following three functions from a separate file called hmcpng.py:

• load_pixels(filename), which takes as input a string filename that specifies the name of a PNG image file, and that returns a 2-D list containing the pixels for that image

• save_pixels(pixels, filename), which takes a 2-D list pixels containing the pixels for an image and saves the corresponding PNG image to disk using the specified filename (a string).

• compare_images(filename1, filename2), which takes two strings representing the names of PNG files and compares the two images to each other. We encourage you to use this function to check the results of your functions.

In addition, we’ve given you two other functions:

• create_green_image(height, width) that creates and returns a 2-D list of pixels with height rows and width columns in which all of the pixels are colored green (i.e., have RGB values [0,255,0]). This is similar to the create_uniform_image function from Lab 9.

• brightness(pixel), which you will use to compute the brightness of a pixel.

We demonstrated load_pixels and save_pixels in Lab 9. We also provided examples of manipulating images represented as 2-D lists. We encourage you to review that material from lab before proceeding.

Your tasks

1. Write a function bw(pixels, threshold) that takes the 2-D list pixels containing pixels for an image, and that creates and returns a new 2-D list of pixels for an image that is a black-and-white version of the original image. The second input to the function is an integer threshold between 0 and 255, and it should govern which pixels are turned white and which are turned black.

   The brightness of a pixel [r,b,g] can be computed using this formula:

   (21*r + 72*g + 7*b) // 100
   

   We’ve given you a helper function called brightness() that you should use to make this computation.

   If a pixel’s brightness (as determined by the brightness() helper function) is greater than the specified threshold, the pixel should be turned white ([255,255,255]) in the black-and-white version of the image; otherwise, the pixel should be turned black ([0,0,0]) in the black-and-white version.

   For example, if you do the following:

   >>> pixels = load_pixels('spam.png')
   
   >>> bw_spam = bw(pixels, 100)
   
   >>> save_pixels(bw_spam, 'bw_spam.png')
   bw_spam.png saved.
   

   you should obtain the following image:
   
   

   After saving the result of your function, you can double-click on the new PNG file in the ps7_image folder to see the image that was produced. In addition, you should verify that the resulting image is correct by using the procedure explained below.

   Notes/hints:

   • Your function will need to create a new 2-D list of pixels with the same dimensions as pixels. You can use the create_green_image function that we’ve provided to create a new 2-D list of green pixels that you then modify.

   • Your function should return the new 2-D list of pixels that it creates.

   • Important: The 2-D list created by create_green_image will be filled with green pixels. If you see unexpected green pixels in your new image (e.g., at the borders of the image), there is a bug in your function that you will need to fix.

   Verifying the produced image
   In the ps7image folder, we have included a PNG file for the expected result of each function that you will write.

   To verify the image produced by your bw() function, you should do the following after executing the lines above.

   >>> compare_images('bw_spam.png', 'bw_expected.png')
   bw_spam.png and bw_expected.png are identical.
   

   If the image produced by your bw() function is identical to the expected result, you will see the message shown above. Otherwise, you will see another message with details about the ways in which the two images differ.

2. Write a function fold_diag(pixels) that takes the 2-D list pixels containing pixels for an image, and that creates and returns a new 2-D list of pixels for an image in which the original image is “folded” along its diagonal.

   For example, if you do the following:

   >>> pixels = load_pixels('spam.png')
   
   >>> fold = fold_diag(pixels)
   
   >>> save_pixels(fold, 'fold_spam.png')
   fold_spam.png saved.
   

   you should obtain the following image:
   
   

   To verify your image:

   >>> compare_images('fold_spam.png', 'fold_expected.png')
   fold_spam.png and fold_expected.png are identical.
   

   Notes/hints:

   • Here again, you should use the green_image function to create a new 2-D list of green pixels that you then modify, and you should return the modified 2-D list.

   • Although we refer to this process as “folding” the image, you will simply need to change the RGB values of the pixels that appear below the diagonal, giving them the RGB values for the color white ([255,255,255]).

   • The pixels along the diagonal are the ones in which the row index is equal to the column index. Those pixels should be left unchanged in the new image; only the pixels below the diagonal should be changed to white.

   • If the image’s height and width are not the same, you won’t obtain a perfect fold. For example, in the folded spam image shown above, the lower right-hand corner of the original image is still present in the folded image. That is to be expected.

3. Write a function flip_horiz(pixels) that takes the 2-D list pixels containing pixels for an image, and that creates and returns a new 2-D list of pixels for an image in which the original image is “flipped” horizontally. In other words, the left of the original image should now be on the right, and the right should now be on the left. For example, if you do the following:

   >>> pixels = load_pixels('spam.png')
   
   >>> flipped = flip_horiz(pixels)
   
   >>> save_pixels(flipped, 'flip_spam.png')
   flip_spam.png saved.
   

   you should obtain the following image:
   
   

   To verify your image:

   >>> compare_images('flip_spam.png', 'flip_expected.png')
   flip_spam.png and flip_expected.png are identical.
   

   Notes/hints:

   • Here again, you should use the green_image function to create a new 2-D list of green pixels that you then modify, and you should return the modified 2-D list.

   • When computing the appropriate coordinates for a flipped pixel, don’t forget that valid (r,c) coordinates for an image of height h and width w are the following:

     0 ≤ r ≤ h - 1
0 ≤ c ≤ w - 1

     Given these ranges, where should a pixel from the leftmost column of a given row end up in the flipped image? Where should a pixel from the second column of a given row end up? Where should a pixel from the cth column of the original image end up?

Problem 4: Creating a simple database program using file processing

25 points; individual-only

Background information
Your task is to create a simple database program that provides access to historical population data for the most populous cities in the United States. The source of our data is a site called peakbagger.com.

Format of the data file
Your program will read from a file like cities.txt — a comma-delimited text file that contains the information needed for the database.

Each line of the file represents one record of the database, and each record has information about a particular city’s population in a particular year.

More specifically, each record has the following five fields:

• the year in which the population was recorded
• the rank of the city in that year, where a rank of 1 indicates the city with the largest population, a rank of 2 indicates the city with the second largest population, and so on.
• the name of the city itself (e.g., “Boston”)
• the abbreviation of the state in which the city is found (e.g., “MA”)
• the approximate population of the city in that year as a multiple of 1000; for example, a population value of 33.1 represents a total population of 33,100. (Strictly speaking, these populations are for the metropolitan areas surrounding each city.)

Because the file is a CSV file, the individual fields are separated by commas.

For example, here are the first three lines of the file that we’ve given you:

1790,1,Philadelphia,PA,44.1
1790,2,New York,NY,33.1
1790,3,Boston,MA,18.3

All of these records are for the year 1790. The first record indicates that the city with the largest population in 1790 (and thus a rank of 1) was Philadelphia, PA, which had a population of 44,100. The second record indicates that the city with the second largest population in 1790 (and thus a rank of 2) was New York, NY, which had a population of 33,100. The third record indicates that the city with the third largest population in 1790 (and thus a rank of 3) was Boston, MA, which had a population of 18,300.

Your tasks
Here are the steps that you should take:

1. Download the following files:

   • ps7pr4.py - a Python file that includes a helper function that you will use in your work on this problem.

   • cities.txt - an example of the type of data file that your program should be able to process.

   Make sure that you put both files in your ps7 folder.

2. In Spyder, open the ps7pr4.py file that you downloaded above.

3. Write a function find_results(filename, city, state) that takes three strings as inputs:

   • filename, which is the name of the data file
   • city, which is the name of the city that we are looking for in the data file
   • state, which is the state abbreviation for the state we are looking for.

   This function should do the following:

   • open a connection to the data file with the specified filename

   • use a loop to process the file line by line, just as we did in lecture

   • inside the loop, use either slicing or the strip method to remove the newline character from the end of each line

   • use the split method to break each line into a list of fields

   • determine which lines are a match for the specified city and state values; if a given line is a match, call the provided output_formatted helper function, passing in the year, rank and population fields. output_formatted will take care of formatting and printing the appropriate line of results for the field values that you pass in. Note: find_results should not print the results itself. Rather, it should make the necessary calls to output_formatted to print them.

   • print an error message if no results for the specified city and state values are found in the data file

   • close the connection to the data file.

   The function should not return a value.

   Here are some examples of how this function should work:

   >>> find_results('cities.txt', 'Boston', 'MA')
   1790    3         18,300
   1810    4         38,700
   1830    3         85,600
   1850    3        308,000
   1870    3        501,000
   1890    4        818,000
   1910    4      1,213,000
   1930    6      1,479,000
   1950    6      2,301,000
   1970    7      2,703,000
   1990    9      3,355,000
   2010    11     4,407,000
   
   >>> find_results('cities.txt', 'Louisville', 'KY')
   1830    16        10,300
   1850    13        61,000
   1870    13       129,000
   1890    18       183,000
   
   >>> find_results('cities.txt', 'Portland', 'OR')
   no results found for Portland OR
   

   Note: You do not need to worry about putting the results into chronological order. You may assume that the records in the data file are ordered by year, and thus you can simply print the results in the order in which you encounter them in the file.

4. Write a function called main that will be used to start the program. This function should not take any inputs, and it should not return a value.

   Like the main function in Lab 8, Tasks 2 and 3 and the tts function in PS 6, Problem 4, your main function should include the user-interaction loop and the input statements that get the necessary values from the user.

   First, main() should begin by using an input statement to get the name of the data file from the user, and you should assign that filename to an appropriately named variable. This step should be performed only once, at the very beginning of main().

   Next, your main() function should use a loop to repeatedly do the following:

   • Use an input statement to get the name of a city from the user. If the user enters the word 'quit', the program should end, which you can do by returning from main().

   • If the user does not enter quit for the city name, main() should use a second input statement to get the city’s two-letter state abbreviation, and it should call your find_results() function to perform the necessary file-processing for the specified city and state.

   • After calling find_results(), main() should print a blank line.

   Your main() function should then repeat these steps until the user enters 'quit'.

In general, your program should behave in ways that are consistent with the sample run that is available here.

Running and testing your program
To run the program, first run your ps7pr4.py file in Spyder, and then make the following function call from the console:

>>> main()

Test your program for a variety of different cases. Make sure that its behavior matches the behavior found in the sample run.

In addition, make sure that your program works for any CSV file that has the same format as cities.txt. In other words, your program should not assume that the name of the data file is cities.txt, but rather it should use whatever filename is entered by the user. To ensure that this is the case, you can test your program using the following data file: cities2.txt

This file is similar to cities.txt, but it only includes data for years after 1900, so using it will lead to fewer lines of results for cities like Boston, MA.

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 ps7pr3.py and ps7pr4.py files under the assignment labeled PS 7: Problems 3 and 4 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 your 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 April 1, 2025.