Problem Set 5 - Due Friday March 8


  1. Slides and notebooks from Lec 08 (Sequences and Loops), Lec 09 (Iteration, Part 1), and Lec 10 (Lists, Memory Diagrams, and Mutable vs. Immutable Sequences).
  2. Problems and solutions from Lab 05: Loops and Lab 06: Lists
  3. Think Python, Ch. 8: Strings
  4. Think Python, Ch. 7: Iteration
  5. Think Python, Ch. 9: Lists

About this Problem Set

This problem set will give you practice with sequences (strings and lists), operations on sequences, loops on sequences, loops with graphics, and list memory diagrams.

  1. In Task 1 (Partner-Recommended task), you will create your own functions that use loops to analyze and manipulate strings. Use this shared Google Doc to find a pair programming partner and record your partner. Remember that you can talk with other people about high-level problem-solving strategies, but sharing code in an Honor Code violation.)

  2. In Task 2 you will create your own function that uses loops to generate pictures with repeating elements from cs1graphics.

  3. In Task 3, you will study the connection between Python code and memory diagrams for lists to practice the concepts of mutability and aliasing. For subtask 3c, you need to draw a memory diagram on the template page provided to you. You can either submit the scanned version of your diagram or submit a hard copy. See details and submission instructions.

Other notes:

All code for this assignment is available in the ps05 folder in the cs111/download directory within your cs server account. This assignment also uses the Codder program to help you do a final check for Tasks 1, 2, and 3 before you submit.

Task 1: Word Play

In this problem, having a partner is optional, but is strongly recommended. If you want to find a partner, use this shared Google Doc.

In this task you will flesh out the definitions of various word-related functions in the provided file

Subtask 1a: Scrabble Score

What is the Scrabble value of a word? In this subtask, you will determine this by adding the points assigned by Scrabble to each letter, which are:

A = 1 B = 3 C = 3 D = 2 E = 1 F = 4
G = 2 H = 4 I = 1 J = 8 K = 5 L = 1
M = 3 N = 1 O = 1 P = 3 Q = 10 R = 1
S = 1 T = 1 U = 1 V = 4 W = 4 X = 8
Y = 4 Z = 10

You will do this by fleshing out the following two functions in

def scrabblePoints(letter):
    """Returns the Scrabble score of a particular letter (a single-character
    string), as determined by the table in the PS05 Task 1a description.
    Case of the letter does not matter. Returns 0 for nonletter characters.
    # Flesh out the body of this function

def scrabbleScore(word):
    """Returns total number of Scrabble points that word is worth,
    as determined by the table in the PS05 Task 1a description.
    This function must call scrabblePoints.
    # Flesh out the body of this function


In []: scrabblePoints('s')
Out[]: 1

In []: scrabblePoints('E')
Out[]: 1

In []: scrabblePoints('c')
Out[]: 3

In []: scrabblePoints('Q')
Out[]: 10

In []: scrabblePoints('5')
Out[]: 0

In []: scrabblePoints('?')
Out[]: 0

In []: scrabblePoints(' ')
Out[]: 0

In []: scrabbleScore('cat')
Out[]: 5

In []: scrabbleScore('QUIZ')
Out[]: 22

In []: scrabbleScore('juxtapose')
Out[]: 25

In []: scrabbleScore('Wellesley')
Out[]: 15

In []: scrabbleScore("I'm 3LI73!") # Nonletter characters have score 0
Out[]: 6



Subtask 1b: Mystery Speech


What would English sound like if we were not allowed to use each letter more than once in a sentence? Would one still be able to understand it? Let's try it out with some famous (or not) phrases. Can you guess them? (The phrases are shown at the end of this subtask).

In []: keepFirstLetter(somePhrase1)
Out[]: 'To be r n  '
In []: keepFirstLetter(somePhrase2)
Out[]: 'The king s da, lo v  !'
In []: keepFirstLetter(somePhrase3)
Out[]: 'We ar nv  gti bck oh'
In []: keepFirstLetter(somePhrase4)
Out[]: 'Only Victr s kd xeg a pu f h j q   BMW   z'
In []: keepFirstLetter(somePhrase5)
Out[]: 'Quizes ar dfclt o py n wv xh, b g mk j.'

In this subtask, you'll flesh out the body of the function keepFirstLetter which transforms string phrases as shown above. This function is also part of the file.

def keepFirstLetter(phrase):
    """Returns a new string that contains only the first occurrence of a
    letter from the original phrase.
    The first letter occurrence can be upper or lower case.
    Non-alphabetic characters (such as punctuation and spaces) are unchanged.

There are different approaches for writing the keepFirstLetter function, but we want you to use a particular approach indicated by the iteration table in the next subsection.

Iteration Tables

Before writing any code for a function that involves a loop, it's a good idea to get clear in your mind how the loop is going to solve the problem at hand.

As presented in slides 14--15 of Lec 09 (Iteration 1), iteration tables are a great way to do this. So in this subtask you will use an iteration table to help you think about how to design the loop you'll need in keepFirstLetter.

Below is an iteration table example for the keepFirstLetter function on the input string:

'Amy says, "Me?"'

char lettersSeen newPhrase
'' ''
'A' 'a' 'A'
'm' 'am' 'Am'
'y' 'amy' 'Amy'
' ' 'amy' 'Amy '
's' 'amys' 'Amy s'
'a' 'amys' 'Amy s'
'y' 'amys' 'Amy s'
's' 'amys' 'Amy s'
',' 'amys' 'Amy s,'
' ' 'amys' 'Amy s, '
'"' 'amys' 'Amy s, "'
'M' 'amys' 'Amy s, "'
'e' 'amyse' 'Amy s, "e'
'?' 'amyse' 'Amy s, "e?'
'"' 'amyse' 'Amy s, "e?"'

An iteration table has these features:

Your Task

Flesh out the body of the function keepFirstLetter in so that it implements the strategy indicated by the above iteration table. In particular, it should use a for loop with iteration variable named char that updates two state variables named lettersSeen and newPhrase.



Fun Ungraded Challenge:

If you manage to create a meaningful English phrase which after passing through keepFirstLetter contains all the letters of the alphabet, please post it to the Google Group. We will add them to the mystery phrases for the next semester. *Credit to Riley Rettig and Jennifer Chang for creating somePhrase4; Alissa Tinney and Isabel Bryant for creating somePhrase5.

Subtask 1c: Word Properties

We are interested in some fun properties of written words.

  1. Does the word use only the top row of keys (i.e., 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p') on the keyboard? Examples are typewriter and pretty.
  2. Does a word contain at least three vowels in a row? Examples are beautiful and delicious.
  3. Does a word contain exactly one occurrence of each of the five vowels? Examples are education and tambourine.

Your task is to flesh out the definitions of these three functions in

def isTopRow(word):
    """This predicate determines if word can be spelled using only letters in      
    the top row of the  keyboard: q, w, e, r, t, y, u, i, o, p.                    
    Returns a boolean.
    # Flesh out the body of this function

def isBeauteous(word):
    """Call a word "beauteous" if it contains at least three consecutive vowels.
    'beauteous' itself is beauteous (both 'eau' and 'eou'), but so are.
    'delicous' (iou) and 'sequoia' ('uoia'). In contrast,
    'aardvark', and 'nation' are not.
    This predicate returns True if word is beauteous and False otherwise.
    # Flesh out the body of this function

def isPrecarious(word):
    """Call a word "precarious" if it contains exactly one of each of 
    the five vowels (aeiou), not necessarily in order. Examples of such 
    words are 'precarious', 'education', 'facetious' (has them in order!)
    'tambourine', 'authorize', and 'sequoia'. In contrast, 
    'auction' (no 'e'), 'precautionary' (two 'a's), and 'insidious' 
    (five vowels, but three are 'i's) are not precarious. 
    This predicate returns True if word is precarious and False otherwise.
    # Flesh out the body of this function


As shown below, your Your functions should not be sensitive to capitalization.

In [2]: isTopRow('typewriter') # topRow words use only top row keys
Out[2]: True

In [3]: isTopRow('Pretty')
Out[3]: True

In [3]: isTopRow('QUIP')
Out[3]: True

In [4]: isTopRow('bunny')
Out[4]: False

In [5]: isTopRow('sequoia')
Out[5]: False

In [6]: isBeauteous('delicious') # Beauteous words have at least 
Out[6]: True                     # three consecutive vowels

In [7]: isBeauteous('sequoia') 
Out[7]: True

In [8]: isBeauteous('education') 
Out[8]: False

In [9]: isBeauteous('amnesia') 
Out[9]: False

In [10]: isPrecarious('education') # Precarious words have 
Out[10]: True                      # exactly one of each vowel

In [11]: isPrecarious('sequoia') # 'sequoia' is both beauteous *and* precarious!
Out[11]: True

In [12]: isPrecarious('auction') # No 'e'
Out[12]: False

In [13]: isPrecarious('precautionary') # Six total vowels covering all five, but with two 'a's
Out[13]: False

In [14]: isPrecarious('insidious') # Five vowels, but no 'a' or 'e'
Out[14]: False




Task 2: Concentric Circles

This is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

In this task, you will create a Python file named and define in it the three functions concentricCircles, showConcentricCircles, and circleRow.

Your file should begin with this header, which you should fill out:

# Your name:
# Your username:
# CS111 PS05 Task 2
# Submission date:

You should also import cs1graphics via the following line at the beginning of your code:

from cs1graphics import *

Subtask 2a: concentricCircles

In this subtask, your goal is to generate pictures like the following:

paper1 = Canvas(200, 200)
cybla = concentricCircles(200, 5, 'cyan', 'black')
cybla.move(100, 100)
paper2 = Canvas(400, 400)
grellow = concentricCircles(400, 8, 'green', 'yellow')
grellow.move(200, 200)
paper3 = Canvas(500, 500)
pima = concentricCircles(500, 2, 'pink', 'magenta')
pima.move(250, 250)
paper4 = Canvas(500, 500)
reblu = concentricCircles(500, 13, 'red', 'blue')
reblu.move(250, 250)

In, define the function concentricCircles that fulfills the following contract:

def concentricCircles(size, numCircles, color1, color2):
    """Creates and *returns* a Layer containing numCircles
    circles, all of which are centered at (0,0).
    Let r be the radius of the smallest circle. Then the radii of
    the circles grow in arithmetic progression -- r, 2r, 3r, etc. --
    up to the radius of the largest circle, which is size/2.
    The smallest circle is filled with color1 and afterwards the colors 
    alternate between color1 and color2.



Subtask 2b showConcentricCircles

If you look at the 4 statements (shown in gray boxes in Task 2a above) that are used to generate each of the concentric circles, you'll note there is a pattern. Capture that pattern by writing a function called showConcentricCircles in the file that fulfills the following contract:

def showConcentricCircles(canvasSize, numCircles, color1, color2):
    """Creates and *returns* a canvasSize x canvasSize white canvas containing
    numCircles concentric circles, with the smallest circle having color1
    and alternating with color2. The title of the canvas should
    be a string representation of the invocation of the showConcentricCircles
    function that created the canvas.

For example, the following invocation produces the canvas below (note the title):

    showConcentricCircles(500, 13, 'red', 'blue')


Subtask 2c: circleRow {task2c}

In this task, your goal is to generate pictures like the following:

single = circleRow(1, 500, 7, 'orange', 'yellow')
triple = circleRow(3, 400, 10, 'red', 'pink')
quint = circleRow(5, 240, 8, 'blue', 'green')
dozen = circleRow(12, 100, 10, 'black', 'white')

In your file, define a function circleRow that fulfills the following contract:

def circleRow(numCirclesInRow, size, numCircles, color1, color2):
    """Creates and *returns* a numCirclesInRow*size x size white canvas 
    containing numCirclesInRow circles, each of which is a concentric circle. 
    The distance between the center of each circle is size. The title of the 
    canvas should be a string representation of the invocation of the circleRow 
    function that created the canvas.



Task 3: Memory Diagrams

This is an individual problem that you must complete on your own, though you may ask for help from the CS111 staff.

This problem involves memory diagrams. You should review the notation and conventions for memory diagrams explained in Lec 10 before starting this problem.

Subtask 3a: Matching Code to Memory Diagrams

In this subtask you are given these 20 code snippets (named CODE01 through CODE20) and these 10 memory diagrams (named A through <span style="color:magenta;font-weight:bold;"">J). Your goal is to match each code snippet with the corresponding memory diagram. (A single diagram might be generated by multipled snippets.)

This subtask is based on a midterm exam problem given during a previous semester. The goal of the problem was to write a sequence of statements to create memory diagram A:

There were a dizzying number of solutions, some of which created memory diagram A, some of which created other memory diagrams, and some of which generated errors. The code snippets CODE01 through CODE20 are adapted from actual student solutions to this problem.

You will express your answers in the given file by assigning the given variables CODE01 through CODE20 (initially defined to be the value None) to be one of the strings 'A' through 'J' (to indicate that it creates the diagram named by that string).

For this subtask, running Codder will check that all of your variables are defined to be valid strings, but it will not tell you whether or not your answers are correct. That will be done only during the final grading phase.

Subtask 3b: Modifying Memory Diagram A

Assume that the value of variable x is the list with memory diagram A:

In this subtask, you will flesh out the body of the function A_to_K in that takes as its single parameter a list named L, and modifies it in such a way that after calling A_to_K(x), the structure of x has been changed to that of memory diagram K:

In the body of A_to_K, your code should satisfy the following restrictions:

For this subtask, running Codder will check that your A_to_K function satisfies the above restrictions and performs the correct modifications when called on the list x from diagram A and will report any discrepancies.

Subtask 3c: Drawing a Modified Memory Diagram

Assume that the value of variable x is the list with memory diagram A:

In this subtask, you will draw the final memory diagram that shows the structure of the list x after executing the following sequence of statements:

x[3] = [x[1], x[0], x[2][0]]
x[1].insert(0, x[2])
x[2][0] = x[2][1] + x[1][1] + x[3][0][0][0] 

You must draw your memory diagram on the following template page. We will hand out copies of this page on the day of Lec 10 (Tuesday, March 5) when this topic will be covered. Alternatively you can download and print it from this link.


Task 4: Honor Code Form

As in the previous psets, your honor code submission for this pset will involve defining entering values for the variables in the file.

How to turn in this Problem Set

Hardcopy (paper) submission

You may submit the solution page of subtask 3c as a hard copy by sliding it under the door of room E114 (Shikha Singh's office) by 11:59 pm on the DUE DATE = Friday, March 8, 2019. You must still draw the memory diagram on the following template page.

If submitting a hard copy, take a picture or make a copy of your solution so you can compare it to our solution before grading is finished.

Softcopy (electronic) submission