[Solved] PROGRAMMING ASSIGNMENT #3 CS 2223 PALINDROMES, INVERSIONS, AND BINARY REFLECTED GRAY CODE

1. (10 Points) A palindrome is a word, phrase, or sequence that reads the same backward as forward. Write a recursive C++ program/procedure which determines whether an input sequence (string) from the keyboard is a palindrome or not. There is no need for fancy classes, etc. here. (You can assume the input will be shorter than 256 characters.)

Call your program/project palindromecheck.

Three Bonus Points: Make your program case insensitive, and have your program ignore white space and punctuation:

Never odd or even

Able was I ere I saw Elba

A man, a plan, a canal: Panama!

2. (25 Points) Let A[0..n1] be an array of real numbers (or any ordered set). A pair (A[i],A[j]) is said to be an inversion if these numbers (elements) are out of order, i.e., i < j but A[i] > A[j]. Note that this pair need not be adjacent. The array/sequence (3, 2, 1) contains three inversions: (3,2), (2,1), and (3,1).

(10 Points) Write a program with a nave O(n²) algorithm that counts the number of inversions in such an array A. Hint: Bubblesort is O(n²). Call your program/project easyinversioncount.

(15 Points) Write a program with a O(nlogn) algorithm that counts the number of inversions in such an array A.

Call your program/project fastinversioncount. (Hint 2 to followWednesday )

1

3. (15 Points) Binary Reflected Gray Code

Professor Wolfe has four children: Alice, Bob, Chris, and Dylan. Each year for Arbor Day the family goes on a tree-planting picnic, and Professor Wolfe takes photos of the kids in every possible subset arrangement with the new trees they have planted as a backdrop. Its a lovely tradition. However, last year with newborn Dylan things got more complicated. In transitioning from photograph 7 (0111) to photograph 8 (1000), Professor Wolfe placed baby Dylan on the picnic blanket while all the other children got up and left the scene. Mayhem ensued. Bob and Chris started chasing each other with rakes, and Alice complained about having to move every time a photo was to be taken.

This year is going to be different. Instead of using a binary counting sequence to ensure that all the subset arrangements are made, Professor Wolfe is going to use the Binary Reflected Gray Code of order four. In this way, each transition from one subset of children to the next can be made by having just one child enter or leave the tableau:

• (5 Points) Using C++, implement algorithm brgc(n) on page 148 of Levitin to produce the Binary Reflected Gray Code of order n.
• (5 Points) Add to your routine (or write a separate one using the idea in Problem 9b on page 149 of Levitin) to create a sequence of names representing which child must move when.

The partial sequence up to six is: Alice, Bob, Alice, Chris, Alice, Bob,

• (5 Points) Put it all together to complete the table above for all 15 photos Professor Wolfe wants to take. You can even start at 0=0000, if you like.

Call your program/project graycodesarefun.

Where have we seen this before? How many interesting patterns can you find?

Can you extend your code to Eve? Felix? Gerry? Helen? Ian? Jane? Karl?