Heap and Queueing Assignment using visual studio. C++

Heap and Queueing Simulation

Two BIG Parts

• Implementing Heap – Basic requirement

• Perform a queueing simulation experiment with Priority Queue – Difficult – Treat it as a mini project

Time to Level UP!

Something Different

• We will NOT give you the MSVC .sln or Xcode project – It’s time for you to create your own – Any problem, please refer to Lab 1 slides

Something Different

• We will tell you need to do – Namely, list of tasks

• However – You have to decide the order – There may be some additional unnamed tasks you

have to fill in

Something Different

• You have to learn how to NOT relying on the coursemology output – Instead relying on your own testing cases and

judgement

Given Files

• The Heap files: – heap.h – heap.hpp

• The driver program for your tests – main.cpp

• Customer class, but you can ignore it for the Heap task first – customer.h – customer.cpp

Part 1 Heap Implementation (Array)

Very First Task

• Create your own MSVC .sln or Xcode Project

Implementing Heap

• MaxHeap – Parents > children

• You will implement the Heap with the array representation – It is NOT recommended to implement the heap by

pointer/tree/node representation

• The following functions are provided for you – printHeapArray, printTree, _lookFor

Given Functions

• printHeapArray() – print out the array that stores the heap

• printTree() – print the heap in a graphical tree form… somehow

Given Functions

• The function int Heap<T>::_lookFor(T x)

• It searches for the item x in the array and return the index of x in the heap array

• In real practice, the index of x and x should be stored in a symbol table/dictionary, thus, hash table, for fast look-up of the index of x – O(1) look-up time

• However, we just use a linear search here for our assignment – O(n) look-up time

Implementing Heap

• You have to implement and submit the following functions: – insert(x): Insert an item x into the heap – extractMax(): extract the max. item from the heap – decreaseKey(x,y): decrease the key of item x to y – increaseKey (x,y): increase the key of item x to y – deleteItem(x): remove the item x – _bubbleUp(i): bubble up the item in index i – _bubbleDown(i) : bubble down the item in index i

Implementing Heap

• You have to implement and submit the following functions:

insert(x), extractMax(), decreaseKey(x,y), increaseKey (x,y), deleteItem(x), _bubbleUp(i),_bubbleDown(i)

• What is the order of implementation?!

If You Implemented Correctly

If You Implemented Correctly

Second Part: Queueing Simulation

• Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

Queueing Theory

Model

• Customers – Arrival time – Processing time

• Time need to be served • Queue

– Where customer wait, can be prioritized

• Server – Customers get served and

leave

Questions

• About waiting time – Average WT – Max WT – Min WT – or other WT

• For all customers

Single/Multiple Queue(s) with Multiple Servers

What does the bank do?

Queue with “Priority”

Part 2: Queue Simulation

• First, the code customerTest() will generate 10 customers for you in customer.cpp

• And we assume that there is only ONE server now

Customer Behavior

• All the customers will be stored in the array custList[]

• To make it simple, the customer number is equal to the time they arrived in minutes – E.g. Customer 4 will arrive 4 min after the store

opens

• When the customer arrives, they will wait in the waiting queue if the server is serving another customer

Customer Behavior

• If the server is serving no one, next customer in the queue will be served (dequeued)

• Each customer has a processing time (PT) – The amount of time he will occupy the server

when he left the waiting queue – The server will not server the next one in the

queue until he finish this current one

Waiting Time

• For each customer, his waiting time (WT) is count as the difference between – The time he arrives and the time he starts to be

served (dequeued) – NOT the time he finished being served

Example (Normal Queue)

• Assume that the priority of the queue is FIFO – Normal queue in real life

• Generate four customers (Done for you):

Time at the start of… Customer Server

0 C0 arrives Serves C0 at time 0

1 C1 arrives Serves C1 at time 1

2 C2 arrives Busy with C1

3 C3 arrives Busy with C1

4 Busy with C1

5 Serves C2 at time 5

6 Serves C3 at time 6

• Customer 2 waits for 5 – 2 = 3 min in the queue • Customer 3 waits for 6 – 3 = 3 min in the queue

Output for FIFO

• Total WT = 6 min for all customers • Average WT = 1.5 min for each customer

For 10 Customers (Setup)

Output for FIFO (10 Customers)

However

• If we change the queue priority – It will not be First Come First Served

• Miraculously, there is a smart scanner that can detect the processing time for the customer in the queue

• The server will serve the customer with the LEAST processing time among the people in the queue FIRST

Output For Least PT (10 Customers)

Conclusion?

• What is the difference in the average waiting time for two different policy of the priority of the queue? – FIFO vs Least PT

• Is it just coincident? Or is it always like that?

Difference

• FIFO

• Least PT first

Given Code class Customer { private: int arrival_time; // time of arrival after the shop opened in min int processing_time; // amount of time need to be processed with the customer serivce in min public: Customer () {arrival_time = 0; processing_time = 0;}; void setAT(int t) {arrival_time = t;}; void setPT(int t) {processing_time = t;}; int AT() {return arrival_time;}; int PT() {return processing_time;}; bool operator>(const Customer& c); // a customer is "greater" if his time is shorter };

Comparison For Heap/PQ

• If comparisonWay = 0 – the heap be ordered by arrival times (AT)

• If comparisonWay = 0 – the heap be ordered by processing times (PT)

int comparisonWay = 0; // 0 for arrival time, 1 for processing time bool Customer::operator>(const Customer& c) { return comparisonWay ? processing_time < c.processing_time : arrival_time < c.arrival_time; // a customer is "greater" if his time is shorter };

Actually NOT a good practice to use a global variable

First Part of CustomerQueueTest() void customerQueueTest(int n_cust) { int current_time = 0; int totalWaitingTime = 0; int i; int WT = 0; // waiting time for each customer Heap<Customer> queue; Customer* custList = new Customer[n_cust]; cout << endl << endl << "Setup" << endl; cout << "List of customers and their arrival and processing times" << endl; for (i = 0; i<n_cust; i++) { custList[i].setAT(i); custList[i].setPT((n_cust - i) % (n_cust / 2) + 1 + (i % 2)*(n_cust / 2)); cout << "Customer " << i << " will arrive at time " << custList[i].AT() << " with PT=" << custList[i].PT() << endl; } cout << endl;

Setting up n customers for the test

Following on for (int round = 0; round<2; round++) { // you may need a big modification within this for-loop cout << endl << endl; cout << "Test Round " << round + 1 << endl; cout << (round == 0 ? "First come first serve" : "Customer with the least PT served first") << endl; comparisonWay = round; current_time = 0; totalWaitingTime = 0; queue.insert(custList[0]); cout << "Customer arrives at time " << custList[0].AT() << " with PT=" << custList[0].PT() << endl; while (!queue.empty()) { // you should change all of the code here inside Customer c = queue.extractMax(); cout << "Customer arrives when no one is waiting" << endl; cout << "Customer is served at time " << current_time << " with AT=" << c.AT() << " and PT=" << c.PT() << " after waiting for “ << WT << " min." << endl; } cout << "Total Waiting Time: " << totalWaitingTime << endl; cout << "Average Waiting Time: " << totalWaitingTime / (float)n_cust << endl;

You have to change all the code here!

The purpose for giving you the code here is for all those “cout” such that it will match the coursemology test case

Difference

• FIFO

• Least PT first

Real Job

• Treat the Queueing Simulation part of your assignment as a real job – A mini project

10 ways school is different than the working world

• If you can't do the work, you're out. • We grade on a curve. • … • We hate slackers. • You have to fight for recognition. • We really, really, really want you to be able to write

properly. • We really, really, really want you to be able to do math. • If you can't make money for us, we won't hire you.

https://www.cbsnews.com/news/10-ways-school-is-different-than-the-world-of-work/

We really, really, really want you to be able to write CODE properly