CS 206 - Introduction to Data Structures

Assignment 9: Due 11:59PM Thursday April 16, 11:59pm

Part 1 -- Remove method for Priority Queues

Watch the video on Moodle, "Heaps -- Removal" and get my code for Heaps and for the Priority Queue Interface. (This code is also available /home/gtowell/Public206/a9/) Write code to implement the remove function that is specified in the interface but is not implemented in the code. For reference, here is the definition from the interface
	* Remove an item from the priority queue.  The item to be removed may be anywhere within 
	* the priority queue. If the item is not in the priority queue, then return false; otherwise the 
	* removal must succeed and the function will return true.
	* @param toBeRemoved the item to be removed from the priority queue.
	* @return true if the item was removed, false otherwise.
        boolean remove(V toBeRemoved);

Part 2 -- Testing code

Write code, similar to that of Homework 7, part 2, that tests all of the functions of the heap based priority queue. You should test all public methods, not merely the one you wrote. You should test all condintions for all methods. Your tests should be print documenting. That is, I should not have to read your code to understand what the test is testing and whether or not the test passed.

As a part of your testing code, you will almost certainly need to write code that prints the contents of the heap as a binary tree. You can dust off, and update appropriately, code you wrote for part 1 of homework 7.

As in Homework 7, the goal here is for you to think about all of the ways in which the heap based priority queue might fail. Then think of ways to test whether or not it fails. (If you find failures, you should fix them. I believe that my code is correct, but if your tests find errors, you should fix those too.)

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items: DO NOT INCLUDE:
Data files that are read from the class site.

The following steps for submission assume you are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/

  1. For this assignment N=9
  2. Put the README file into the project directory and your maze (/home/YOU/cs206/AssignmentN)
  3. Go to the directory /home/YOU/cs206
  4. Enter submit -c 206 -p N -d AssignmentN

For more on using the submit script click here