Design analysis
You're working as a software engineer and have been contracted to build a priority queue for a client. The client's specification requests that the design support exactly three levels of priority: "high," "medium," and "low." Elements enqueued at the same priority level are to be processed in FIFO (first-in-first-out) order. Your manager proposes a design for a new PQueue class that has an internal implementation consisting of three ordinary Queues: one for high priority elements, one for medium priority elements, and one for low priority elements. To dequeue elements, it would first drain the high priority queue, then medium, and then low.
Q15. Consider the differences between this three-bin priority queue and the priority queue you implemented on your assignment. Which would be more efficient to insert elements into and why? More generally, what are the benefits and disadvantages of using the three-bin priority queue vs. a regular priority queue?
Your manager tasks you with implementing the proposed priority queue. Now, you have to decide the threshold between a low priority element, a medium priority element, and a high priority element.
Q16. Describe a real-world system where a three-bin priority queue could be used. What factors would you use to distinguish between a low vs. medium vs. high priority element? What limitations might you need to consider when using a three-bin priority queue to represent this system?
Validity of rank-based systems
Say a college admissions department used a priority queue to rank their applicants. The admissions team decides on an algorithm to assign each applicant a weighted score, claiming that it takes into account the applicant's GPA, course load, extracurriculars, and personal statements. Each applicant's score would be a double, and a higher score would make them higher priority in the queue (more likely to be admitted). Once the admissions team builds up the priority queue, they take the top 500 applicants (based on their weighted score) and admit them.
Q17. Different admissions departments consider different factors and convert admissions criteria to numbers in different ways. Regardless of what specific factors are considered, should an admissions department use a purely numerical ranking system for applicants? Why or why not?
If yes, discuss what factors you think would be best to include when calculating numerical rankings and why those factors are well-represented as numbers. If not, discuss what factors you think should be considered in college admissions that would be difficult to represent as a numerical score. There are no right or wrong answers here – we're genuinely interested in your thoughts!
Q18. Describe a real-world system that requires ranking but in which classification with a single number misses important context (i.e. a priority queue might not be the best way to store the objects being ranked). Make sure to use an example that hasn't already been discussed in lecture or in this assignment.
Dynamic vs. static priority
Our PQArray and PQHeap implementations were both designed to assign a static priority to a given element. By static, we mean that once a priority is assigned, it does not change. There can be situations where an element's initially assigned priority does not take into account the full spectrum of considerations when deciding which element should be dequeued first.
The United Network for Organ Sharing (UNOS) specifies that organ donation matching considers waiting time, distance from donor hospital, pediatric status, survival benefit, and several other factors. Say a hospital uses a priority queue to determine which patients get matched with which organs. The priority is determined from the UNOS factors and is assigned when the patient's doctor first puts in the request for an organ. However, this initial priority ranking occurs before the doctor evaluates compatibility of tissue between the donor and the recipient. Tissue compatibility increases the likelihood that the transplant will be successful. After considering the ethical and practical implications of statically assigning priorities to patients, you suggest that the hospital redesigns their priority queue to consider each patient's priority as a dynamic value. By dynamic, we mean that a patient's priority can change from its original assigned value.
Q19. Consider the PQueue class you just implemented. What would you change about the public interface to allow the hospital to dynamically update priorities in order to determine which patient is the best match for an organ? For any methods that you add, briefly describe when they would be used by the client and how they might be implemented privately. Note: Your design does not have to be the fastest or most efficient.