Assignment 5: Heaps & Priority Queues COMP 2140, Fall 2021 Due: Tuesday 7 December 2021 at 5:00 p.m Instructions ˆ You must complete the “Honesty Declaration” checklist on the course website before...

Assignment in Java I recommended Intel J


Assignment 5: Heaps & Priority Queues COMP 2140, Fall 2021 Due: Tuesday 7 December 2021 at 5:00 p.m Instructions ˆ You must complete the “Honesty Declaration” checklist on the course website before you can submit any assignment. ˆ Assignments must follow the programming standards document published on UM Learn. ˆ After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please see the course outline document published on UM Learn for the course policy for late submissions. ˆ If you make multiple submissions, only the most recent version (the last submission) will be marked. We strongly encourage you to submit early! ˆ These assignments are your chance to learn the material for the exams. Code your assignments inde- pendently. We use software to compare all submitted assignments to each other, and pursue academic dishonesty vigorously. ˆ You can get help from the T.A. during your lab section and from the instructors and from the course Assignment 5 discussion forum on UM Learn. You can discuss general topics related to the assignment with fellow students or other people, but you cannot discuss the solution to the assignment with them. You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a full discussion of our expectations for individual work on this assignment, see the Department of Computer Science’s expectations webpage. ˆ Your Java program must compile and run upon download, without requiring any modifica- tions. The marker will not fix your program’s problems. See also the “Hand in” instructions at the end of this assignment Part 1 (Programming): Waiting to See a Doctor at an ER Objective: To simulate patients in an Emergency Room (ER) waiting room. The application and the file you will complete: The file A05.java contains an incomplete application that simulates patients arriving at and leaving an ER. The application creates a priority queue to represent the waiting room of the ER for a hospital. Then it randomly generates some events: ˆ A new patient arrives at the ER. The triage nurse assigns the new patient the next available patient ID and an appropriate priority (based on the patient’s complaint and condition). The patient then waits in the waiting room. ˆ The highest-priority patient leaves the waiting room to see a doctor. ˆ A patient leaves the hospital without seeing a doctor. ˆ A patient’s condition changes, so the triage nurse changes the patient’s priority. 1 https://sci.umanitoba.ca/cs/expectations/ After all the randomly-generated events have been handled, the application prints out some statistics. Representing a patient and the waiting room: A patient is represented by a Patient object, which contains a patient ID and a priority (both ints). You can get the ID or the priority, and you can change a priority. The waiting room is represented by a TriagePriorityQueue, which is implemented as a max heap with all the usual methods, plus some non-standard methods. The heap array in this implementation is an array of Patient objects. The TriagePriorityQueue methods you will write: You will write the bodies of two non-standard methods in TriagePriorityQueue to complete the application. Do not change anything else in the file. ˆ Method isHeapOrdered needs to return true if the calling TriagePriorityQueue array is in heap order and false if it isn’t. It has to check that every parent is in heap order with respect to its children (or child, if it only has one). ˆ Method changePriority is passed the ID number of a patient in the waiting room and a new priority for that patient. This method has two parts: a non-standard part (finding the patient with the given ID in the heap in a linear search and changing that patient’s priority to the new priority) and a standard part (restoring heap order). Hint: Use already-written helper methods to find the patient and to restore heap order — you just have to figure out when and how to call them. In both these method bodies, if there is already a TriagePriorityQueue method to do something you need to do, then you should use the existing method. So look at the existing methods and do not duplicate code! Hand In: To submit the programming part of the assignment, upload the specified file to the Assignment 5 folder on the course website. Verify that the submission worked. (See the detailed hand-in instructions in the “COMP2140-HandIn-Instructions” document under “General Information” in the content browser of the course website on UM Learn.) ˆ Submit ONE .java file, which must be named A5.java (e.g., A5CameronHelen.java). ˆ Do not submit .class or .java~ files (or compressed files or directories)! ˆ The marker will not edit your file in any way, so make sure it will compile and run for the marker. ˆ Make sure your file does not specify a package at the top! Part 2 (Written): Operations on Leaf-based 2-3 Trees & Heaps Objective: To practice basic operations on leaf-based 2-3 Trees and Heaps. Leaf-based 2-3 Trees: For each of the following trees, using the insertion algorithm for leaf-based 2-3 tree described in the pre-recorded lectures, insert 2, then insert 15, then insert 25, then insert 35 (in that order). It suffices to draw the final tree for each case. 7, 26 4 3 6 14, 20 10 16 24 29 27 31 Tree A 76 53 44 39 48 61 58 72 91 84 79 88 97 95 99 Tree B 2 4, 8 2 1 3 6 5 7 10 9 14 Tree C 8Tree D Heaps: 1. Draw the heap tree represented by the following heap structure: heap 44 17 39 16 10 37 12 8 11 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 10heapSize 2. Insert 55, 19, 36, and 62 (in that order) into the above heap. Draw the heap tree and the heap array after all insertions are completed. 3. Consider a heap stored in an array heap = [20, 12, 18, 9, 3, 16, 17, 2]. What does the array contain after we apply two deleteMax operations? Write down the array content after the first and after the second deleteMax operations. 4. Indicate whether the following statement is correct or not. Provide a brief justification for your answer. You should either use an example (with large n) to show the statement is not correct or use English words to prove the statement: “The deleteMax() operation in a heap of size n, where n is a large number, can take O(1) in the best case.” Hand In: You can write/draw your answers on paper OR use a computer program to typeset your answers. In any case, you should convert your answers (for all written questions) into a single .pdf file (which must be named A5.pdf (e.g., A5CameronHelen.pdf)) and upload the file to the Assignment 5 folder on the course website. 3