Description
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 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 can’t do the work, you’re 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 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/
