CS 20, Summer 2009
Project 3

Files in ~cs20/p3/part1/ (at CSIL)

Heap.java-skeleton, CS20Heap.java, TestHeap.java, testheap.dat and corresponding output files for Max-Heap and Min-Heap (maxheap.out and minheap.out)

Files in ~cs20/p3/part2/

BST.java-skeleton, TestBST.java, testbst.dat and the corresponding output file (testbst.out)

Due: Tuesday, July 28, 9:00pm
Worth: 100 homework points

1. Implement (and test) a heap data structure as follows:
   1. Complete Heap.java to implement interface CS20Heap. The methods must behave exactly as documented by the interface.
      • Begin with ~cs20/p3/part1/Heap.java-skeleton and follow any instructions in that file. Use only the instance variables that are already declared. The constructors and toString() are already done - do not change them.
      • The heap must never become full. Increase the size of the array by the amount of INITIAL_CAPACITY if the insert method is called while the array is already filled.
      • Heap items must be String objects, and the heap must be able to operate as either a Min-Heap (minimum item on top) or a Max-Heap (maximum item on top), depending on the value of the parameter passed to the constructor. See javadocs.
        [Hint: our solution includes a utility method called tops that takes two String parameters - it returns true or false depending on the heap's ordering principle.]
      • None of the operations should throw any exceptions.
   2. Use ~cs20/p3/part1/TestHeap.java to test your heap implementation.
      • One command line argument may exist. If "max" is the first command line argument, a Max-Heap is used; otherwise a Min-Heap is used.
      • The program reads from System.in until the end of input or "quit" by itself on a line.
      • Six commands are legal (case does not matter).
        • Five commands require no parameters: size, clear, print, top, and removeTop.
        • The insert command requires a string parameter, but it may take multiple strings (to insert each one in order).
      • The program ignores comment lines (first non-blank character is '#') and blank lines.
      • When you are ready, input testheap.dat (by file redirection) to more completely test the implementation. If the program is run without "max" on the command line, these sample Min-Heap results should print; with "max" on the command line, these sample Max-Heap results should print.
2. Finish implementing (and test) a binary search tree as follows:
   1. Complete BST.java by finishing the private nested class of BST named Node. The class BST itself is already done, but it relies on the nested class methods to implement most operations. Of course the BST public interface hides these details.
      • Begin with the skeleton (~cs20/p3/part2/BST.java-skeleton), and follow the instructions there. All 9 Node methods shown are required.
      • Don't change any part of the outer class (BST), but read it carefully to learn what it expects from class Node.
      • Instance variables and a constructor for Node are already defined. You may not use any other instance variables in your solution.
      • You may solve these problems recursively or iteratively (but most people find the recursive solutions to be simpler).
      • Include a space character after each item in strings returned by the inOrder, preOrder and postOrder methods. Don't worry about an extra space at the end.
      • Specific requirement for the delete method - to be consistent with the results of our solution: When deleting an item with 2 children, replace it with the greatest item in the left subtree (instead of the least item in the right subtree).
   2. Use ~cs20/p3/part2/TestBST.java for testing your methods.
      • The program reads from System.in until the end of input or "quit" is entered by itself. It ignores comment lines (first non-blank character is '#') and blank lines.
      • Eight commands are legal (case does not matter).
        • Three commands require no parameters: count, clear, and height.
        • All others require a parameter: insert s (may be multiple), delete s, depth s, contains s, and print order, where s is a string, and order is one of pre, in, or post.
      • Redirect the contents of testbst.dat to fully test the implementation. These sample results should print.
3. Turn in both required files at once from your engineering account as follows:
   
   turnin p3@cs20 Heap.java BST.java
   Late projects may not be accepted.

Updated 7/14/09 by C. Michael Costanzo