Priority Queue

Wednesday, July 31

Due Wednesday, July 31 at 11:59 PM

  • Submit to Paperless. Deadline is 11:59 PM.
  • The late day policy gives you the ability to self-grant an extension (as long as you have not used all your late days); we trust you will make reasonable and sparing use of this power. Be sure to reserve late days for emergencies.
  • Reminder: You have a limited pool of late days. You have a total of 4 late days to use throughout the quarter, but you cannot use more than 2 late days per assignment. Late days are expended in 24-hour blocks. See the Assignments page for more details.

After spending the first half of CS106B learning how to use our provided data structures to accomplish nifty and powerful tasks, you're now ready to step up to implementing your own data structure!

You will implement the Priority Queue class, a variant on the standard queue that processes elements in order of relative priority. You will explore two different approaches for the class implementation: the first using a sorted array and the second using the fancy and efficient binary heap. You will also analyze and write client code that uses your new data type, and you will reflect on the tradeoffs in the two implementations as well as other alternatives. Neat stuff!

This assignment is to be completed individually. Working in pairs/groups is not permitted.

Learning goals

  • Students will be able to implement a class according to a provided interface definition.
  • Students will understand how code is written in the role of implementer and how that differs from code written in the role of client.
  • Students will gain practice with pointers, dynamic arrays, and explicit management of memory using new and delete.
  • Students will develop an appreciation for the need to be vigilant when working with memory and pointers.
  • Students will be able to identify tradeoffs in implementation options and to reason about how these choices impact the flexibility and efficiency of the data structure.

Assignment parts

This assignment consists of a warmup debugging exercise, three programming tasks, and reflection questions.

  • Warmup

    Practice with debugging on objects and arrays/memory.

  • PQArray

    Complete the implementation of a Priority Queue class that stores elements in an array.

  • PQueue Client and Data Science Demos

    Solve data processing tasks as a client of the Priority Queue class and play with cool demos that we've provided to see the utility of your new class in analyzing real-world data.

  • PQHeap

    Implement a Priority Queue class that stores elements in a binary heap.

  • Ethics of Prioritization and Ranking

    Reflect on ethical concerns around use of priority queues in the real world.

Please note that the three programming tasks are not equal when it comes to the amount of work being asked of you. Whereas the PQArray and PQ Client tasks ask you to to complete one function each; the PQHeap task requires you to design and implement the entire class, which consists of 8-10 functions. Please have this in mind when designing your plan of attack!

Getting started

📦 Starter project

The starter project is provided as a zip archive. Download the zip, extract the files, and move the project folder to your CS106B folder. Open the .pro file in Qt Creator to get started.

Resources

Here are resources that will be helpful for this assignment:

Getting help

Working very closely with raw memory and implementing your own classes can get tricky! We recommend drawing lots of diagrams and making maximal use of the debugger.

If you have questions for us, the Ed forum is open 24/7 for general discussion. Always start by searching first to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the LaIR helper hours or office hours.

Submit

Before you call it done, run through our submit checklist to be sure all your ts are crossed and is dotted. Then upload your completed files to Paperless for grading.

Please submit only the files you edited; for this assignment, these files will be:

  • pqarray.cpp and pqarray.h
  • pqclient.cpp
  • pqheap.cpp and pqheap.h
  • short_answer.txt

🏁 Submit to Paperless