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 whose internal implementation consists 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 low.
Q15. What are the advantages and disadvantages of this priority queue design? Consider how difficult it would be to develop and test the code, the efficiency of its operations, and how well it could handle a variety of inputs.
Your manager tasks you with implementing the queue. Now, you have to decide the threshold between a low priority element, a medium priority element, and a high priority element. Assume that the minimum priority is 0 and the maximum priority is 10.
Recall that in the PQArray and the PQHeap we used the double data type to denote priority. Compared to an int, a double can be great for added precision – we can distinguish between a priority of 2.5 and 2.2, for instance – but there are some instances where that added granularity can lead to less ideal priority assignments.
Q16. Should the thresholds be ints or doubles? Describe a real-world three-bin priority queue for which either ints or doubles would be preferable and explain why. How could your decision impact how your client uses the priority queue?
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 stored into the priority queue. 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 in admissions and convert admissions criteria to numbers different ways. Regardless of what specific factors are considered, should an admissions department use a purely numerical rankings based system? Why or why not? Include in your justification at least one additional factor and explain why it would or would not be difficult to include in an individual ranking based on numerical score.
Q18. Describe a real-world scenario not yet mentioned in which a priority queue does not work well because classification with a single number misses important context.
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 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 assigned when the patient's doctor first puts in the request. However, this initial priority ranking occurs before tissue typing, which evaluates compatibility between donor and recipient and therefore likelihood that the transplant will be successful. After considering the ethical and practical implications of statically assigning priority 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. How would you design an implementation for the hospital's priority queue that dynamically determines which patient is the best match whenever a new organ becomes available? Note: Your design does not have to be the fastest or most efficient.