CS 102 LAB5 Recursion


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 recitation section 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.


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 still spell 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 Nov. 19th 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.

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

  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)

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.


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 November 19th.

The rest of the lab is

Due By Midnight Tuesday November 30th