Assign4: Priority Queue
Due Monday, July 27 at 11:59 pm
- The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
- Submit by the end of the day Monday deadline for a small, “early-bird” bonus.
- All students have a pre-approved extension or "grace period" that extends until Tuesday end of the day PDT, with no penalty.
- The grace period expires at the end of the day Tuesday, after which we cannot accept further late submissions.
- Note that our Paperless submission system displays due dates and submission times in the 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 about some powerful debugging tools and some of the dangers of working with dynamic memory, you will work on completing two different implementations of a priority queue class. The first implementation will be backed by an array of sorted elements and the second will be backed by a binary heap. In between, you will also analyze and write some "client" code to make use of your brand new data structures, which will help you reason about some of the benefits and drawbacks of the different underlying data organization techiques that you will be utilizing. Onward!
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 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 develop an appreciation for the importance of being vigilant when working with dynamically allocated memory.
- Students will be able to weigh the different costs and benefits of choosing different ways of organizing underlying 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 data structure.
-
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 Analysis Demos
Enjoy a fun conclusion to your class implementation journey. No extra implementation needed, just run some provided demos and watch your new PQueue data structures do all the heavy lifting!
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 (PQHeap) 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 that end, before getting started on Assignment 4, 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 love to get 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)
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
.
Before getting started writing code, we highly recommend reading the CS106B Style Guide. All of your assignment submissions this quarter will be graded on their coding style, and this guide contains the coding standards that make up our style rubric.
Helpful Resources
Here are some resources that you might find helpful for this assignment:
- Trip's Assignment 4 YEAH Slides
- A Guide to Testing Code in CS106B
- Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
- Stanford Libraries Documentation
- Lecture Slides: Wednesday Classes and Object-Oriented Programming, Thursday Dynamic Memory and Arrays, Monday Implementing OurVector, Tuesday Priority Queues and Heaps
- Section: Classes/Objects, Dynamic Memory and Arrays/Pointers
- Textbook Chapter 6 Designing Classes, Chapter 11 Pointers and Array, Chapter 16.5 Partially ordered trees.
Getting help
Working very closely with raw memory and implemeting your own classes can get very tricky! We always recommend drawing lots of diagrams and making use of the debugger whenever possible. As always, we're here to help you if you get stuck. You can contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for code debugging questions – however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. 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 submission checklist to be sure all your ts are crossed and is dotted. Then 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
Note: When submitting to Paperless, due dates are expressed in PDT.