You're familiar with several of Python's types including strings, lists, tuples,

and dictionaries. You also know how to use a variety of

operations, methods, conditional statements, and loops.

This lecture isn't about learning any new Python features.

It's about solving a problem by exploring several approaches to it and using what

you already know. In this lecture, we're going to focus on a

single problem. The problem is determining whether a

string is a palindrome. A palindrome is a string that is read the

same from front to back and back to front. For example, noon and racecar are both

palindromes. Before we start to write any code, we need

to decide which approach we'll take to solve this problem.

We're going to explore several different approaches for determining whether a

string is a palindrome. These approaches are called algorithms.

An algorithm is a sequence of steps that accomplish a task.

For our first approach, we revisit the definition of palindrome.

A palindrome is string that is read the same from front to back, and back to

front. That means that if we have a string, and

we reverse it, it's a palindrome, if the original and the reverse are the same.

Let's consider a couple of examples. The first example is noon.

Noon, reversed. We're beginning with the last letter in

the original, becoming the first letter in the reverse string, and so on.

The original string and the reverse string are the same so this is a palindrome.

Next, let's look at racecar. We'll begin by reversing the string, the r

becomes the first letter followed by a, and the original string and the reverse

string are equal, so this is also a palindrome.

One more example, dented. We begin by reversing the string d,

followed by e. This time, the 2 strings are not the same

so this is not a palindrome. Now, we'll take a different approach to

solving the same problem. We're going to start this time by

splitting the string into 2 halves. We'll then reverse the second half of the

string, so o, n will become n, o. We compare the first half of the original

string with the second half reversed. If they're the same, the string is a

palindrome. We'll do this again for racecar.

Racecar has an odd length. So, it's not clear which half the e should

belong in. We're actually not going to include it in

either. We're going to take the string, half of

the string before e and the other half of the string after e, and omit the e

altogether. We'll then reverse the second half getting

r, a, c and compare the first half of the original with the second half reversed to

confirm that it's a palindrome. Finally, we'll do the same thing for

dented. We split the string in half, reverse the

second path, compare the first half to the second half reversed, and this time

they're not the same, so this is not a palindrome.

Let's consider one more approach. In this approach, we're going to compare

pairs of characters. We'll start by comparing the first

character to the last to see whether they're the same.

Then, we'll compare the second character to the second last, and we stop when we

reached the middle of the string. If all of the pairs of characters are the

same, then the string is a palindrome. Let's do the same thing for racecar.

We begin by comparing the first character to the last, then the second to the second

last, third to the third last, stopping when we reach the middle of the string.

All of the pair, pairs of characters are the same, so this is also a palindrome.

And finally, dented. In this case, the first two pairs of

characters are the same, but the third character is not the same as the third

last so this is not a palindrome. There may be other approaches to solving

this problem. But these are three that we thought of.

In upcoming lectures, we'll discuss some features of algorithms that might make one

more desirable than another. For now though, we'll implement all three

of these algorithms. Now, let's follow the steps of the

function design recipe to implement this function.

I'm going to open a new window in which to write the function definition.

The first step of the function design recipe involves writing example calls on

the function in the doc string. To do this, we need to give the function a

name. I'm going to call it, is palindrome.

The function will take one string argument, such as noon, and return a

Boolean indicating whether that string is a palindrome.

In this case, it returns true. It should also return true for the string

racecar. And we expect that when is palindrome is

call, called with the argument dented, that it will return false.

Next, we'll write the type contract. This function takes one string and returns

a Boolean. The third step of the function design

recipe is writing the header. We're using name is_palindrome, and we

need to give a name now to the parameter to this function.

I'm going to call it s. The last part of the doc string is the

description. This function should return true if and

only if s is a palindrome. The last two steps of the function design

recipe involve writing the body of the function and then testing the function.

We are going to complete those two steps in an upcoming lecture.