Problem Set 5 FAQ

Problem 1 (Caesar cipher/decipher)
Problem 2 (More algorithm design)

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

Problem 1 (Caesar cipher/decipher)

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.
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.
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 2 (More algorithm design)

My index function works in some cases, but not in others. Do you have any suggestions?

As usual, it can help to consider some concrete cases. For example, let’s assume that you’re taking our typical approach and making recursive calls on a slice that includes everything but the first element.

Consider the initial call index(5, [2, 3, 4, 5, 6, 7]). It will involve a series of calls:
```
index(5, [2, 3, 4, 5, 6, 7])
index(5, [3, 4, 5, 6, 7])
index(5, [4, 5, 6, 7])
etc.
```
Given those calls, ask yourself two questions:
- How far do the recursive calls need to go? Do they need to go all the way to the empty list, or is it possible to stop earlier? If it is possible to stop early in some cases, make sure to include the base case(s) that will do so. If not, make sure to have a base case for the empty list. Remember that you are not allowed to use the in operator in this function.
- What do I need to do with the value that is returned by the recursive call? Remember that the recursive call is solving a smaller subproblem. How can you use the solution to that smaller subproblem to determine the solution to the original problem? For the example above, how could you use the solution to the subproblem index(5, [3, 4, 5, 6, 7]) to determine the solution to index(5, [2, 3, 4, 5, 6, 7])?
Next consider the initial call index(8, [2, 3, 4, 5, 6, 7])– which is a call in which the value does not appear in the list at all. It will involve a series of calls:
```
index(8, [2, 3, 4, 5, 6, 7])
index(8, [3, 4, 5, 6, 7])
index(8, [4, 5, 6, 7])
etc.
```
Given those calls, ask yourself two questions:
- How far do the recursive calls need to go? Do they need to go all the way to the empty list, or is it possible to stop earlier? If it is possible to stop early in some cases, make sure to include the base case(s) that will do so. If not, make sure to have a base case for the empty list. Remember that you are not allowed to use the in operator in this function.
- What do I need to do with the value that is returned by the recursive call? Remember that the recursive call is solving a smaller subproblem. How can you use the solution to that smaller subproblem to determine the solution to the original problem? For the example above, how could you use the solution to the subproblem index(8, [3, 4, 5, 6, 7]) to determine the solution to index(8, [2, 3, 4, 5, 6, 7])?
Finally, keep in mind the following hint from the problem:

When deciding what to do after the recursive call returns, you will need to base your decision on the result of the recursive call.

That means that you will need an if statement in the recursive case, and it needs to have a condition that is based on the result of the recursive call. In other words, you need to look at the value that is returned by the recursive call in order to decide what you should return.
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?