CS 102 LAB5 Recursion


new: Find a sample implementation of the merge method at the bottem of this page.

Introduction:

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.



Preparation:

Before you begin, look over your notes, review Chapter 17 on recursion as well.

Lab Tasks:

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.

Specification for the project:

At a high level:

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)

  1. decides that this input is a pallendrome or
  2. sorts the input into acending order using merge sort. (to make things easier you can design your program to sort only numeric input, or you may decide to work with strings, its your choice)
Specifically:

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.

 

Beginning your Coding:

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.

Submitting:

What to submit:

You need to submit all your source code for this project, along with the makefile (if any) and a README.txt file
The README.txt file should contain the following information.


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.

Due Date:

UML and function descriptions due by 5pm Friday April 29th.

The rest of the lab is

Due By Midnight Friday   May 6th

Merge Function:

 

//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;
}
}