1. Dr. Awkward: a Palindrome Detector

Write an interactive Palindrome Detector using a recursive algorithm.

"A palindrome is a word or phrase that has the property of reading the same in either direction (the adjustment of punctuation and spaces between words is generally permitted)." ( paraphrased from wikipedia)

% palindrome

Enter palindrome: anna

Yes, anna is a palindrome!

Enter your palindrome: andy

No, andy is not a palindrome!

Enter your palindrome: Rats live on no evil star

Yes, Rats live on no evil star is a palindrome!

Enter your palindrome: I could go for a pizza

No, I could go for a pizza is not a palindrome!

Enter your palindrome: ~quit


%

Guidelines

a. Start by writing a function with the following prototype:

bool isPalindrome(char phrase[], int size);

This function isPalindrome returns true if the phrase of characters stored in the array phrase[] is a palindrome. Assume that the character array is pre-processed and contains no spaces, all of the characters are lower-case, and that the size of the array is exactly given in the parameter size.

This function will contain/utilize a recursive algorithm to tell whether the phrase in the character array is a palindrome. Note that isPalindrome might not be called recursively itself, but it must utilize a recursive function itself.

b. Next, write a function that pre-processes the input from the user to a format that this appropriate for the isPalindrome() function:

int preProcess(char phrase[], int size);

This function preProcess takes the character array phrase[] and removes all spaces, and converts all characters to lower-case. Note, since the spaces are removes, the size of the character array shrinks. The parameter size that is passed into the function is the size of the original character array. preProcess keeps track of the current size of the array, returns the final new size of the altered phrase array.

c. Finally, write a loop in the main() part of your palindrome program, that prompts the user for a phrase to verify that it is a palindrome. Feel free to use any way that we're discussed in class, or from the book to read a line of text from the user.

If the user enters the word "~quit", then the program stops and returns a 0.

Total Points

     The total points for this problem is 3 points.

Extras

Cellular Automata (1 point).

Another use of recursion is to produce fractals and patterns of emergent behavior. Have a look at S. Wolfram's A New Kind of Science Chapter 3: Section 1. (A rather controversial book that came out a couple of years back.) (You might need to register at the site to see the first few pages, but that should be enough to get started).

Write a simple recursive program that takes one of the rules exhibited and generates the output as shown. The output of these simple programs is binary (on or off) - you can use a '#' to draw a filled in square. Assume you have 80 character's breadth for the window and start your cellular automata in the center.

2. Alphabytes Quality Assurance

A large cereal manufacturer has enlisted your programming help to write a Quality Assurance program on the production of their Alphabytes cereal (a breakfast cereal comprised of tasty nutrious letters, numbers, and punctuation marks).

The computer vision system on the assembly line will give your program a large unsorted list of letters, number, and punctuation marks. Your job is to write a program that uses an efficient sorting algorithm to sort the letters, numbers, and punctuation marks according to this order of precedence:

1. Lower Case letters, in alphabetical order (a-z)
2. Numbers in order from 0 to 9
3. UpperCase letters, in alphabetical order (A-Z)
4. Punctuation Marks in this order:

5. a. The Question Mark: ?
   b. The Exclamations Point: !
   c. The Comma: ,
   d. The Point Sign: #
   e. The Schwaa Sign: *
   f. The Period: .

Their computer vision system is susceptible to errors! Thus, reject any whitespace, or other charaters (or non-characters) that may come up.

Once you have all of the Alphabytes sorted. Generate a report with the sorted list of letters, numbers, and punctuation marks accompanied with the number of occurances of each letter, number, and punctation mark.

Make the string "~quit" quit the application.

An small example transaction:

% alphabyte
Ready: !bz Fb5?FF!!!8
Report
b: 2
z: 1
5: 1
8: 1
F: 3
?: 1
!: 4


Ready: ~quit

%

Guidelines

Your supervisor wants to write and test two seperate versions of this program:

1. Using Selection Sort

2. Using QuickSort

Once you have these two versions written you are ready for the time analysis.

Time Analysis

Once you have the two programs written. Do a time analysis on your own set of inputs (test at least 10 cases). Include your report in the header sections of both versions of the program.

Before you do your time analysis, you will have to modify your alphabyte programs. Add an option to receive the input string from the command line as an arguement. You can now use the time utility to measure the running time ofboth versions of your program.

Total Points

     The total points for this problem is 3 points.

Extras

Anagram Machine (1 extra Point):

You can also use the Alphabyte program as the basis for an Anagram Machine. See the Anagram server for details. Given a phrase, the sorted list of letters can act as a key to compare to another phrase's sorted list of letters. If two phrases have identical sorted lists then they are anagrams. Feasibly one can use the sorted list of letters to generate a new phrase comprised out of these letters. (One might want to employ the use of a dictionary of some sort - the unix machine has one "more /usr/dict/words")