Problem Set 5 - Due Friday October 11


  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, and submit it in GradeScope. 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 0: Scrambled Solutions

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

This time we have three puzzles for you to solve to review the problem set 4 solutions: One puzzle for each task. Go to:

CS 111 Puzzles

and select each of the options under Problem Set 4. These puzzles will only be made available after ps04 is due.

As before, please download and submit your solution files, and email if you run into trouble.

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

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

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 ten code snippets and six memory diagrams (the code snippets are named CODE0 through CODE9 and the memory diagrams are labeled 'A' through 'F'). Your goal is to match each code snippet with the corresponding memory diagram. (A single diagram might be generated by multiple 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 CODE0 through CODE9 are adapted from actual student solutions to this problem.

You will express your answers in the given file by assigning the given variables CODE0 through CODE9 (initially defined to be the value None) to be one of the strings 'A' through 'F' (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.

You will need to upload it electronically to GradeScope in order to submit it.


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

GradeScope submission

You must submit the solution page of subtask 3c via GradeScope by 11:59 pm on the DUE DATE = Friday, October 11, 2019. You must draw the memory diagram on the following template page.

Electronic submission