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!
This assignment consists of a warmup debugging exercise and three programming tasks involving the Priority Queue class.
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!
This exercise will add a few new tricks with the debugger to your repertoire that will come in handy for this assignment and into the future.
Debugging objects
The files ball.h and ball.cpp define a Ball class similar to a lecture example from last week.
First, look over the code to get acquainted with it. Each ball is created with a ID number that is used as the label when drawing the ball. The ID number helps identify which ball is which in the window.
There is one provided test for the Ball class. This test constructs many Ball objects and runs an animation loop to repeatedly move and redraw each ball.
Run the program and select the tests for ball.cpp. A new windows pops up and a swarm of numbered balls bounce around within the window. Cool! After about 20 seconds, the test completes and the window closes.
Figure: see image.
This version of the ball animation has a bug that sometimes causes balls to bounce incorrectly. You will use the debugger to help you track down the bug.
Run the program again under the debugger. While the balls bounce around, arrange the graphics and the debugger windows on your screen so you can see both simultaneously. In the debugger window, set a breakpoint on the line in ball.cpp where pause is called at the bottom of the animation loop. The debugger stops at this breakpoint almost immediately.
Click the Continue button to resume execution, and the program will execute another loop iteration and stop again at the breakpoint. Click Continue a few more times and keep an eye on the graphics window as you do this. During each iteration of the loop, all of the balls slightly move.
Object member variables
When stopped at the breakpoint, look to the "Variables" pane of in the upper-right of the debugger window. Click the triangles to expand the allBalls Vector, its _elements, and the elements at indexes [0] and [1]. Each element is one Ball object. An object has its own private versions of the member variables, so each ball has its own position x,y, velocity and id.
Click Continue a few more times, observing the updates to the member variables for allBalls[0] and allBalls[1] in the Variables pane and match that to the movement of those balls in the graphics window.
Answer this question in short_answer.txt:
The variable this
Now click the red dot for your previous breakpoint to delete it. Set a new breakpoint on the first line of the Ball::move method. The debugger will now stop on each ball move. When stopped at this breakpoint, look at the variables in the Variables pane. Because execution is inside a C++ member function, there is a special variable called this that refers to the object currently executing the member function. When stopped inside the function Ball::move, this refers to the ball that is currently taking its turn to move. Expand this to see the member variables of the object. Use this ball's position and id to locate the corresponding ball in the graphics window.
Click the Continue button to resume. The breakpoint is hit again on the next call to Ball::move. Note that this now refers to a different Ball object, with its own member variables. Click Continue a few more times to see some other balls take their turn to move.
Control-click on the red dot for your breakpoint to bring up the pop-up menu and choose Disable breakpoint. This leaves the breakpoint in place but makes it inactive. It is marked with a dim red dot. Use Continue to resume execution and the balls should freely animate without stopping.
Debugging in the context of randomness
When the program begins, each ball is created with a starting position and velocity; these values are chosen randomly. Quit and restart the program a few times to observe how the initial configuration varies from run to run. Debugging a program that has random features can be challenging as you may not be able to reproduce a particular scenario at will. Sometimes your best option is to just keep an eye out for an intermittent bug and opportunistically jump into debugging whenever you encounter it.
If you run the program a few times, you may notice that occasionally a ball or two gets "stuck" along the bottom or right edge of the window. This is the bug we are trying to diagnose. Let's see if we can get this under the debugger to investigate further.
Quit and restart the program in Debug mode until you get a starting configuration where at least one ball stuck and enough of the stuck ball is visible that you can see its ID number. (It may take a few tries.)
Control-click on the dim red dot for the disabled breakpoint in Ball::move and choose Enable breakpoint from the pop-up menu. With this breakpoint active, it stops at every single move for every single ball. Since there are many balls and each moves many times per second, having to stop and continue on each move is very tedious. We would much rather zero in on the ball in trouble. For example, in this case, we know the ID of the stuck ball. Ideally, we want to step through the move of only that ball, and zip past the others.
Conditional breakpoints
The debugger has just the thing we need: a conditional breakpoint. A condition can be added to a breakpoint to tell the debugger to only stop the program at this breakpoint if a certain condition is met.
Control-click on the breakpoint's red dot and choose Edit breakpoint from the pop-up menu. Look for the text field labeled Condition. The condition is any C++ expression that is valid to be evaluated at the breakpoint location and can refer to local variables and parameters. Each time execution reaches the breakpoint location, the condition is re-evaluated and the debugger stops only if the condition evaluates to true, otherwise it behaves as if the breakpoint were inactive and just continues on past.
Figure: see image.
Let's try it out! Add a condition on the breakpoint to only stop if _id is the ID number of the stuck ball in your configuration. The breakpoint in Ball::move will only stop when executing for the stuck ball. Each Continue should take the program straight through to this particular ball's next move.
(Instructor's Note: We have found the Qt debugger to be a little flaky when handling breakpoint conditions. Sometimes it stops even when it shouldn't, but continuing once or twice seems to straighten it out. Your patience and tolerance will be rewarded; conditional breakpoints can be a great help for debugging a complex situation. Advanced features like can stress out the debugger, so if you give a few tries and it won't cooperate, just note that in your answers and move on.
Focus on observing what's happening to the stuck ball on each move. Do a couple of rounds with Continue, noting how the values of its member variables are changing. Contrast what is happening for the stuck ball to what what you observed earlier for a correctly moving ball.
Answer the following question in short_answer.txt
Changing variables in the debugger
You have a hunch that forcibly moving the stuck ball to a different position would cause it to right itself. The Variables pane of the debugger allows you to change the value of a variable in a running program. Double-click to edit the _x and _y fields and place this ball at position (0, 0). The next time this ball is drawn it should appear in the upper left corner of the graphics window, where you have teleported it.
(Note: Sometimes the Qt debugger is unable to process your update to the variables and reverts to the previous value. If this happens to you, just note it in your answer to the question below).
Answer the following question in short_answer.txt
Given the above detective work, do you see what caused the ball to become stuck? What fix is needed to avoid getting into this situation? You may optionally try to modify the code to fix it, though this is not required.
A conditional breakpoint can be a godsend when debugging a program that works correctly almost all the time and only rarely hits a bug. Rather than having to first wade through lots of correct operations, the conditional breakpoint lets you zero on exactly and only the situation that needs attention.
Debugging arrays and memory
The last task is to practice debugging on arrays and memory. Pointers can be a fairly lethal part of the C++ language, as there are many pitfalls you can fall into with harsh consequences. It will take your finest debugging skills to diagnose these woes, so let's do some practicing now.
Changing the display format
You've used the Variables pane to see the values of variables, as well as click the triangle to expand an ADT or object to see its internal data. Our next Pro Tip is how to view the contents of an array.
Review the code in the test cases of the warmup.cpp file. The first test case demonstrates correct use of an array. Set a breakpoint within the test case on the statement after the loop has completed initializing the array elements. Run the program under the debugger and select the tests for warmup.cpp.
When the program stops at the breakpoint, look at how the shoppingList variable is displayed in the Variables pane. A C++ array does not track its length, so the debugger does not know how many elements to display for an array. Unless told otherwise, the the debugger assumes the array length is 1 and displays only the first value. To see additional elements beyond the first, you must tell the debugger how many items to display.
In the Variables pane, control-click the array variable to bring up the pop-up menu and choose "Change Value Display Format". In the submenu, look for the section labeled "Change Display for Object Named " and select "Array of 10 items" from the options.
Figure: see image.
The options for array length are 10, 100, 1000, and 10000. If your array contains 50 items, you have to choose whether to display only the first 10 or display 100, where the first 50 are valid followed by an additional 50 garbage items.
Examine array memory
Change the display format for shoppingList to an Array of 10 items. The Variables panel adds a triangle to the variable and if you click to expand, it will display 10 Item structs, indexed by position.
In this code, the array memory was allocated to hold 6 Item structs. The loop initialized the first 3 elements. Examine the values of the elements at index [0],[1] and [2] to see that they are as expected.
The indexes [3] [4] and [5] are a valid part of the array memory, but these elements have not been initialized. C++ has set the values according to what it normally does for that type of variable. In particular,
It also is displaying slots for indexes [6] through [9] (because we told the debugger to display 10 elements, remember?), but these slots are beyond the valid range of the array memory. Although the debugger gamely shows the contents of the memory at that location, these contents are even trashier than before; both the integers and the strings are an unpredictable mix of empty, < not accessible>, and random values.
What you see in the debugger parallels what you would observe in an executing program. The value of a variable that has not been initialized is the default value for the type (empty for string or a collection type) or random for the primitive types like int. If your code accesses an index beyond the valid range of the array, you simply get garbage contents.
Arrays have no helpful "out of bounds" message to alert you to your mistake. The programmer herself must be vigilant!
Debugging memory mistakes
The warmup.cpp file contains additional test cases that each demonstrate a common error in handling array/memory:
Study the code in each test case to understand why the code is in error.
We want you to observe how these errors are going to present themselves. The test cases are currently commented out. Pro tip: To quickly comment a section in or out, select the lines and use "Toggle Comment Section" under the Edit Menu, bound to the hot key Command-/.
Uncomment the first test case (nullptr) and rebuild. Run the program without the debugger.
Whereas ordinary programming errors may cause a program to compute the wrong answer, mis-draw a fractal, or get stuck in a infinite loop, memory errors tend to be much more consequential. This particular error is fatal - the program immediately halts, closes all windows and disappears, leaving behind only a pitiful cry for help in the form of a crash report. Click the "Application Output" tab of the Qt Creator window to see the crash report which will look something like this:
***
*** STANFORD C++ LIBRARY
*** A segmentation fault (SIGSEGV) occurred during program execution.
*** This can happen when you dereference a pointer to an invalid memory address
*** (possibly out of bounds, deallocated, nullptr, or ...).
***
Whenever you encounter a crash, your next move is to run that same code under the debugger.
Rather than exit on fatal error, a crashing program will stop in the debugger at the critical point. This give you a chance to see where the code was executing at the time of the crash and poke around and observe the program state. Run the fatal test case under the debugger and it will stop at the exact line of the bad dereference, allowing you to see that the value of shoppingList is 0x0. (nullptr is the memory address zero).
After you're done exploring a test case, comment it back out. Then uncomment the next test case and try that one.
For each test case, you want to observe what happens without the debugger and again with it. Some memory errors present loud and clear with a distinctive crash, others silently and insidiously do the wrong thing. The very same error can get different results in a different context or when executing on a different operating system. All of this makes debugging memory errors extra hairy.
Take note of how each error is presented on your system so you can recognize it in the future should you need to diagnose a similar error in your own program. Answer the following question in short_answer.txt
The Priority Queue data structure
A standard queue processes elements in the first-in, first-out ("FIFO") manner typical of ordinary waiting lines. New elements are added to the back of the queue and the next element to be processed is taken from the front. Queues can be handy, but a FIFO strategy isn't always what's needed.
A hospital emergency room, for example, needs to schedule patients according to priority. A patient with a more critical problem will pre-empt others that arrived earlier, allowing their problems to be addressed earlier. The data structure that we need in order to enable this behavior is a priority queue. The highest priority element in the queue is considered frontmost and will be dequeued first. As we will see later on in the assignment there are many practical applications for a priority queue, both inside and outside of computer science!
PQSortedArray Class
In order to provide this desired functionality, we turn to harness the power of classes in C++ and define our own ADT class called PQSortedArray. This class will be defined and used much in the same way that we have seen so far with collection classes like the Queue, Vector, and Set. The only difference is that this time around, instead of relying on the Stanford libraries to define the behavior of these class, we take the power into our own hands! The whole purpose of designing a class in this case is to hide the messy details (keeping the elements in sorted order, always removing the one with highest priority, etc.) inside the implementation and present a clean abstraction for use by the client.
Although our discussion in class centered around how to use a binary heap as the data storage backing for a Priority Queue, we are first going to take a step back and try out a simpler approach to get you warmed up and thinking about class interfaces and dynamic memory. One possibility for implementing a priority queue would be to store the elements in an array and keep the array in sorted order. In this way, it is quick to find the frontmost element that should be dequeued, as it will always be either the first or the last element in the array, depending on whether we store the elements in increasing or decreasing order.
Below is the interface for the PQSortedArray class. Note that the public interface of the Priority Queue class is identical to that of the standard Queue. The only operational difference is that the highest priority element is treated as frontmost for peek/dequeue rather than the element that was enqueued first.
Ideally the class would be written as a generic that allows the user's choice of element type, but alas, we have yet to introduce you to those mechanisms, so we will have to settle for making the class specifically handle elements that are represented as integers. Importantly, the integer value will be treated as the element's priority. Smaller integers are higher priority than larger and will be dequeued first.
class PQSortedArray {
public:
PQSortedArray();
~PQSortedArray();
void enqueue(int element);
int dequeue();
int peek() const;
bool isEmpty() const;
int size() const;
void clear();
private:
int* _elements;
int _count;
int _capacity;
};
Note: For this part of the assignment, you will not be implementing the whole class interface, but rather just one component (function) of it) There is a lot of write-up in order to get you to the point of understanding what the task is, but worry not, you will only have to implement one function! We have provided a nearly complete implementation of the PQSortedArray class that is missing only the enqueue operation. Your goal is to review the given code to learn how the class operates and then implement the final missing operation.
The PQSortedArray stores the elements in an array. The array elements are to be stored in order of highest to lowest value. The enqueue operation must find the correct position in the array to place the new element and move the other elements aside to make room for it.
The other important job of enqueue is to grow the array when it is filled to capacity. As seen in the lecture example VectorInt, the task of enlarging the array fits nicely in a helper function. Add a declaration of the helper function to the private section of the class interface and define it as part of the class implementation. You can then call the helper from enqueue when appropriate.
Notes
Testing and timing
With a correct implementation of the missing enqueue function, you should now have a fully working priority queue. Use the provided tests to exercise the PQSortedArray. Work through any test failures and resolve the issues until you are confident your implementation is fully correct.
Once your code is finalized, do some time trials on the PQSortedArray operations. First predict what you expect to be the Big O of enqueue and dequeue. Use the SimpleTest timing operation to measure the execution time over 4 or more different size inputs. You should choose sizes so that the largest operation completes in under a minute or so.
Answer these questions in short_answer.txt:
We bring you this little interlude between the PQSortedArray and PQHeap to appreciate the utility of the Priority Queue class abstraction in solving interesting and challenging problems.
While implementing a class, you as the programmer have your head down and are focused entirely on getting the class to work appropriately, navigating all the challenges and tricky small details along the way, as you probably just experienced when completing the implementation of PQSortedArray! However, once the class is completed and working as expected, what a delight it can be to switch hats to become a client of your own data structure and take advantage of what the class has to offer! Remember how in previous assignments when you made use of Vector and Map to solve problems without worrying about how those types were actually implemented? Let's go there now and see what we can do with a working implementation of a handy data structure like the PQSortedArray now in our repertoire.
Sorting via Priority Queue
Given our discussion in lecture on Friday about different sorting algorithms, it seems almost too fortuitous that we can actually use a priority queue as a tool for sorting! Since we know that internally a priority queue always maintains its elements in sorted order, we can devise a devilishly simple sorting algorithm as follows: * Given a list of values, originally unsorted * Enqueue the values into a priority queue * Then, repeatedly call dequeue to pull them out, overwriting the original list with the elements now in order Voila! You have the sorted the input list into increasing order!
The four-line of pqSort in pqclient.cpp does exactly this:
void pqSort(Vector& v)
{
PQSortedArray pq;
for (int i = 0; i < v.size(); i++) {
pq.enqueue(v[i]);
}
for (int i = 0; i < v.size(); i++) {
v[i] = pq.dequeue();
}
}
Answer the following questions in short_answer.txt:
Streaming top K via Priority Queue
The second priority queue client application we will consider is a neat algorithm that solves an interesting "challenge" problem often presented in coding interviews. The streaming top-k problem is the task of returning the k elements with the largest values from a stream of values. The stream is expected to contain a enormous count of values and k is small; the goal is to complete the task efficiently in both use of space and time.
Using a priority queue as a building block is a great approach to solving this problem, as this data structure lends itself naturally to the task of keeping track of some subset of elements as designated by their integer priority (their value in this case).
You are to write the function
Vector< int> topK(istream& stream, int k);
takes as input a data stream and a number k, then returns a Vector of k values from that stream with the largest values. If there are fewer than k elements in the data stream, it return all the elements in that stream. The elements in the returned vector are arranged in descending order, the maximum value is at index 0, the next largest at index 1, and so on.
You might have noticed that the input to this function is not provided by a Vector< int>, but rather by an istream, which is usually something you'd hook up to a file or to the console. Why is this?
Imagine you're working at Google and have a file with how many times each search query was made in a given day. You want to find the 1,000 most popular searches made that day. Google gets billions of search queries in a day, and most computers simply dont have the memory to hold all those queries at once. That would mean that you couldnt create a Vector< int> to hold all the values from the file; it would take up more memory than your computer has available!
When you read data from a file stream in C++, on the other hand, the full contents of that stream don't all have to be held in memory at the same time. Instead, whenever you try reading data from the stream, the stream calls out to your computers hard drive to get a bit more information. This means that you can process the elements from a data file one at a time without filling up your computers memory; the space to hold each element from the file gets recycled each time you pull in a new element.
In the case of this problem, your goal is to implement your function such that you can find the top k elements using only O(k) space; that is, space proportional to the number of elements you'll need to return. In other words, if you wanted the top 1,000 search queries from Google, it wouldnt matter that there are billions or tens of billions of search queries per day. Youd only need to use enough memory to hold about a thousand or so of them. Wow!
Write your implementation of topK and use our provided tests to confirm that the function works correctly.
Answer the following questions in short_answer.txt:
Notes
int num;
while (stream >> num) {
/* do something with num */
}
Vector< int> counts(5); // construct array of size 5
counts[0] = 106;
counts[1] = 930;
Now you are ready for the pice de rsistance of the assignment implementing the priority queue as a binary heap.
ADTs for the win
One of the neat things about a C++ class as an abstraction is that you can swap out its innards for a totally different implementation, such to improve the performance or use a more compact representation, while your clients continue on using the same interface unaware and unaffected.
For this task you will implement the PQHeap class using a binary heap. This version of the priority queue has the same operational behavior as the PQSortedArray you worked on earlier, but runs with much higher efficiency. This will allow the priority queue client applications to scale to much higher input sizes than was possible with the much slower PQSortedArray.
The PQHeap class
The PQHeap class has the same public interface as the PQSortedArray:
class PQHeap {
public:
PQHeap();
~PQHeap();
void enqueue(int priority);
int dequeue();
int peek() const;
bool isEmpty() const;
int size() const;
void clear();
private:
};
The private section is left for you to define as part of your implementation.
The pqheap.h file includes documentation of the expected behavior of each operation, including the required handling for error conditions such as attempting to peek an empty queue.
Specification for PQHeap
The dequeue operation needs to be able to quickly retrieve the frontmost element, but keeping the entire array in fully sorted order as PQSortedArray did is actually a bit of overkill in its approach. The binary heap is a partially-ordered data structure optimized for quick access the frontmost element (and those near the front) and gives less attention to sorting those elements all the way in the back. A binary heap is ordered in a much weaker sense than a sorted array, but its form of ordering is still sufficient for highly efficient performance of the enqueue and dequeue operations.
Here are the details of the specific implementation we require:
Advice
Break the speed barrier
Return to your role as client of the Priority Queue and change the the functions pqSort and topK in pqclient.cpp to use your shiny new PQHeap in place of that pokey old PQSortedArray. The only change required is the type of the variable declaration, let's here for the power of abstraction! Re-run your previous time trial tests, increasing the sizes to a range appropriate for this zippy implementation.
The action of pqSort using PQHeap is akin to the sorting algorithm heapsort, a classic O(NlogN) performer. Streaming top-k should operate in time O(NlogK), using space proportional to K. That some impressive work you've done!
Answer the following questions in short_answer.txt:
Extensions
Looking to go further with the priority queue? There are lots of directions you could take this project!