CSCE 221 Programming Assignment #3 Solution

Any assignment turned in without a fully completed coverpage will receive ZERO POINTS.
Please list all below all sources (people, books, webpages, etc) consulted regarding this assignment:

CSCE 221 Students Other People Printed Material Web Material (URL) Other
1. 1. 1. 1. 1.
2. 2. 2. 2. 2.
3. 3. 3. 3. 3.
4. 4. 4. 4. 4.
5. 5. 5. 5. 5.


I certify that I have listed above all the sources that I consulted regarding this assignment, and that I have not received nor given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment.



Printed Name (in lieu of a signature):
Priority Queues and Heaps

Description:

We will test your implementations using a set of numbers in a text file named “numbers.txt”.
• Each line of the file will contain a number.
• The first number will be which Priority Queue to use (0=UnsortedPQ, 1=SortedPQ, 2=HeapPQ).
• The second number will be the number of remaining elements in the file, n.
• The first two numbers of the file (queue type and n) will NOT be inserted into your Priority Queue. However, the remaining n numbers will be inserted.
• You should then remove all n numbers and print them to the screen.
• An example numbers.txt file is provided to you.


Coding Portion (50 Points):
• Start with the template: PriorityQueue.h provided with this assignment, and create three versions of the Priority Queue (using templates for the type of object) filling in all of the member functions.
• Be sure to test the correctness of your algorithms and implementations (we will).
• Your code will be graded based on whether or not it compiles, runs, produces the expected output, produces correct output, whether or not your experimental setup is correct, and your coding style (does the code follow proper indentation/style and comments).
• You should only use STL functions for data structures and algorithms you have already implemented. Vectors, Deques, Lists are all okay. The STL heap functions are not.

Report (50 Points):
You will write a brief report that includes theoretical analysis, a description of your experiments, and discussion of your results. At a minimum, your report should include the following sections:
1. Introduction. In this section, you should describe the objective of this assignment.
2. Theoretical Analysis. In this section, you should provide an analysis of the complexity of an insert operation and the complexity of the sort (inserting all of the items and then removing all of the items). Describe the advantages and disadvantages of the three strategies. What is the complexity of an insert (on average) for the different implementations? What is the complexity of the sort (on average) for the different implementations?
3. Experimental Setup. In this section, you should provide a description of your experimental setup, which includes but is not limited to
a. Machine specification
b. How did you generate the test inputs? What input sizes did you test? Why? What data structures did you use for your List implementation of the Priority Queue?
c. How many times did you repeat each experiment? Some thoughts on how you chose the repetition will be helpful.
4. Experimental Results. In this section, you should compare the performance (running time) of the insert() operation and the sort on the three different implementations to one another and to their theoretical complexity.
a. Make a plot showing the running time (y-axis) vs. the number of insert operations (xaxis). You must use some electronic tool (matlab, gnuplot, excel, …) to create the plot – hand-written plots will NOT be accepted.
b. Make a plot showing the running time (y-axis) vs. the number of items inserted and removed (x-axis). You must use some electronic tool (matlab, gnuplot, excel, …) to create the plot – hand-written plots will NOT be accepted.
c. Provide a discussion of your results, which includes but is not limited to:
i. Which of the three Priority Queue implementations performs the best? Does it depend on the input?
ii. To what extent does the theoretical analysis agree with the experimental results? Attempt to understand and explain any discrepancies you note.

BONUS (10 Points):
● Implement a bottom up construction for the heap using the algorithm discussed in class or in academic literature. Compare the time the bottom up construction takes versus inserting n items into the heap in your experimental section.