The purpose of this assignment is to implement three types of queues, including a binary heap-based one, apply them to implement a heapsort array-sorting algorithm, and to compare the performance of those algorithms to the performance achievable with the sorting methods that are already available in Java.
2011 Assignment 2 1 EECS 2011: Assignment 2 Due: as set in eClass. May be done in groups of up to three students TL;DR: implement 3 types of queues, each in its class, 1 priority queue sorting method in a separate class. Submit 4 java classes. Cheating not allowed. Motivation The purpose of this assignment is to implement three types of queues, including a binary heap-based one, apply them to implement a heapsort array-sorting algorithm, and to compare the performance of those algorithms to the performance achievable with the sorting methods that are already available in Java. You are also encouraged to compare your priority queue performance to the one in the java.util package1. Introduction In this assignment you will implement a class that extends an AbstractQueue2 class, which in itself implements a Queue3 interface. Note that the names of the methods in that interface differ from the ones used for priority queues in the textbook. Also note that each of the queue methods exists in two version: a version returning a special value, and a version that throws an exception. Like with any queue implementation utilizing a binary heap data structure, the performance of insertions and removals when using the heap is going to be O(log n), while examining the value will be done in constant time. While there are other data structures that are more efficient in theory, real-world performance of binary heaps is often superior, especially when no additional functionality is required (e.g., changing the keys). In addition to the lecture notes, you might find the following resources useful: Priority Queues chapter of the Algorithms textbook https://algs4.cs.princeton.edu/24pq/ Implementation Here, you have to create three classes. Name them PQueueUnsortedArray, PQueueSortedArray, and PQueueHeap and put them in the default package. As the names suggest, the implementations should use an unsorted array, a sorted array, and an array representation of the binary heap, respectively. In addition, for the heap 1 https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html 2 https://docs.oracle.com/javase/8/docs/api/java/util/AbstractQueue.html 3 https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html https://algs4.cs.princeton.edu/24pq/ https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html https://docs.oracle.com/javase/8/docs/api/java/util/AbstractQueue.html https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html 2 implementation, you should not use the first position of the array, just like described in the link above. For all the implementations, the array should also grow automatically as needed (similar to how it’s implemented in ArrayList, for example; note how different growth strategies affect the performance). Automatic shrinking is not required. Part 1 For each class, implement the following public methods: 1. boolean offer(E e) 2. boolean add(E e) 3. E poll() 4. E remove() 5. E peek() 6. E element() 7. int size() 8. String toString() (described below) One public constructor should exist in your implementations: the one that takes no parameters and creates an empty queue when the class is instantiated. No other methods need to be implemented or overridden (e.g., the iterator() method is not required). The behaviour of the methods in your implementation should be equivalent to that of Java Standard Library’s classes (i.e., java.util.PriorityQueue; please refer to the class API online). The time complexity, of course, will vary. toString() should simply return a String with the contents of the array representing the corresponding queue, e.g., for the binary heap version: [null, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] The array looks sorted, as the items were inserted sequentially, from 1 to 12. When the same are inserted in the reverse order, the resulting array representing the heap will be: [null, 1, 3, 2, 6, 4, 7, 8, 12, 9, 10, 5, 11] The other versions of the queues will return different strings (e.g., no null elements in front, and the order is always either sorted, or the original insertion order). Of course, you are free to implement any private or protected methods and classes as you see fit. However, you should not have any public methods other than the ones mentioned (or the ones present in the interface or in the class’ superclass). Part 2 Name your class Sort and put it in the default package. Inside, create the following public method: static
void PQSort(Queue pq, E[] a) The method should implement a priority queue sorting algorithm (not-in-place kind), similar to how it was shown in class. The first parameter is one of the priority queue implementations from Part 1. Note that it will only work with priority queue instances. 3 NB: This method can literally be implemented in three lines. Test the method to ensure it works correctly (and produces the same result as, say, a call to Arrays.sort on the same array). The order is non-decreasing. Part 3 Nothing needs to be submitted for this part. Create some tester class and use it with your queue implementations to investigate the sorting methods running time complexity as the number of items you insert in the queue of each type increases. Try using values from 10 to 1,000,000 while measuring the running time. Confirm that the running time follows the expected logarithmic or linear behaviour for both add and remove methods. NOTES: 1. Do not use package-s in your project (put your classes in the default package). Using packages will cost you a 10 % deduction from the assignment mark. 2. Some aspects of your code will be marked automatically (e.g., how it handles boundary cases and error conditions), using a custom tester class. It is also imperative you test your classes. If any of the java files that you submit do not compile, the whole submission will be given a grade of zero, regardless of how trivial the compiler error is. The code you submit should compile using javac *.java command in either Windows, Linux, or MacOS. 3. Your code should include Javadoc comments. 4. Using any java.util implementations of Collection4 or Map5 is not allowed (importing the java.util.AbstractQueue class is of course fine). Submission Find all the java files in your project and submit them electronically via eClass (do not zip, tar, rar, or 7z them). Only 4 files are expected, but you may write other classes, if you deem them necessary. If working in a group, make only one submission per group and include a group.txt file containing the names and the student numbers of the group members. The deadline is firm. Contact your instructor in advance if you cannot meet the deadline explaining your circumstances. The extension may or may not be granted, at instructor’s discretion. 4 https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html 5 https://docs.oracle.com/javase/8/docs/api/java/util/Map.html 4 Grading The assignment will be graded using the Common Grading Scheme for Undergraduate Faculties6. We look at whether the code passes the unit tests, satisfies the requirements of this document, and whether it conforms to the code style rules. Academic Honesty Academic honesty will be strictly enforced in this course. Specifically, direct collaboration (e.g., sharing code or answers) is not permitted, and plagiarism detection software will be employed. You are, however, allowed to discuss the questions, ideas, or approaches you take. Cite all sources you use (online sources – including web sites, old solutions, books, etc.) in your code comments; using textbook examples is allowed, but these must be cited as well. E.g., 1) /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @exception IllegalArgumentException if the specified initial capacity * is negative * uses code from www.xxx.yyy.edu/123.html for initialization * */ 2) //formula based on Jane Smart’s thesis, page XX, available at https://... a = b + c; Although using outside sources is allowed – with proper citing, if the amount of non- original work is excessive, your grade may be reduced. You might find the following article useful to have an idea what kind of collaboration is appropriate: https://en.wikipedia.org/wiki/Clean_room_design You may not post the contents of this assignment, nor solicit solutions on any external resources. 6 https://secretariat-policies.info.yorku.ca/policies/common-grading-scheme-for-undergraduate-faculties/ https://en.wikipedia.org/wiki/Clean_room_design https://secretariat-policies.info.yorku.ca/policies/common-grading-scheme-for-undergraduate-faculties/