CSE 101 -- Fall 2021

CSE 101 -- Prog 2

Due before midnight, Sunday, October 31, 2021.
Late submissions will not be accepted/graded.

Objectives:

Implement Priority Queue ADT using heap and applications in service sector simulation.

Description:

This program will require you to implement Priority Queue ADT using heap and an application that uses your implementation. The application is a standard and generic logistics/supply chain where we have random arrival of clients (like people arriving at a barber shop) subject to capacity constraints. We will simulate this process and look into how a standard queue and priority queue would differ in terms of the overall waiting time of clients

Details:

As before, input will be from stdin and output will be to stdout.
Queue ADT: Both Queue.h and Queue.c are from your hwk2 and are needed by the simulator.

Heap:
Heaps are a kind of structure that maintains a top-down order of elements it contains. You will also implement the Heap that will be the backbone of the priority queue. This will be a min heap similiar to the textbook. Similarly, you will be implementing the interface provided in Heap.h in the Heap.c.
Priority Queue ADT:
Unlike the sequential processing of items in a queue, a priority queue would rate items by their priority/value (also known as keys) and then prioritize the processing of items that are of higher priority/value. For instance, in the client-haircut setting, we might want to prioritize 'higher value' customers that generate more revenue. You can implement the operations supported by a priority queue using the heap that you developed. These include the ones mentioned in the PriorityQueue.h which you will implement in the PriorityQueue.c file.

Simulator:
You are provided with a simulator.c file that simulates random arrival of clients. The simulator will then process these clients using the queue and priority queue ADTs that you develop to schedule them based on appointment length. We will then see how the two strategies would impact the average wait time of of each client how that is tied to the time constraint. Most of this simulator is implemented for you and you will not need to change the code in that file. More details on how the simulator works is in the corresponding .c file.

Files for this program: The following files are provided to you, and should all be submitted with your work.
- Makefile: You can edit to change compilers and flags.
- Queue.h: Do not change this file. It has a list of functions that you need to implement for the Queue ADT.
- Queue.c: This is the implementation of Queue per the interface provided in the Queue header file. You will have implemented this as your HW2 and need to include it here as the simulator client requires it.
- Heap.h: Do not change this file. It has a list of functions that you need to implement for the Heap.
- Heap.c: This is where you define the Heap struct and implement your Heap. Only type code where you see the TODOs.
- PriorityQueue.h: Do not change this file. It has a list of functions that you need to implement for the Priority Queue ADT.
- PriorityQueue.c: This is where you define the Priority Queue struct and implement your Priority Queue ADT. Only type code where you see the TODOs.
- simulator.c: This is where the discrete-event simulator is implemented for your. You will not need to change the contents of this file but it should be included in you submission as it will be you executable (renamed upon compilation to prog2)

Sample input is provided in:

prog2

Resources:

Check back here for links to TA section recordings and other resources
FAQ

Grading:

Rubric:

You start off with 100 points.
You lose credit for missing functionality, incorrect results,
poorly documented or formatted code, or not following instructions.
Particularly:

- test cases 30 - we have ? test cases each has ? points
- unit tests: 50 points for proper implementation of Queue ADT and Priority Queue ADT
- style and commenting 20 points

Below is a partial list:

- up to 10 points off for inadequate comments or hard-to-read code
- up to 10 points off for not following instructions
- up to 10 points off for special handling to grade your homework (usually
  because you did not check that it runs on the computers in the lab first).
- functionality points depending on importance

Make sure you:
a.  include a makefile, .c files, and .h file
b.  generate an executable file called prog1 with your makefile
c.  have confirmed that it compiles and runs properly on unix.ic.ucsc.edu
d.  followed the general instructions described in overview.html

grading_files

Who graded your assignment based on your CRUZID first letter :
```
nathan: a*  - ju*
bryan: 	jw* - z*
```

Submission:

Make sure that you've compiled and tested your code on the campus unix timeshare before submitting. On the unix timeshare, put materials in a folder named prog2 and zip it up.

submit cse101-ap.f21 prog2 prog2.zip

You can submit as often as you want up until the deadline. We will only look at your most recent submission.

After each submission, you should get a message like:

Submitting the files you specified...
copying XXX

1 File submitted: 
  XXX (revision 2)

where XXX is the material you submitted.

Read the for instructions on how to submit your work.