Design Due: 7 April.

Project Due: 24 April.

Administrative Information

Complete the following activities. You must work in pairs for the Project. You may not have more than 2 people on a team. If you cannot find a partner, I will appoint one.

All results must be put into the appropriate project folder on the cs174jb nova account.

All programs must have a heading identifying the people who worked on the project. Programs must also contain appropriate comments. See style sheets.

Input

1. The retained criminal information, generated by the previous execution of this program, is input from file "Criminal.mf" at the beginning of each execution of the program.

2. The user inputs commands from the keyboard, in the format shown below. Names and attributes are strings of no more than 20 characters. The program should not be case sensitive (e.g., 'JOE' and 'Joe' are the same name). To simplify the processing, you can assume that names are unique; that is, no two criminals use the same professional handle. The commands are discussed in detail in the Command Processing instructions below.

Output

1. Responses to user commands are to be written to the screen, as described in the Command Processing instructions below.

2. Echoprint each command and show the results of any PRINT commands in a file called "Criminal.trn". You may determine the format of the information in this file; it should be labeled and formatted clearly. A hard copy of this file is turned in with your program for grading.

3. If any new suspects were added (see ADD command), file "Criminal.mf" must be rewritten to contain the updated collection of criminal information.

Command Processing

New suspects can be added to the collection of criminal information using the ADD command. An inquiry consists of a set of commands with respect to a single crime, at the end of which the crime is assumed to be solved. An inquiry must be completed within the execution of the program; it cannot be "saved" to finish on a subsequent execution. After an inquiry is complete, a new inquiry (the investigation of another crime) can begin. Each new inquiry starts over with the entire collection of suspects.

• ADD Add a suspect to the Suspects data structure. Prompt the user for the suspect's name and a list of attributes. ADD commands can be issued only before an inquiry begins.

• INQUIRY Prompt user for code name of this inquiry. Once the inquiry has begun, do not allow the user to issue the ADD command until this inquiry is complete.

• TIP Prompt user for the tip information (a particular attribute). Process the tip, reducing the set of current suspects by deleting suspects who do not match the attribute mentioned in the tip. If there is only one suspect left in the set of active suspects, print out a message indicating that the crime is solved. Be sure to include the suspect's name and inquiry code name. This terminates the current inquiry.

• CHECK Prompt the user for a suspect's name. Check the set of active suspects to see if this name is there; print out an appropriate response.

• PRINT Print the set of active suspects (those who have not yet been eliminated). You will actually just print to a file.

• QUIT If any new suspects have been added during this execution of the program, rewrite the "Criminal.mf" file. Be careful about how you go about saving the records; the traversal order affects the shape of the tree that is built on the next execution of the program. Terminate the program.

  

  Sample Input

  (Some of the labels shown in the sample input are not typed in by the user, but are only printed for clarity. For this example, the "Criminal.mf" file is empty and all the potential suspects are added by command.)

  ADD       Name:             Quickdraw McGraw
            Attributes:       has a Texas accent
                              has a body guard
                              is computer literate
  
  ADD       Name:             Twingun Morgan
            Attributes:       has a New York accent
                              has red hair
                              smokes cigars
  
  ADD       Name:             Jackda Ripper
            Attributes:       has a body guard
                              bites his fingernails
                              carries a knife
                              is computer literate
  
  ADD       Name:             Annie Getcher Gunn
            Attributes:       has a New York accent
                              has red hair
                              eats Fritos
                              smokes cigars
  
  ADD       Name:             Slowdrawl Raul
            Attributes:       has a Texas accent
                              carries a knife
                              is computer literate
                              eats Fritos
  
  ADD       Name:             Sloan de Uptake
            Attributes:       has a body guard
                              has red hair
                              bites his fingernails
                              is computer literate
  
  INQUIRY            Code Name: Bang Bang
  TIP                Tip Info: has a New York accent
  CHECK              Quickdraw McGraw
  TIP                Tip Info: has red hair
  CHECK              Annie Getcher Gunn
  TIP                Tip Info: eats Fritos
  
  INQUIRY            Code Name: Holdup
  TIP                Tip Info: has a Texas accent
  CHECK              Slowdrawl Raul
  CHECK              Sloan de Uptake
  TIP                Tip Info: is computer literate
  
  INQUIRY            Code Name: Tough Stuff
  TIP                Tip Info: bites his fingernails
  PRINT
  CHECK              Twingun Morgan
  TIP                Tip Info: has a body guard
  CHECK              Slowdrawl Raul
  TIP                Tip Info: is computer literate
  QUIT
  

  

  Data Structures

  1. There is no upper bound to the number of suspects or number of attributes for a given suspect. You cannot use an array-based list to store the suspects or the attributes for a given suspect.

  2. The CHECK operation must be very efficient, because suspects are continually being pulled off the street for questioning and we must decide whether to let them go or ruthlessly interrogate them. Using a simple linked list to store the suspects is not sufficient. You must use a binary search tree. Suspects must be actually deleted from the structure when they are eliminated by TIP information. Because you destroy the list of suspects, as suspects are eliminated by TIP information, each inquiry should work on a copy of the original tree.

  3. TIP is executed much less often than CHECK and hence can be less efficient. It is acceptable if processing a TIP command requires searching the whole data structure of (active) suspects. Thus, a list of attributes can be stored with each suspect. You do not have to link all the suspects with the same attributes together. (This could potentially make for a much faster TIP operation.)

  

  Testing

  This program is complicated. You must create a test plan and use test drivers (as is done in the labs). You need to execute the program more than one time.

  

  Deliverables

  1. A design. You turn in an initial design on 7 April and you turn in a final design when you submit the project.

  2. Listing of the program's source code.

  3. Source code must be placed in the "project 1" folder on Nova.

  4. Hard copies of file "Criminal.mf" from each of the final test executions.

  5. Implemented test plan and test drivers. Include both code and copies of your test plan.

  6. A 1-2 page paper describing how your program works, what objects are included in it, and what each person did on the project. Explain what advanced features are in the application and where you used advanced techniques.

  This project must be done in a group of two people. In no circumstance may more than 2 people work in a group. There are two parts to the project. Part 1 is the basic program. This is the "C" level project. Part 2 has advanced features that you can add. Your grade will depend on how many features you add and how well they are implemented.

  

  PART 1

  Requirements:

  1. You must turn in a design based on some decomposition design method.

  2. You must use a dynamic implementations of all data structures.

  3. You must use the String class developed in class to store any strings that you use.

  4. You do not have to actually eliminate suspects from the binary search tree when they are eliminated via TIPs. Instead, you can just mark the suspect as not relevant (using some field in the suspect's record).

  5. You do not have to save information to the "Criminal.mf" file between executions, ie, you must build the tree each time you run the program.

  6. Every function must have correct pre and post conditions.

  

  PART 2

  You must implement everything in part 1. The features discussed here provide a mechanism for improving your grade. The exact grade you receive depends on the difficulty of your features as well as the effectiveness and correctness of your implementation.

  1. All programs beyond the "C" level must actually delete suspects from the structure when they are eliminated by TIP information.

  2. All programs beyond the "C" level must save criminal information that is stored in the tree into the file "Criminal.mf".

  3. All programs beyond the "C" level must save a file of transactions.

  4. All programs beyond the "C" level must automatically save a file when the user uses the QUIT command.

  5. Link suspects with the same attributes together to speed searching.

  

  Grading

  Regardless of which parts you complete, your project will be graded based on its design and how well implemented it is. I will examine comments and programming style. A poorly designed and commented program, even with advanced features, will receive a poor grade.

  Your grade will be determined by the following criteria:

  1. Did you meet the minimum criteria for your level?

  2. How well commented is your code? How accurate are your pre/post conditions? How well formated is your program? Is your program easy to read?

  3. How complete is your test plan? Does it cover all of the code or input classes? Does your program pass all of the tests?

  4. How elegant is your user interface? Is it easy to use?

  5. How elegant is your design? Do you decompose the problem logically? Do you have redundant code? Does your class structure make sense?

  6. How well does your program run. Are there errors or inconsistencies?

  

  Hints

  1. Start your design by using top-down decomposition as we talked about in class. Determine what different parts there are in the problem. Then decompose these into smaller parts, etc.

  2. Implement and test your ADTs first. Create a test plan for your ADTs and driver code. Once you know that your ADTs work, then start on the rest of your project.
  

  Return to Student Pages

  Return to John Barr's Home Page

  Last Modified: 10 March 2000
  

  THIS PAGE MAINTAINED BY:
  John Barr, Ithaca College