====================================================
LANGUAGE: JAVA
====================================================
In this programming part, you will implement a standard Priority Queue interface using four basic strategies and then evaluate and compare their operational performance. Storing a collection of prioritized elements, a Priority Queue is an ADT characterized as follows: In general, the elements are ordered pairs' (k,v) with key k prioritizing value v in the priority queue. It can store elements of any type, as long as the keys satisfy a total ordering relationship. (See text book, page 363) It supports arbitrary insertions of elements. It allows the removal of the element that has highest priority. In this assignment : an element with the smallest key has the highest priority. if multiple elements have the same priority, then the removal process may arbitrary remove any of those elements. It supports the following MyPQ
interface (Page 361): insert(k, v): Creates an entry (element) with key k and value v in the priority queue. min(): Returns (but does not remove) a priority queue entry (k,v) having minimal key; returns null if the priority queue is empty. removeMin(): Removes and returns an entry (k,v) having minimal key from the priority queue; returns null if the priority queue is empty. size(): Returns the number of entries in the priority queue. isEmpty(): Returns a boolean indicating whether the priority queue is empty. Programming Requirements: 1. Implement the MyPQ interface above four ways: array-based and linked list-based, each sorted and unsorted. Specifically, implement the following four classes. a) Array-Based i. MyPQUnsortedArray 1. Uses an array to store the elements, with array's initial capacity = 1. 2. During a call to insert(k, v), immediately knows where to insert an element in the array, 3. During a call to removeMin() or min(), searches the array for the element with the smallest key. 4. Before inserting an element during a call to insert(k, v), the array capacity is doubled if it is full 5. After removing the smallest element during a call to removeMin(), the array capacity is halved if its size is less than 25% of the capacity. ii. MyPQSortedArray 1. Uses an array to store the elements, with array's initial capacity = 1. 2. During a call to insert(k, v), search among the sorted elements in the array for an appropriate position to insert the element there. 3. During a call to removeMin() or min(), immediately knows where the element with the smallest key is located. 4. Before inserting an element during a call to insert(k, v), the array capacity is doubled ) if it is full 5. After removing the smallest element during a call to removeMin(), the array capacity is halved if its size is less than 25% of the capacity. b) Linked List-Based i. MyPQUnsorted List 1. Uses a doubly linked list to store the elements, 2. During a call to insert(k, v), immediately knows where to insert an element in the array, 3. During a call to removeMin() or min( ), searches the array for the element with the smallest key. ii. MyPQSorted List 1. Uses a doubly linked list to store the elements, 2. During a call to insert(k, v), search among the sorted elements in the list for an appropriate position to insert the element there. 3. During a call to removeMin() or min(), immediately knows where the element with the smallest key is located. 2. Your implementations above may not use the Java Collections class and the java collection framework; that is, you are expected to roll out you own code! It seems like a lot, but as you can see it repeats the same theme four times. Please note that your array-based and linked list-based classes do not need to be as expansive as Java's ArrayList or LinkedList classes beyond what is the bare minimum to support the MyPQ interface. 3. Write a program named PQTester to test drive your classes as follows: a) For each N in {10, 100, 1000, 10000, 100000, 1000000} i. Using the input files posted with this assignment, prepare an input file: 1. If N is in the range [1, 10000] use elements_test_filel, which has 10000 lines of strings. 2. If N is in the range (10000, 100000], then use elements_test_file2, which has 100000 lines of strings. 3. If N is in the range [100000, 1000000], then use elements_test_file3, which has 1000000 lines of strings. ii. Starting with four empty priority queue objects, one of each of your classes above, measure how long it takes to insert n elements of type into each queue, where the Integer keys are random integers in the range [1,N), and the String values come from the input file prepared above. iii. Using the priority queues created in part a, measure how long it takes to remove all of the N elements. iv. Create and fill a table of values that looks as follows (the (ms) timing values below are just an illustration and do not relate to any real measurements): RemoveMin (k, v) (ms) N = 10 Insert (k,v) (ms) 35 15 MyPQUnsortedArray 11 45 MyPQUnsortedList 71 15 MyPQSortedArray 86 48 MyPQSortedList v. Save the table to a file named pqtestrun.txt. vi. Make sure you reset the timer (or save the intermediate time before the next measurement). In other words, make sure that your measured time contains only the time to perform one set of operations (insert or remove) that was supposed to be timed 4. In case the operations for big N numbers take too long (e.g., more than 50s) you may reduce the number to a smaller one or eliminate it (so that you will have a range from, say, 1 to 100000) 5. As always, it is imperative that you test your classes, making sure that your program can handle boundary cases (e.g., calling min() or minRemove() on an empty queue) and other error conditions. In this programming part, you will implement a standard Priority Queue interface using four basic strategies and then evaluate and compare their operational performance. Storing a collection of prioritized elements, a Priority Queue is an ADT characterized as follows: In general, the elements are ordered pairs' (k,v) with key k prioritizing value v in the priority queue. It can store elements of any type, as long as the keys satisfy a total ordering relationship. (See text book, page 363) It supports arbitrary insertions of elements. It allows the removal of the element that has highest priority. In this assignment : an element with the smallest key has the highest priority. if multiple elements have the same priority, then the removal process may arbitrary remove any of those elements. It supports the following MyPQ interface (Page 361): insert(k, v): Creates an entry (element) with key k and value v in the priority queue. min(): Returns (but does not remove) a priority queue entry (k,v) having minimal key; returns null if the priority queue is empty. removeMin(): Removes and returns an entry (k,v) having minimal key from the priority queue; returns null if the priority queue is empty. size(): Returns the number of entries in the priority queue. isEmpty(): Returns a boolean indicating whether the priority queue is empty. Programming Requirements: 1. Implement the MyPQ interface above four ways: array-based and linked list-based, each sorted and unsorted. Specifically, implement the following four classes. a) Array-Based i. MyPQUnsortedArray 1. Uses an array to store the elements, with array's initial capacity = 1. 2. During a call to insert(k, v), immediately knows where to insert an element in the array, 3. During a call to removeMin() or min(), searches the array for the element with the smallest key. 4. Before inserting an element during a call to insert(k, v), the array capacity is doubled if it is full 5. After removing the smallest element during a call to removeMin(), the array capacity is halved if its size is less than 25% of the capacity. ii. MyPQSortedArray 1. Uses an array to store the elements, with array's initial capacity = 1. 2. During a call to insert(k, v), search among the sorted elements in the array for an appropriate position to insert the element there. 3. During a call to removeMin() or min(), immediately knows where the element with the smallest key is located. 4. Before inserting an element during a call to insert(k, v), the array capacity is doubled ) if it is full 5. After removing the smallest element during a call to removeMin(), the array capacity is halved if its size is less than 25% of the capacity. b) Linked List-Based i. MyPQUnsorted List 1. Uses a doubly linked list to store the elements, 2. During a call to insert(k, v), immediately knows where to insert an element in the array, 3. During a call to removeMin() or min( ), searches the array for the element with the smallest key. ii. MyPQSorted List 1. Uses a doubly linked list to store the elements, 2. During a call to insert(k, v), search among the sorted elements in the list for an appropriate position to insert the element there. 3. During a call to removeMin() or min(), immediately knows where the element with the smallest key is located. 2. Your implementations above may not use the Java Collections class and the java collection framework; that is, you are expected to roll out you own code! It seems like a lot, but as you can see it repeats the same theme four times. Please note that your array-based and linked list-based classes do not need to be as expansive as Java's ArrayList or LinkedList classes beyond what is the bare minimum to support the MyPQ interface. 3. Write a program named PQTester to test drive your classes as follows: a) For each N in {10, 100, 1000, 10000, 100000, 1000000} i. Using the input files posted with this assignment, prepare an input file: 1. If N is in the range [1, 10000] use elements_test_filel, which has 10000 lines of strings. 2. If N is in the range (10000, 100000], then use elements_test_file2, which has 100000 lines of strings. 3. If N is in the range [100000, 1000000], then use elements_test_file3, which has 1000000 lines of strings. ii. Starting with four empty priority queue objects, one of each of your classes above, measure how long it takes to insert n elements of type into each queue, where the Integer keys are random integers in the range [1,N), and the String values come from the input file prepared above. iii. Using the priority queues created in part a, measure how long it takes to remove all of the N elements. iv. Create and fill a table of values that looks as follows (the (ms) timing values below are just an illustration and do not relate to any real measurements): RemoveMin (k, v) (ms) N = 10 Insert (k,v) (ms) 35 15 MyPQUnsortedArray 11 45 MyPQUnsortedList 71 15 MyPQSortedArray 86 48 MyPQSortedList v. Save the table to a file named pqtestrun.txt. vi. Make sure you reset the timer (or save the intermediate time before the next measurement). In other words, make sure that your measured time contains only the time to perform one set of operations (insert or remove) that was supposed to be timed 4. In case the operations for big N numbers take too long (e.g., more than 50s) you may reduce the number to a smaller one or eliminate it (so that you will have a range from, say, 1 to 100000) 5. As always, it is imperative that you test your classes, making sure that your program can handle boundary cases (e.g., calling min() or minRemove() on an empty queue) and other error conditions
