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

• Its time for you to create your own
• Any problem, please refer to Lab 1 slides

Something Different

• We will tell you what 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:
  • h
  • hpp
• The driver program for your tests
  • cpp
• Customer class, but you can ignore it for the Heap task first
  • h
  • 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

Queue Simulation

Second Part

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.

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 = 1
  • the heap be ordered by processing times (PT)

int comparisonWay = 0; // 0 for arrival time, 1 for processing

arrival_time < c.arrival_time;

// a customer is greater if his time is shorter };

First Part of CustomerQueueTest()

void customerQueueTest(int n_cust) { Setting up n int current_time = 0; customers for the

int totalWaitingTime = 0;

int i; test

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;

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 You have to << custList[0].AT() << with PT= << custList[0].PT() << endl;

while (!queue.empty()) { change all the

// you should change all of the code here insidecode here!

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;

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 cant do the work, youre out.
• We grade on a curve.
• We hate slackers.
• You have to fight for recognition.
• We realWe really, really, really want you to be able to write y, really, really want you to be able to write properly.CODE properly
• We really, really, really want you to be able to do math.
• If you cant make money for us, we wont hire you.

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