Class Notes: Data Structures and Algorithms

Summer-C 1999 - M WRF 2nd Period CSE/E119

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Project 4 Assignment

Project 4 consists of writing a Java application that performs insertion, deletion, and BFS/DFS graph traversal on binary search trees (BSTs) and AVL search trees.

Updates in response to student questions are in red typeface.

• Goal. The purpose of this project is to provide intermediate hands-on experience with Java programming for tree maintenance and traversal.

  The program you develop as Project 4 will (a) read a sequence of integers from stdin as in Project 1, (b) store the sequence in an array or linked list, (c) insert the input sequence into a BST or AVL search tree as specified by an input switch, (d) draw a diagram of the tree, (e) perform DFS or BFS traversal of the tree, (f) output the sequence of vertices visited, (g) perform user-directed deletion of a value from the tree (with appropriate rotation or rebalancing), then (h) draw a diagram of the modified tree to the screen. An example of input and output is shown below.

  When the TAs test the program, the numbers will be read in from a text file (denoted by inFile), and the command line will be as follows:

  java Proj4 dswitch aswitch < inFile

  where dswitch is one of the following switches: -a for AVL search tree or -b for BST; and aswitch is one of the following switches: -b for BFS or -d for dfs. Note that inFile, a text file that you enter using a word processor will be stored on disk. Your program will read the input sequence by command-line piping of that file to stdin.

  More information about the test procedure is posted below under Example Test Procedure.

• Features. We will be making a modular program with object-oriented design and implementation, as well as resuable Java code, as follows.

• Functionality. The program implemented as a Java Class called Proj4 (must be capitalized) that will perform the following steps:
  Step 1. Read input from stdin piped from a text file whose name is specified on the command line. The input file must be structured as a stream of positive or negative integers, one per line, followed by an "E" when the input sequence is completed. Following the "E" will be a line with the number to be deleted from the tree.

  Step 2. Depending on the dswitch flag, insert the input sequence into either a BST or AVL search tree, keeping the BST or AVL search tree properties maintained after each insertion.

  Step 3. Write the following header to the screen:

           your-name      your-SSN
           23 July 1999   COP3530-C99-Proj4
  

  Then, write the input sequence to the screen, ten integers per line, using the code you developed for Projects 2 and 3:

    4 2 9 3 5 6 7 8 10 11 1 12 14 13 

  The screen will display the following information after the header, and separated from the header by two blank lines:

  Data Structure:      (whatever one dswitch specifies)
  Traversal Algorithm: (whatever one aswitch specifies)
  
  Numbers Read In: 14
  
  Input Sequence:
       4   2   9   3   5   6   7   8   10  11 
       1  12  14  13 
  

  Step 4. Print the BST or AVL search tree to the screen. For example, the following partial BST could be constructed from the preceding input:

  Binary Search Tree
  
                  7              [partial tree given as example
                 / \              only - you must draw the full
                4   12            tree]
               / \  / \
              3   5 11 14
  

  Hint: Tree display can be fairly simple, if you partition the tree into levels. You can do this in one of two ways. For example, you could make the array representation of the tree, as we did in class and in the homework. The first value is the root, the next two values are the children of the root, and so forth. Alternatively, you could perform BFS on the tree, to partition it into levels.

  After you have the levels, you need to figure out the spacing and the way to arrange the "\" and "/" symbols to form the tree branches. There are tree printing codes on the Internet, which you can find through a search engine such as Lycos or Netscape. Look for keywords such as library and tree and pretty-print. Feel free to share the routines you find with others in the class. An example algorithm would proceed this way:

  Step T1. Partition the tree into L levels, using BFS.

  Step T2. The bottom level has 2^L-1 objects. In this assignment, the objects are three-digit integers. So, if you have K objects (a power of two), then you can allot M spaces between each object on the bottom level, and that gives you 3K + M(K-1) spaces total.

  Step T3. Work your way up the tree, figuring out where each parent goes (between each of its two children), as shown in the diagram below:

                       xxx
                       / \
           xxx                     xxx
           / \                     / \
     xxx         xxx         xxx         xxx
     / \         / \         / \         / \
  xxx   xxx   xxx   xxx   xxx   xxx   xxx   xxx
  

  To output the nodes on the screen, you can traverse each level of the tree horizontally. Hint: Using an array representation for the tree is particularly handy.

  Step 5. After you have displayed the tree, then perform BFS or DFS traversal of the tree, outputting the vertices visited in that order, using the widget with which you displayed the sequence. For example, for the partial tree shown above, and BFS, one could have:

  BFS output:  7  4 12  3  5 11 14 ...
  

  depending on whether or not repeated vertices were displayed.

  Step 6. After you have displayed the tree, then delete from the tree the number specified at the end of the input file. Do not use a prompt as originally specified, because many students are having problems with "stdin" conflicts.

  You need to have three response alternatives (For example, these could be error messages): The number has been found and deleted from the tree or The number you specified is not in the tree, try again, or you have entered an incorrect symbol (must be 0-9 or E), try again.

  Important Note: Be sure to rebalance the tree, if necessary, after each deletion to preserve the tree properties.

  Step 7. After you have completed each deletion, redisplay the modified tree and perform BFS or DFS to yield the tree display and list of vertices traversed, as shown in Steps 4 and 5.

  Step 8. After you have tested and completed your program, use the submission procedure outlined below to submit your project.

  Example Test Procedure. Type up a text file "inFile" in either Dos or Unix with one value per line, like this:

  22          [Input number 1]
  36          [Input number 2]
  54          [Input number 3]
  14          [Input number 4]
  17          [Input number 5]
  65          [Input number 6]
  E           [Specifies end of input sequence]
  14          [Number to be deleted from tree]
  

  Now run your program this way:

  java Proj4 dswitch aswitch < inFile

  where dswitch and aswitch were described previously.

  For the dswitch -a, the Data Structure line should read AVL Search Tree, and for -b, the Data Structure line should read Binary Search Tree. The legend to put on the Traversal Algorithm line for aswitch = -b is Breadth-First Search or for aswitch = -d is Depth-First Search.

  Required Programming Procedure. Define each class in a separate .java file, with your master file as Proj4.java, where Proj4, which has a main method, is the class name that the TAs will use to run your program. (It is o.k. to have a main method in each class - the TAs are primarily interested in the main method in the Proj3 class.)

  Other Hints on Programming Procedure. Use the following steps to guide your implementation of the Java version of the preceding program.

  Hint 1. Get started early!!! Don't wait until the last two or three days, especially if you have not had much Java programming experience.

  Hint 2. Decide what classes you will use. It is strongly suggested that you adapt Dr. Sahni's classes as shown in the text, to avoid undue programming effort. You can get code from Dr. Sahni's Web page at http://www.cise.ufl.edu/~sahni/dsaaj/, but you must not copy the code verbatim, instead adapting it for your use. After you have figured out what classes and objects to use, design your Java class specification(s) on paper. Then (and only then) should you start coding.

  Hint 3. Code your class(es) and methods, testing them incrementally (i.e., one at a time). Get each one working before you go on to the next one. If you write your program all in one blob of code, you will assuredly have difficulty debugging it.

  Hint 4. Try your program on different kinds of output (e.g., large and small inputs, with both negative and positive integers. If your code breaks, fix it until it works on all inputs. Use the pipe construct on the command line to get the input into your application.

  Hint 5. Use the streaming I/O reader developed for Project 3. If you developed another kind of reader for Project 3, you must modify it so it meets this specification. Deviations will be considered erroneous.

  Hint 6. The TAs are here to help you with your problems. We have scheduled office hours throughout the week, with the exception of the Independence Day Holiday. Please feel free to ask the TAs any questions about your Java program.

  Documentation. Illustrate your program with in-line comments, so the TAs know what you are doing. Consult your textbook and other Java programming references provided on the course Web page and elsewhere (e.g., Java books in library) for style guides.

• Evaluation. Maximum score = 100 points, as follows:

    For each of BFS and DFS on BST or AVL  search  tree:
      Code present and clear             1 points max.
      Code compiles correctly            2 points max.
      Data read in correctly             1 points max.
      Cmd-line switches work correctly   1 points max.
      Tree built correctly               5 points max.
      Tree traversed correctly           5 points max.
      Tree displayed correctly           5 points max.
      Deletions performed correctly      5 points max.
    TOTAL POINTS PER DataStructure/TraversalMethod:    25 points max.
    ----------------------------------------------------------------
    TOTAL POINTS (4 structure/method pairs)           100 points max.
  

  Note that we have "raised the bar" on this assignment. For example, if your code is present as specified, but doesn't compile and isn't documented, you would get 2 points structure-method pair for which the code is present (8 points max.) If the code is present, well documented, compiles, reads in data, and builds the tree correctly with correct tree display (but doesn't do anything else), then you could get as many as 60 points total.

• Submission Procedure. Please submit only your *.java files. You must be logged in to your CISE account to perform the submission procedure, which is described in detail at this link.

  In summary, type in the following commands within your directory to submit all the java files for Project 4:

  turnin -c cop3530 -p proj4 *.java {Return}

  where {Return} denotes the carriage return key.

  Important Note: In case you have developed your programs on any environment other than the CISE Unix system, please test your program on a CISE Unix machine before submission. We will only be testing programs for grading purposes on the CISE Unix machines. The excuse that you could not get into the CISE Lab will not be accepted, since you can remote log-in to all CISE and CIRCA labs 24 hours per day.

  Special Note from Lloyd Noronha:

  Before starting any programming project, please make sure that there are no unnecessary files in your "dev" directory. Make sure you only submit the files necessary for compiling and running your project. You will lose points for compilation errors in any file you submit, even if it is not relevant. We will compile and run your project as follows :

  javac *.java
  java Proj4 -a -i < inFile
  

  So please make sure that you test run your project as above in your directory just before your submission.

• Due Date. Submit the completed project by MIDNIGHT on Friday 23 July 1999. Projects submitted a day late will be penalized -10%; two days late: -20%, three days late: -30%, and four days late: -40% . Projects turned in more than four days late will not be accepted unless accompanied by a documented excuse (e.g., note from your physician or advisor).

This concludes the description of Project #4. Use the E-mail link at the top of this Web page to ask the TAs, if you have any questions about programming or grading.