Assignment 4. Priority Queue

Due Wednesday, August 2 at 11:59 pm Pacific

  • Submissions received by due date receive a small on-time bonus.
  • All students are granted a pre-approved extension or "grace period" of 24 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Thu, Aug 3 at 11:59 pm Pacific, after which we will deduct 15% per late day.
  • You must submit the assignment by Tue, Aug 8 at 11:59 pm Pacific to receive any credit. We will not accept any submissions past this date.
  • In this course, we express all date/times in Pacific time GMT -7. Our Paperless submission system also displays/records due dates and submission times in Pacific time.

After spending the first half of CS106B learning how to use our provided data structures to accomplish very cool and powerful things, 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 simple array and the second using the fancier and more 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

After completing Assignment 4, you will be able to…

  • Implement a class according to a provided interface definition.
  • Understand how code is written in the role of implementer and how that differs from code written in the role of client.
  • Work with pointers, dynamic arrays, and explicit management of memory using new and delete.
  • Develop an appreciation for the need to be vigilant when working with memory and pointers.
  • Identify tradeoffs in implementations and 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 ethics 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

We provide a ZIP of the starter project. Download the zip, extract the files, and double-click the .pro file to open the project in Qt Creator.

📦 Starter code

The source files you will edit are pqarray.h/.cpp, pqclient.cpp, and pqheap.h/.cpp. Additionally, you will answer questions in short_answer.txt.

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.

We'll host a virtual YEAH session for this assignment on Wednesday, June 26th from 3-4pm, and this session will be recorded and posted to Canvas. 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 LaIR 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