CS2040C Assignment#4-Heap and Queueing Simulation Solved

 

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:

–   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
 

 

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/