Problem Set 3 FAQ

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

You may also find it helpful to consult the general questions from the PS 1 FAQ and PS 2 FAQ, and the page we have assembled with info about common Python errors.

Problem 2 (Algorithm design)

1. Can you explain how we are supposed to use num_vowels in our work on most_vowels?

   First, you should copy our num_vowels function into your ps3pr2.py file. It should be its own separate function, just like any other function that you are writing for this problem.

   Then, when writing your most_vowels, you should call num_vowels whenever you need to determine the number of vowels in a given word!

   You will end up with something that looks like this:

   def num_vowels(s):
       """ returns the number of vowels in the string s
           input: s is a string of 0 or more lowercase letters
       """
       if s == '':
           return 0
       else:
           num_in_rest = num_vowels(s[1:])
           if s[0] in 'aeiou':
               return 1 + num_in_rest
           else:
               return 0 + num_in_rest
   
   def most_vowels(words):
       """ your docstring goes here
       """
       ## within your function, call num_vowels as needed!
   

2. When forming the string returned by the message function, how can I include the number of years that someone needs to wait to be legal?

   You will need to turn the number of years into a string. To do so, you should use a built-in function called str(), which will take an integer and turn it into a string. For example:

   >>> x = 3
   >>> str(x)
   '3'
   

Problem 3 (Caesar cipher/decipher)

1. How do I start solving the decipher problem?

   The decipher problem may seem daunting at first, but you have all the tools needed to solve it! Instead of trying to get the whole function to work in a single effort, focus on one step at time–following the guidelines in the problem–and make sure that each step works before going on to the next step. You can utilize temporary print statements in your function to check if you are getting the right values for each step.

   Remember that we do not have the rotation number that was used to encipher the string s. Therefore, we need to generate all possible strings that can be made from rotating s. Recall that rotating a string by n is the same as enciphering a string with n. Since there are only 26 possible rotations, you will make 26 options to choose from.

2. How can I assign a score to each string in decipher?

   Once you have your list of options, you need to determine the score of each option. We have given you a function called letter_prob that determines the probability that a single character occurs in an English phrase. This means that you cannot give an entire phrase to letter_prob. Instead, try to come up with a function called string_prob that takes a string and uses letter_prob to compute the probability score for every character in the string, and that combines these probabilities together in order to return a single probability. This result will be the probability that the string is an English phrase.

   With a function like string_prob you can now calculate the probability score for an entire phrase.

3. How can I pick the most likely option in decipher?

   In lecture, we covered a lists-of-lists technique for problem-solving, and we went over a very similar problem of choosing the scrabble word with the highest score. Look over the best_word function in the lecture notes, and think about how you could take the list-of-lists technique that we used there and apply it to the decipher problem.

Problem 4 (more algorithm design)

1. I’m having trouble with my lcs function. It seems like I should be able to adapt my jscore function, but doing so doesn’t seem to work. Do you have any suggestions?

   We don’t recommend trying to adapt jscore here. For one thing, jscore returns a number, whereas lcs is supposed to return a string.

   Here are some things to keep in mind as you write this function:

   • Make sure to start with your base case(s). When can you know the LCS without needing to look at smaller strings?

   • Make sure to follow the suggested strategy that the problem outlines for the recursive case.

   • In particular, make sure that you start the recursive case by comparing the first characters in the two strings. Note that you want to compare just the first characters, so you won’t be able to use the in operator for this. Instead, you should use indexing to obtain the first character in each string, and then you should use the appropriate operator to see if the two characters match.

   • If the first characters in the two strings don’t match, our suggested strategy recommends making two recursive calls. Each of those recursive calls will return a string result, and you should return the better of the two results. When you compare the results to see which one is better, you should base your comparison on the characteristics of the two strings. Ask yourself: what makes one string result better than another in this context?