## Description

csce350 — Data Structures and Algorithms

Project 4: Hannah and Otto

For this assignment only, late submissions will be accepted without penalty until 11:59pm on December 8.

The purpose of this assignment is to give you some practice designing and implementing an algorithm based on the

dynamic programming algorithm design strategy.

The Problem Hannah and her friend Otto like palindromes.1

In fact, they like palindromes so much that,

when they see a word that is not a palindrome, they each wonder about how to insert letters into that word to

make it into a palindrome. They are willing to insert characters that the beginning, the end, or the middle of

any word. That’s why Hannah and Otto want a program that will read a list of words and compute the shortest

palindrome that can be formed by inserting letters into each word. Here are some examples.

Word Letters to insert Resulting palindrome

roger E, G rEGoger

mimi I Imimi

benny E, B, Y YbennEBy

Your task Your job is to write a program that uses dynamic programming to solve this problem. Specifically,

you should write a C++ program that does precisely these things:

1. Read a word, consisting of a sequence of lowercase letters, from standard input.

2. Compute the length of the shortest palindrome that can be formed by inserting characters into that word.

Compute the palindrome itself, using uppercase for the inserted letters. If there is more than one shortest

palindrome—which happens often—compute the one that is alphabetically first.2

3. Print a line containing the length and the palindrome itself, separated by a space.

4. Return to Step 1 above to read and process another instance. Terminate when standard input reaches

end-of-file.

Here are a few example inputs with the correct output for each one.

Sample Input 1

leonardo

michelangelo

donatello

raphael

splinter

april

casey

shredder

kraang

Sample Output 1

13 leoDRAnardoEL

21 OLmicheGNAlangeHCIMlo

14 donatellETANoD

11 LEraHphaRel

15 RETNILPsplinter

9 LIRPapril

9 YESAcasey

10 shredderHS

10 GNkraaRKng

An additional much longer sample input, along with its correct corresponding output, is available on the

course website.

1You will probably recall that a palindrome is a string that reads the same both forward and backward.

2

Specifically, use the ASCII ordering, in which capital letters come before lowercase letters.

csce350 Project 4: Hannah and Otto 1 of 3

Some hints

1. Focus first on finding the length of the shortest palindrome, rather on computing the shortest palindrome

itself. When you get this part, not only will you have already earned substantial partial credit, but you

should also have a much better idea about how to compute the palindromes themselves.

2. A correct dynamic programming solution to this problem should take Θ(n

2

) time. For comparison, my

solution takes about 1.5 seconds on my laptop to solve the 62,886 instances in project4-2.in. Though

the specific speeds are not too important, if your program takes more than a few seconds on this input,

something is wrong.

3. Because your solution should use dynamic programming, the first step is to write a recurrence that

describes the solution you want to compute, in terms of the solutions to smaller subproblems. Since this

is a string problem with a single input S[0, . . . , n − 1], one natural place to start is to think about all of

the substrings of S. To define a substring, we need to know the position of its first character and its last

character, which we’ll call i and j respectively. Based on that idea, we can define p(i, j) this way:

Let p(i, j) denote the length of the shortest palindrome that can be formed by inserting into S[i, . . . , j].

Then to solve our original problem, we simply need to compute p(0, n − 1).

4. Next, we need to figure out how the p values are related to each other. That is: Given values for i and j,

can we write an equation for p(i, j) in terms of other p values?

In this case we are interested in the shortest palindrome that can be formed from S[i, . . . , j]. Let’s call

that string Xi,j . We know, from the definition of the word palindrome, that the first and last letters of

Xi,j are the same—otherwise, Xi,j would not be a palindrome. We also know that every character in Xi,j

comes from one of two places: It could be a character originally from S (these are shown in lowercase in

our examples) or it could have been inserted to complete the palindrome (which we show in uppercase).

These two possibilities, applied to the first and last characters of Xi,j , give us four cases.

case first character of Xij last character of Xij

1 original original

2 original inserted

3 inserted original

4 inserted inserted

Let’s think about each of these cases, in order.

• Case 1: This case refers to the situation in which both the first and last characters of Xij are originals.

If that’s true, then we know that Xi,j looks like this:

Xi,j = S[i]Xi+1,j−1S[j]

This is useful, because it begins to connect the solution for (i, j) to the solution to a smaller subproblem, specifically to (i + 1, j − 1). However, this case only applies when S[i] = S[j], because otherwise

we would not be getting a palindrome.

• Case 2: Next, suppose that the first character of Xi,j is an original, and the last one was inserted to

match it. If that’s true, then we know that Xi,j looks like this:

Xi,j = S[i]Xi+1,jS[i].

Again, this gives us a connection to a smaller subproblem.

csce350 Project 4: Hannah and Otto 2 of 3

• Case 3: The last character of Xi,j is an original, and the first one was inserted to match it. This is just

like Case 1, but in reverse:

Xi,j = S[j]Xi,j−1S[j]

• Case 4: Both the first and last characters of Xij were inserted. This case never happens in shortest

palindromes, because if it did, we could get a shorter palindrome by deleting the first and last

characters. Therefore, we can completely ignore this case.

That leaves three possibilities. How do we know which one forms the correct palindrome? Since we

want the shortest palindrome, the answer is to try each one, and keep the one that leads to the shortest string.

All of this is enough to write our recurrence for p(i, j). We take the general forms for Xij from above,

and add up the length of each of those strings;

p(i, j) = (

min {p(i + 1, j − 1) + 2, p(i + 1, j) + 2, p(i, j − 1) + 2} if S[i] = S[j]

min {p(i + 1, j) + 2, p(i, j − 1) + 2} if S[i] 6= S[j]

.

The +2 terms come from that fact that we are adding two additional characters—one at the front and one

at the back—to the smaller string (either Xi+1,j−1, Xi+1,j , or Xi,j−1) that we expand to get Xij . It turns

out, though, that if Case 1 applies, that it always will be the shortest length. That allows us to simplify

the recurrence a bit, by leaving Cases 2 and 3 out of the top line:

p(i, j) = (

p(i + 1, j − 1) + 2 if S[i] = S[j]

min {p(i + 1, j) + 2, p(i, j − 1) + 2} if S[i] 6= S[j]

This simplified version has a box around it because that formula is the most important thing in this document—a correct solution to Project 3 will come from turning that recurrence into an implemented algorithm.

5. Now that we have a recurrence, there are a few issues left to resolve.

(a) We need two loops to fill in the dynamic programming table, one for i and one for j. What are the

correct upper and lower bounds for each loop? Should they be increasing or decreasing? What size

should the table be?

(b) What is the base case (or base cases) for p?

(c) Given the completed DP table, how can you compute the correct shortest palindrome? (Alternatively, can you build the correct palindrome along the way?)

These details are left for you to resolve, but feel free to ask for help.

Notes A few possibly helpful comments:

• For calibration purposes, my solution has 66 lines of code. Yours may be longer, but if you find yourself

writing huge amounts of code, something has probably gone wrong.

• Keep in mind that you are expected to submit your own original work for this problem. Accessing

reference material for C++ in general is fine and encouraged. However, you are strongly discouraged

from conducting web searches for code specific to palindromes.

What to Submit You should submit, using the department’s dropbox website, a single C++ source file containing all of the code for your program. We will compile this program using this command line:

g++ -Wall -std=c++11 yourfile.cpp

csce350 Project 4: Hannah and Otto 3 of

3