# Palindromes are cute, but annoying

Palindromes are numbers or strings with a cute property: If you reverse them, they remain the same. For example,

• 101 is a palindrome.
• 123 is not a palindrome.
• hah is a palindrome.
• haha is not a palindrome.

Reversing a string or integer acts as an intermediate step to check for palindromes. So, it is wise for us to investigate the art of reversing algorithm.

For Python, reversing is easy to handle:

```str = "PROGRAMMING ASAP&amp";

print str[::-1]
```

The code above will print `PASA GNIMMARGORP`.

When the variable is an integer, Python does it effectively too:

```num = 314159
num = str(num)

print num[::-1]
```

The second line converts the variable type of `num` from integer to string. Then, we perform it just as before and it will print `951413`.

However in C++, there will be more coding to do to tackle reversing. For string,

```#include <algorithm>
#include <iostream>

using namespace std;

int main(){
string str = "PALINDROME";
reverse(str.begin(), str.end());

cout << str;

return 0;
}
```

The code above will print `EMORDNILAP`.

That doesn’t look much. The challenging one is reverse an integer in C++:

```#include <iostream>;
using namespace std;

int main() {
int num = 271828;

int rev = 0;
int tmp = num;
while(tmp > 0){
rev = rev*10 + (tmp%10);
tmp = tmp / 10;
}

cout << rev;

return 0;
}
```

The variable `rev` will hold the value of reversed `num`. To check the correctness of the reversing algorithm above, we must show three things about the loop invariant:

1. Initialization : It is true prior to the first iteration of the loop.
2. Maintenance : If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination : When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Initialization : Let $j$ be the number of digit in `tmp`. Before the first loop iteration, it is true that `tmp` has $j$ digits with $d_1d_2...d_j$ while `rev` is empty.

Maintenance : The `for` loop works by adding a space behind `rev` and insert the last digit of `tmp` in it. Then, remove the last digit of `tmp`. This yield an invariant such that the total number of digit in `tmp` and `rev` remains the same.

Termination : After the loop terminates, `tmp` is $d_1d_2...d{j-1}$ while `rev` is $d_j$. After $k$ loop terminations, `latex tmp` will be $d_1d_2...d{j-k}$ while `rev` is $d_jd_{j-1}...d{j-k+1}$. The loop stops when $k = j$, which means `tmp` is $0$.

Way to check the correctness of loop termination follows Introduction to Algorithm.