|CSE Home||CSE 326 Home||CSE 326 Projects||About Us||Search||Contact Info|
The project overview is best described in the preliminary writeup.
Part A is to implement and test various varieties of Priority Queues. Since most of the code is in the book, the focus is more on how to test your code and understanding its asymtotic complexity. In part B you will incorporate your code into the Networked Maze code described in the preliminary writeup.
Rather than specifying a due date for part A, I am going to stick to a single due date (to be determined, but the week after the midterm ) for the entire project. However, in order to be sure you are on track, there will be a 'checkpoint' for part A on Wednesday, July 11th. You must turnin a version of your code by 10pm on the day of the checkpoint. However, that version does not need to be entirely complete.
The assignment description below describes what must be turned in with part B by the project due date. For the checkpoint, any pieces of the part A assignment which are not completed must be documented in your README. In addition, you must indicate the following:
So in summary - you will have to do all that is listed below at some point, but it is not all due on Monday. I would strongly recommend you getting as much done for Monday as possible.
Every group is required to write two heap data structures to implement the Priority Queue ADT. One must be array-based (either a Binary Heap or a d-Heap) and the other pointer-based (either a Leftist Heap or a Skew Heap).
There will be no code distributed for this part of the assignment. Instead, you must develop your own from this specification.
You must write the abstract base class PriorityQueue which has the following methods (assuming data type D and key type K):
Your README file should list the data structures you chose to implement, and for each data structure, for each method, you should indicate the asymtotic running time of your code. You should strive to make that running time as low as possible, but dont get stuck on this, you will have time to improve it later.
Like last time, every groupís code must compile using make, and your entire class hierarchy must be templated.
In addition to the PriorityQueue, you should design and build a (simple) program to test your queue, demonstrating that queue behaves correctly in a variety of situations. Some example situations include: deleteMin on an empty queue; insert into an array-based queue when the array is full; deleteMin returns a sorted list; etc. You should develop a list of such cases, and write code to test them. Feel free to work together (beyond the confines of your group) to come up with cases, but just the group members should write the code.
I am not going to say you must have so many or it suffices to have so many - the point is for you to give us the program tools to demonstrate that your code behaves as it should. You should give us all that is needed to demonstrate that.
Your README file should list the cases you cover, and how to run your testing harness to demonstrate each case.
You may work on a team of at most two on this assignment. The teams for part A will be the same as those for part B. You may choose how to divide the work under three conditions:
If you end up working alone, your responsibilities are the same.
Your README file should document your submission (though it does not by any means replace comments in the code!). It should contain the following:
Department of Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to owner-cse326]