cs212 »

Back to course page | CS212 Unit 1 | CS212 Unit 2 | Print this page

CS212 Homework 2


No Leading Zeros

hw2-1 video/ | hw2-1 question code/

In this homework assignment, I want you to modify the function compile.formula so that it rejects any formula where there is a zero as the leading digit in a word. Now, in our first version of solve we took care of that, and we had to because Python would have interpreted 012 as an octal number. In the second version where we use compile.formula, we didn't work about that. Now we want to put that test back in.

If YOU is a word in the formula and the function is called with Y equals 0, the function should return False, even if the arithmetic works out. What I want you to do is modify the following code in any way you want, so that the function that you build up as a string and then compile with a vowel is a function that will correctly return false in this case.

Floor Puzzle

hw2-2 video/ | hw2-2 question code/

In this homework assignment, we have a puzzle, which is similar to the zebra puzzle. I'm calling it the floor puzzle.

We describe a five-floor apartment building in which there are five residents, and there's various constraints on them.

What I want you to do is just write the code to return the proper floor assignment for each of the five inhabitants in that order.


hw2-3 video/ | hw2-3 question code/

In this homework you're going to solve the subpalindrome problem. Now, if you took 101, you saw that a palindrome is a string that reads the same forwards as it does backwards. R-A-D-A-R. R-A-D-A-R.

We're going to allow palindromes where the case of the letters can be different. This would be a good palindrome even though there is a capital R here and a lowercase r there.

Now, some people allow palindromes where the spaces and punctuation don't count. You can throw them in anywhere. We're not going to allow this. We're going to only allow cases where there is an exact match.

This would be a palindrome. It has spaces, but they read the same forwards and backwards. That's a good one, and this would not be a palindrome, because the space does not occur in the same place forward and backward.

Now you know what palindrome is, but the problem is to find a subpalindrome. Here is a string. We want to find the longest palindrome. It turns out that it occurs from here to here.

Now, how would you find that?

The Obvious Way

There's one obvious way to do it. It's to try every possible substring, so try every starting location--here, here, here, and so on-- and every ending location--the string "w" by itself, "wh," "whe," then "h" by itself, "he," "her," and so on. Try every single one and check to see if they're a palindrome.

Now, that would work, but it would be slow.

Big-O Order - Algorithmic Efficiency

If there are N characters in the string, then there's N starting locations and N ending locations, and each of those substrings can have up to N characters. To check all of them out would be an order N-cubed operation. There'd be roughly N-cubed checks that you'd have to make to see if two characters are the same. What we're asking you to do is to come up with a solution that's faster than that that takes in the worst case, roughly N-squared rather than N-cubed comparisons, and in most cases will do better.


When I say operations here, what do I count as an operation? I want you to write your routine so that all you do is pick out characters, so we pass you in a text and you pick out a character--text sub i, text sub j-- and then you can do anything you want with the characters you pick out. You can convert them to uppercase to make it easier to compare if they're the same. You can compare two characters.

All those operations will be free, but we'll be counting how many of these operations you do. Now the trick is to find a good way to go through the text and look at the characters.

How Not to Do It

I'm going to tell you a bad way to enumerate through them, and you're going to have to come up with a good way.

Let's say that we knew that text from i to j is a palindrome. Maybe that's abcba.

If we then said let's try to expand this text and look at the next two characters, we could do that test, but we wouldn't have learned anything about whether or not this is a palindrome given that this is a palindrome. We'd have to do the whole test all over again.

We haven't gained any advantage from what we know about a partial result to expand it to a bigger result.


What we want to do is find some way of saying I know something about a palindrome somewhere in the string, and that's going to help me more efficiently figure out a bigger piece of the string. That's what you're being asked to do.

Function Name, Return Value

I'm going to call our function longest_subpalindrome_slice. A "slice" meaning what I want you to return is the i and j indices of the start and the end, and j should be one character after the end so the same conventions that we use normally in Python such that text[i, j] is the longest palindrome. Why did I return the indices rather than the text itself? Because you might be interested in where in the text the palindrome occurs. If you have i and j, it's easy to pull out the actual palindrome, but if I give you the actual palindrome, it's harder to find where it occurs.


Here what I'm doing is making an abbreviation for this function (L).

def test():
    L = longest_subpalindrome_slice
    assert L('racecar') == (0, 7)
    assert L('Racecar') == (0, 7)
    assert L('RacecarX') == (0, 7)
    assert L('Race carr') == (7, 9)
    assert L('') == (0, 0)
    assert L('something rac e car going') == (8,21)
    assert L('xxxxx') == (0, 5)
    assert L('Mad am I ma dam.') == (0, 15)
    return 'tests pass'

print test()

"Longest_subpalindrome_slice is just a variable which names a function. Now I'm just assigning another variable L to be equal to that.

Now these two refer to the same function.

I can go ahead and do that, and I can fit more tests on one line by using the shorter name rather than the longer name. Write your function so that all the tests pass.

Add any other tests you think are useful and make sure you do it through an efficient recurrence relation.

Palindromes in literature

This thread in the forum sparked some interest in performance.

War And Peace

Has two palindromes of equal length.

"ton did not" - Pierre saw that Platon did not want to understand what the Frenchman was saying

"tut tut tut" - "Tut, tut, tut! Tell that to others," said the officer, waving his finger before his nose and smiling.

Ignoring spaces we have:

"rewseyeswer" - Prince Andrew's eyes were closed, so weary and sleepy did he seem.

King James' Bible

With spaces: od deed do

Without spaces: ullam,Mallu

The Adventures of Sherlock Holmes

"saw i was" - It grew worse as Alice grew up, for he soon saw I was more afraid of her knowing my past than of the police.

without spaces:

"atadatadata" - "Data! data! data!" he cried impatiently.