Assignment 3 Heap

Submission

  • In Canvas, submit a pdf document with your responses to the writeup questions.
  • In github, commit and push the final version of your code before the assignment deadline. You should get in the habit of pushing changes every time you get a new part of the assignment working.

Overview

In this part of assignment 3, you will compare using a priority queue to a sorted array to keep track of the most important packet of data as your program processes them.

The starter code includes the following files. Files in italics should not need to be modified

For the priority queue program:

  • PriorityQueue.h in which you will implement your priority queue.

  • DataStream.h and DataStream.cpp which have functions to generate fake packets of data. You do not have to worry about any of the implementation code in the .cpp.

  • processPackets.cpp has a main function you will use for the priority queue program

Assignment Requirements & Output

  • You should use functions to make your main a manageable length and easy to understand.

  • Implement functions as efficiently as reasonably possible. (Reasonable means you pick the optimal BigO based on learned structures.)

  • Your code should not have memory leaks or other memory related errors. Check with valgrind

  • You are not to use any library containers (vector/list) to implement your priority queue. You can use utility functions like std::swap.

    It is also OK to use std:: algorithms and vector in your other .cpp files.

    This is different than previous assignments!
  • Do not prompt for ANY input other than what is specified for in the descriptions below.

Output

Anything you are asked to print out should be printed in your final program with a clear label.

Label each section's output and print something like this before each section:

-----------------------------Section 1----------------------------
…

There should not be a lot of extra debugging output.

Grading

Your code will be built and tested from the command line. Your code must compile and run in that environment to receive credit.

I will score the output of your program as is. I will not fix parts of your code so that I can test other parts. If your program dies trying to run part 2 of an assignment, you will NOT get credit for the output of any parts after that, even if they would work perfectly.

You can get partial credit for code that is mostly there but broken. The maximum amount of credit awarded for each section will be:

  • Code runs and provides correct output - full credit.
  • Code runs and provides incorrect output - partial credit, potentially quite high.
  • Code does not run or produce output (potentially because the program crashed in a previous section)- partial credit - generally less than incorrect output.
  • Code that is commented out - partial credit. Less than incorrect output. If part of a program crashes but later parts work correctly, comment it out and leave a note in the output like "Part 4 disabled… causes crash" so I know to go check out what you did.
  • Code that never runs because something before it crashed. Same as commented out code.

Part 0 - Setup

Begin by accepting the assignment repository listed in Canvas.

Create a Makefile. When the make utility is executed in that folder, it should build an executable called program.exe. (You likely want to copy the .vscode folder, .clang-format, and Makefile from the Basic Project template into the folder as well.)

I will test your project by doing exactly this from your project directory:

make
./program.exe

Part 1

(10% of grade : all writeup)

In processPackets.cpp there is an existing program that is designed to simulate receiving and storing packets for processing. Packets come in in batches and each packet (defined in DataStream.h) has a priority and data:

struct Packet {
    //16 bit numeric value representing priority. 
    //Higher priority = more important
    uint16_t priority;

    //Contents of packet
    std::string data;
}

When the program runs it will expect read a single line of input like:
g 10000 p r 5000 p g 10000 p r 15000 q

That would indicate that the program should do the following:
get 10000 packets and store them
print the highest priority packet
remove 5000 packets
print the highest priority one that remains
get 10000 more packets and store them
print the highest priority packet
remove 15000 packets
quit

The current program uses a sorted vector to store packets waiting to be processed (removed). Every time a packet comes in, it uses binary search to find the proper stores the packet into the vector so that the packets in the vector are always in order, with the highest priority packet in back. To remove a packet, it simply removes the last item from the vector.

Run it with the following script:
g X r X q
For X values of 1000, 4000, 16000, and 64000

Writeup

1A) Provide a table of times taken to get and then remove n packets for n = 1000, 4000, 16000, 64000

1B) What is the Big-O of the existing algorithm for getting n packets? Explain your reasoning.

1C) What is the Big-O for the existing algorithm for removing n packets? Explain your reasoning.

1D) How long would this algorithm take to get and then remove 10,000,000 packets? Show work.

Part 2

(25% of grade)

In PriorityQueue.h, implement a priority queue based on an array implementation of a max heap.

You should not modify the signature of existing functions that are declared, but can add additional ones.

You will not be turning in any standalone tests of this part, but you will want to do some testing in main to verify it is working (Again - I'll run my own tests!). Make sure Valgrind doesn't complain about memory issues.

Part 3

(20% of grade: 10% code, 10% writeup)

Replace the vector based code in processPackets.cpp with code to make and use a PriorityQueue to store the packets. Make sure it still works for a script like:

g 1000 p r 500 p g 1000 p 1500 q

Then test it with:
g X r X q
For X values of 1000, 4000, 16000, 64000, and 256000

Writeup

3A) Provide a table of times taken to get and then remove n packets for n = 1000, 4000, 16000, 64000, and 256000

3B) What is the Big-O of the new algorithm for getting n packets? Explain your reasoning.

3C) What is the Big-O for the new algorithm for removing n packets? Explain your reasoning.

3D) How long would this algorithm take to get and then remove 10,000,000 packets? Show work.