Assignment 5. Priority Queue

Due Wednesday, October 28 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 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Fri, Oct 30 at 11:59 pm Pacific, after which we cannot accept further late submissions.
  • 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 one uses a sorted array and a second more efficient approach that uses a binary heap. You will also analyze and write client code that uses your new data type and use that code to reason about the tradeoffs in the two alternative implementations. 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 efficiency of the data structure.

Assignment parts

This assignment consists of a warmup debugging exercise, three programming tasks, and a fun demo capstone.

  • Warmup

    Practice with debugging on objects and arrays/memory.

  • PQSortedArray

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

  • PQueue Client Tasks

    Solve data processing tasks as a client of the Priority Queue class.

  • PQHeap

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

  • Data Science Demos

    Enjoy a fun conclusion to all your hard work. No additional code to write, just run our provided demos and watch your new Priority Queue do all the heavy lifting!

Please note that the three programming tasks are not equal when it comes to the amount of work being asked of you. Whereas the PQSortedArray and PQ Client tasks ask you to to complete one function; 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 pqsortedarray.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 have several channels where you can reach out to the course staff: post on Ed, email your section leader, join in at office hours, or sign up for one-one-one help at the LaIR. For questions specific to your code, coming to Lair is your best bet. If you cannot attend LaIR due to timezone issues, you may post your question on Ed. However, you must use a private post if you are including code so that you are not posting your solutions for the whole class to see.

Submit

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

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

  • pqsortedarray.cpp andpqsortedarray.h
  • pqclient.cpp
  • pqheap.cpp and pqheap.h
  • short_answer.txt

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in Pacific time.