This lab will give you the opportunity to write recursive solutions to two problems. You will also have the opportunity to do more design work in this project than in previous projects.
The important concepts in this lab.
Note that during the last part of class we will discuss merge sort, an application of recursion useful in the real world. If you miss this discussion, please see a class mate for the notes and see your instructor during office hours.
First read the specifications for the project given below. Then think about a good solution. The specification below spells out (some of ) the classes required, so you don't have complete freedom, but then neither do you have the opportunity to go too far afield in your first design in this class.
Once you have a design in mind, visualize that design and the
relationships between the classes using UML. The UML,
along with a brief description of what each function listed in the uml
will do, is due by Friday April. 29th at 5pm. If you are way
off, you will hear back by the end of Saturday, otherwise you will get
some small pointers by the end of the weekend.
You can either submit this to me on paper, or if you draw it online,
you can submit it by email.
In this project you will write a program that reads in input from a
user and then does one of two things (the program must be capable of
both - but only needs to do one on any given run)
Ask the user which of the two actions to perform.
Then read in input from the command line, and reply with the appropriate output.
You will need at least three classes.
You will need a class to model the user interface. This class is in charge of asking the user, what task is to be done, prompting the user for correct input,
You need a class to model the object that will be in charge of the data, reading input in, and validating that input and prompting the user to fix/replace bad input.
You must have another class that uses a recursive merge sort to sort the data. You must also place the palandrome checker somewhere.
You may request to break some of the above functionality into additional classes. These represent the bare minimum of three classes for the project.
Palandromes for the pupose of the lab, ignore spaces. That is "a da" is just as much a palandrome as "ada" is.
Think about what will be needed at each step. You need to be able to read an entire line of input for the palandrome checker (think "madam Im adam"). Then will you "clean up" the input using the string classes replace method? (I strongly encourage you to use strings for this) Or will you handle the spaces in your recursive palandrome checker?
Also what about the merge sort,? You will need an array at some point in the merge sort. Will you use an array of strings? and array of ints? You will probably need the string class's substr method in either case
When you have your design sketched out, produce the UML for the design.
Because you are designing this solution largely yourself, you are encouraged to find your own best beginning point for writing your code. However, your UML is an excellent place to start. Choose one of the classes in the UML, and write the header file for that class from the UML.
when you are done, write the readme.
When you are ready to submit, zip up your lab4 directory. Go to your
home directory and do the following.
zip -r Lab5Solution.zip lab5
and submit it.
(best way is probably email, in which case you can ftp your zip file
to your webhost (w:) drive and submit it as an attachement.
UML and function descriptions due by 5pm Friday April 29th.
The rest of the lab is
Due By Midnight Friday May 6th
//this method works on an array of ints (you could change it to be an array
of strings if you like easily)
//It assumes an instance variable in the Sorder class called numbers that is
an array of numbers.
// the method assumes that the array from left (called low in class) to mid-1
is sorted, and from mid to right
//is sorted.
void Sorter::merge(int left, int mid, int right)
{
int temp[right -left]
int i, left_end, num_elements, tmp_pos; left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
//This version of the merge function first puts all of the sorted data into
the array
// temp called temp. There is no need to copy the data in numbers to temp at
this time.
//merge together the existing data, making sure that we run off neither sub-array.
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
//once the code above has been executed, one of the two subarrays is empty.
//if it is the low end sub array, copy the low end sub array onto the end of
the
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
//now do the same thing if it is the right end sub array that still had data
left
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
//now copy the data back into the numbers array. I've left this here rather
than
//making you do its yourselves because it is an unusual but nice way of doing
the
//copy.
for (i=0; i < num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}