Assign5: Priority Queue

Due Friday, May 22 at 11:59 pm

• The assignment deadline is by the end of the day, Anywhere on Earth.
• Submit by end of day Friday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Monday end of day AoE, with no penalty.
• The grace period expires end of day Monday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in PDT frame of reference.

After spending the first half of CS106B diligently learning how to use data structures to accomplish very cool and powerful things, the time has come to implement your very own data structure! The focus of this assignment is on implementing the Priority Queue class, a variation on the standard queue which allows for slightly more complex ordering behavior based on relative priority of different elements. After a valuable debugging exercise that will teach you some of the most powerful debugging tools you've learned about yet, you will work on completing two different implementations of a priority queue class, as well as a small bit of "client" code to make use of your brand new data structures. Onward!

Learning goals

• Students will be able to implement a class according to a provided interface definition.
• Students will understand the difference between implementing a class and using it as a "client" in their code
• Students will be confident in their ability to create, destroy, and make use of dynamic arrays in their code. Students will also develop an appreciate for the importance of being vigilant when working with dynamically allocated memory.
• Students will be able to weigh the different costs and benefits of having different backing stores of data for data structures, and to reason about how these choices impact the efficiency of the data structure.

Assignment parts

This assignment consists of a warmup debugging exercise and three programming tasks involving the Priority Queue class.

• 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.

• Priority Queue client

  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.

Please note that unlike in previous assignments, the three programming tasks are not equal when it comes to the amount of work being asked of you. In particular, the first two priority queue tasks consist of implementing one function each; the last task involves designing a full class implementation involving eight different functions. Please have this in mind when designing your plan of attack for the assignment!

Getting started

As always, we have provided a ZIP of the starter project. However, this time around, accessing the starter code files will require a little bit of additional work.

As we are always working to make the learning experience in CS106B as good as it can be, feedback from students is one of the most important things that we consider as we design the class going forward and reflect on the things that we have tried so far. To the end, before getting started on Assignment 5, we would appreciate it if you all took about 15-20 minutes of your time to fill out a Mid-Quarter Evaluation regarding your experience in CS106B so far. All responses are anonymous. We would highly appreciate your input, especially considering all the changes and new aspects of the class that we've experimented with in the time of virtual learning. Thank you in advance for taking the time to share your thoughts with us!

Once you have completed the feedback survey, you will be redirected to a page containing the link to the starter code zip. From there, download the zip, extract the files, and open the project in Qt Creator.

📦 Mid Quarter Evaluation (starter code link distributed upon completion of survery)

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

Getting help

Here are some resources that you might find helpful while working on the assignment:

• Nick is hosting a collaborative group work session open to all students on Monday evening from 6-7pm PDT. More details and Zoom info can be found on the Zoom Details page. Come get your conceptual questions about the assignment answered and meet other students also working on the assignment!
• You can find the slides from the Assignment 5 YEAH session here and the recording of the session has been posted on Canvas. We highly recommend starting with these resources as you get started on the assignment.
• Lecture Slides: Monday C++ classes, Wednesday Dynamic Memory, Friday Memory and Pointers, Monday Implementing VectorInt, Wednesday Heaps, Friday Sorting
• Section: Classes/Objects, Pointers/Heaps/Sorting
• Textbook Chapter 6 Designing Classes, Chapter 11 Pointers and Array, Chapter 16.5 Partially ordered trees.
• We’re here to help you get there! Contact us on Ed discussion, email your section leader, or come join non-stop coding party that is the LaiR.

Submit

Review our submission checklist before calling it done. Upload your completed files for grading to the Paperless website.

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

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

🏁 Submit to Paperless

Note: When submitting to Paperless, due dates are expressed in PDT.