Please, could you help me with this assignment.
ITI 1121. Introduction to Computing II Winter 2022 Assignment 3 Mehrdad Sabetzadeh (Last modified on February 24, 2022) Deadline for Assignment 3: March 21, 2022, 11:30 pm Introduction In this assignment, we continue with the parking-simulator theme established in Assignments 1 and 2. Our goal in Assignment 3 (A3) is as follows: knowing a priori the car arrival rate and how long cars stay in the lot, we would like to determine the minimum number of spots that the parking lot should have to avoid excessive queue buildup at the entrance. What we do in A3 represents a real-world application for simulation: when a real parking lot is being designed, an informed decision needs to be made about how many spots are needed. If there are too few spots, the parking lot will be overwhelmed; in our simulation, such a situation manifests itself as an unacceptably large queue buildup at the parking entrance. Just as having too few spots is problematic, having too many is problematic too! If the capacity of the parking lot exceeds demand by a large margin, the lot will be under-utilized. If this happens, the operational costs of the lot may exceed the revenue that the lot generates, potentially making the lot financially unviable. Finding a balance between supply and demand is therefore essential. What we aim to calculate in A3 is “just the right number of spots”, given an hourly car arrival rate and the probability distribution for how long a car stays parked once it has entered the lot. For simplicity, like in A2, we assume that the probability distribution for departures is fixed. The code that you develop in A3 therefore has only one user-defined parameter: the hourly car arrival rate. Provided with this parameter, your implementation should simulate the parking lot for different numbers of spots and determine the lowest number of spots that meets demand (we discuss what we mean by “meeting demand” a bit later). Like in A2, a simulation run spans 24 (simulated) hours. However, in contrast to A2, we need to run the simulation numerous times rather than just once. Specifically, we need to progressively try larger numbers of spots 1,2, . . ., all the way to the number of spots that would meet demand. For example, suppose we set the hourly rate to 3 cars per hour. To determine how large our lot should be for this level of demand, we start by simulating a lot that has only one spot, then a lot that has only two spots, then a lot that has only three spots, and so on. Let us assume that, through this process, we determine that our lot needs 15 spots to meet demand. This means that we will have simulated the parking lot 15 times, each time for 24 (simulated) hours. The question that now arises is whether we can trust a single simulation run? For example, if we run the simulation only once with 15 spots and somehow we see that there is no queue buildup at the entrance, can we have reasonable confidence that 15 spots would be sufficient? The answer is No! Why? Because our simulation is probabilistic. Like in every probabilistic process, we need to mitigate random variation, that is, the chances of being too lucky or too unlucky in a single run. And, how do we mitigate random variation? By repeating the simulation process several times. A common strategy is to have 10 repetitions and consider the average results. Going back to our example in the previous paragraph, to account for random variation, we need to run the simulation 10 times for a lot that has one spot, 10 times for a lot that has two spots, and so on. This means that we will have simulated the parking lot 150 times (as opposed to merely 15 times) in the scenario described earlier where we found 15 spots would meet demand. In A3, what we want to obtain from an individual simulation run is the number of cars left in the entrance queue after 24 (simulated) hours. To accept a number n of spots as meeting demand, we repeat for 10 times the simulation with n spots. If the average queue size (across 10 runs) is below a given threshold, we can be reasonably confident that having n spots is sufficient. For this assignment, we define “meeting demand” as yielding an average entrance queue length of ≤ 5 across 10 simulation runs. In other words, if we repeat the simulation with n spots for 10 1 1. Initialize lot size (n) to 1; 2. Repeat { 3. Do 10 times { 4. Simulate the lot for 24 hours at the (user-provided) car arrival rate; 5. } 6. Take the average of incoming queue sizes across the 10 simulation runs; 7. if (average <= 5) { // the lot is large enough to meet demand 8. break out of the repeat loop; 9. } else { // the lot is still not large enough to meet demand 10. n = n + 1; 11. } 12. } figure 1: algorithm (pseudo-code) for determining the number n of spots to meet parking demand times, take the average of the queue length at the entrance (after 24 simulated hours), and this average is ≤ 5, then we are done and return n as meeting demand. figure 1 provides the pseudo-code for finding the smallest number of spots n that meets demand. you get to implement this algorithm in task 4, below. to simplify the implementation and further to give you more exposure to the new concepts we will see in class (particularly lists), various tweaks need to be made to the code you previ- ously wrote in a2 before you can adapt that code for a3. to assist you with the implementation, this assignment is broken down into five tasks, numbered 1 to 5, as discussed below. please keep in mind that the tasks are not of equal sizes. for a3, you can reuse the code you wrote in a2 as well as the reference a2 solution provided to you. task 1. complete the parkinglot class. the parkinglot class is going to be simplified considerably in a3. first, there is no lot design anymore: we assume that any car can park at any spot. the cartype enumeration is therefore gone from a3. we further let go of the rectangular (2d-array) design of the lot. the parkinglot class now has a capacity instance variable (primitive integer) storing the maximum number of cars that the lot can accommodate. occupancy is now stored in an instance variable, occupancy, which is of type list. we use the linkedlist implementation of list in a3. in task 1, you get to implement selected methods of parkinglot using lists (as opposed to arrays). these methods that you need to implement (or enhance) are: • public parkinglot(int capacity) • public void park(car c, int timestamp) • public spot remove(int i) • public boolean attemptparking(car c, int timestamp) • public spot getspotat(int i) • public int getoccupancy() for details about what the methods in our new version of parkinglot should do, please consult the documen- tation and comments in the a3 starter code. 2 task 2. implement size() and peek() in the linkedqueue class. in a2, not being able to simply get the size of a queue posed a challenge. there, we had to dequeue all the elements to count how many elements were in the queue. in a3, we have enhanced the queue interface to provide a size() method. we have also enhanced queue with a peek() method to allow us to peek at the element at the front of the queue. recall that in a2, when we dequeued a car and the attempt at parking that car failed, we needed special treatment for that now-dequeued element. we can provide a cleaner implementation of our simulator if we have a peek() method for queues, similar to what we saw in class for stacks. in task 2, you get to implement size() and peek() for the linkedlist-based implementation of queues, linkedqueue, which we will have seen in class. to keep track of the queue size, you will need to define an additional instance variable. task 3. update the simulator class. modify the simulate() method in the simulator class to work with the revised interface of parkinglot and the new peek() method in queue. in addition, implement the getincomingqueuesize() method of simulator using the size() method of queue. the getincomingqueuesize() is going to be used in the capacityoptimizer class (next task) to determine the size of the incoming queue after a simulation run. important!: to complete tasks 1 and 3, please start with the starter code provided for a3 and bring what you need from a2 one method at a time. do not start with your a2 implementation. several small changes have been made since a2; you would not want to get stuck due to these changes potentially going unnoticed. task 4. complete the capacityoptimizer class. implement the algorithm of figure 1. your implementation will go into the getoptimalnumberofspots(...) method of capacityoptimizer. this method writes out statistics to the standard output. the format of the re- ported statistics is straightforward and illustrated below. note that in our illustration, the results for lot sizes between 2 and 13 have been removed due to space. $ java capacityoptimizer 3 ==== setting lot capacity to: 1==== simulation run 1 (23ms); queue length at the end of simulation run: 68 simulation run 2 (11ms); queue length at the end of simulation run: 66 simulation run 3 (11ms); queue length at the end of simulation run: 73 simulation run 4 (10ms); queue length at the end of simulation run: 61 simulation run 5 (10ms); queue length at the end of simulation run: 82 simulation run 6 (9ms); queue length at the end of simulation run: 61 simulation run 7 (10ms); queue length at the end of simulation run: 76 simulation run 8 (9ms); queue length at the end of simulation run: 63 simulation run 9 (8ms); queue length at the end of simulation run: 61 simulation run 10 (9ms); queue length at the end of simulation run: 64 [... results for lot sizes 2 to 13 not shown due to space ...] ==== setting lot capacity to: 14==== simulation run 1 (92ms); queue length at the end of simulation run: 1 simulation run 2 (82ms); queue length at the end of simulation run: 7 simulation run 3 (103ms); queue length at the end of simulation run: 4 simulation run 4 (97ms); queue length at the end of simulation run: 18 simulation run 5 (95ms); queue length at the end of simulation run: 14 simulation run 6 (94ms); queue length at the end of simulation run: 1 simulation run 7 (98ms); queue length at the end of simulation run: 4 simulation run 8 (81ms); queue length at the end of simulation run: 2 5)="" {="" the="" lot="" is="" large="" enough="" to="" meet="" demand="" 8.="" break="" out="" of="" the="" repeat="" loop;="" 9.="" }="" else="" {="" the="" lot="" is="" still="" not="" large="" enough="" to="" meet="" demand="" 10.="" n="n" +="" 1;="" 11.="" }="" 12.="" }="" figure="" 1:="" algorithm="" (pseudo-code)="" for="" determining="" the="" number="" n="" of="" spots="" to="" meet="" parking="" demand="" times,="" take="" the="" average="" of="" the="" queue="" length="" at="" the="" entrance="" (after="" 24="" simulated="" hours),="" and="" this="" average="" is="" ≤="" 5,="" then="" we="" are="" done="" and="" return="" n="" as="" meeting="" demand.="" figure="" 1="" provides="" the="" pseudo-code="" for="" finding="" the="" smallest="" number="" of="" spots="" n="" that="" meets="" demand.="" you="" get="" to="" implement="" this="" algorithm="" in="" task="" 4,="" below.="" to="" simplify="" the="" implementation="" and="" further="" to="" give="" you="" more="" exposure="" to="" the="" new="" concepts="" we="" will="" see="" in="" class="" (particularly="" lists),="" various="" tweaks="" need="" to="" be="" made="" to="" the="" code="" you="" previ-="" ously="" wrote="" in="" a2="" before="" you="" can="" adapt="" that="" code="" for="" a3.="" to="" assist="" you="" with="" the="" implementation,="" this="" assignment="" is="" broken="" down="" into="" five="" tasks,="" numbered="" 1="" to="" 5,="" as="" discussed="" below.="" please="" keep="" in="" mind="" that="" the="" tasks="" are="" not="" of="" equal="" sizes.="" for="" a3,="" you="" can="" reuse="" the="" code="" you="" wrote="" in="" a2="" as="" well="" as="" the="" reference="" a2="" solution="" provided="" to="" you.="" task="" 1.="" complete="" the="" parkinglot="" class.="" the="" parkinglot="" class="" is="" going="" to="" be="" simplified="" considerably="" in="" a3.="" first,="" there="" is="" no="" lot="" design="" anymore:="" we="" assume="" that="" any="" car="" can="" park="" at="" any="" spot.="" the="" cartype="" enumeration="" is="" therefore="" gone="" from="" a3.="" we="" further="" let="" go="" of="" the="" rectangular="" (2d-array)="" design="" of="" the="" lot.="" the="" parkinglot="" class="" now="" has="" a="" capacity="" instance="" variable="" (primitive="" integer)="" storing="" the="" maximum="" number="" of="" cars="" that="" the="" lot="" can="" accommodate.="" occupancy="" is="" now="" stored="" in="" an="" instance="" variable,="" occupancy,="" which="" is="" of="" type="" list.="" we="" use="" the="" linkedlist="" implementation="" of="" list="" in="" a3.="" in="" task="" 1,="" you="" get="" to="" implement="" selected="" methods="" of="" parkinglot="" using="" lists="" (as="" opposed="" to="" arrays).="" these="" methods="" that="" you="" need="" to="" implement="" (or="" enhance)="" are:="" •="" public="" parkinglot(int="" capacity)="" •="" public="" void="" park(car="" c,="" int="" timestamp)="" •="" public="" spot="" remove(int="" i)="" •="" public="" boolean="" attemptparking(car="" c,="" int="" timestamp)="" •="" public="" spot="" getspotat(int="" i)="" •="" public="" int="" getoccupancy()="" for="" details="" about="" what="" the="" methods="" in="" our="" new="" version="" of="" parkinglot="" should="" do,="" please="" consult="" the="" documen-="" tation="" and="" comments="" in="" the="" a3="" starter="" code.="" 2="" task="" 2.="" implement="" size()="" and="" peek()="" in="" the="" linkedqueue="" class.="" in="" a2,="" not="" being="" able="" to="" simply="" get="" the="" size="" of="" a="" queue="" posed="" a="" challenge.="" there,="" we="" had="" to="" dequeue="" all="" the="" elements="" to="" count="" how="" many="" elements="" were="" in="" the="" queue.="" in="" a3,="" we="" have="" enhanced="" the="" queue="" interface="" to="" provide="" a="" size()="" method.="" we="" have="" also="" enhanced="" queue="" with="" a="" peek()="" method="" to="" allow="" us="" to="" peek="" at="" the="" element="" at="" the="" front="" of="" the="" queue.="" recall="" that="" in="" a2,="" when="" we="" dequeued="" a="" car="" and="" the="" attempt="" at="" parking="" that="" car="" failed,="" we="" needed="" special="" treatment="" for="" that="" now-dequeued="" element.="" we="" can="" provide="" a="" cleaner="" implementation="" of="" our="" simulator="" if="" we="" have="" a="" peek()="" method="" for="" queues,="" similar="" to="" what="" we="" saw="" in="" class="" for="" stacks.="" in="" task="" 2,="" you="" get="" to="" implement="" size()="" and="" peek()="" for="" the="" linkedlist-based="" implementation="" of="" queues,="" linkedqueue,="" which="" we="" will="" have="" seen="" in="" class.="" to="" keep="" track="" of="" the="" queue="" size,="" you="" will="" need="" to="" define="" an="" additional="" instance="" variable.="" task="" 3.="" update="" the="" simulator="" class.="" modify="" the="" simulate()="" method="" in="" the="" simulator="" class="" to="" work="" with="" the="" revised="" interface="" of="" parkinglot="" and="" the="" new="" peek()="" method="" in="" queue.="" in="" addition,="" implement="" the="" getincomingqueuesize()="" method="" of="" simulator="" using="" the="" size()="" method="" of="" queue.="" the="" getincomingqueuesize()="" is="" going="" to="" be="" used="" in="" the="" capacityoptimizer="" class="" (next="" task)="" to="" determine="" the="" size="" of="" the="" incoming="" queue="" after="" a="" simulation="" run.="" important!:="" to="" complete="" tasks="" 1="" and="" 3,="" please="" start="" with="" the="" starter="" code="" provided="" for="" a3="" and="" bring="" what="" you="" need="" from="" a2="" one="" method="" at="" a="" time.="" do="" not="" start="" with="" your="" a2="" implementation.="" several="" small="" changes="" have="" been="" made="" since="" a2;="" you="" would="" not="" want="" to="" get="" stuck="" due="" to="" these="" changes="" potentially="" going="" unnoticed.="" task="" 4.="" complete="" the="" capacityoptimizer="" class.="" implement="" the="" algorithm="" of="" figure="" 1.="" your="" implementation="" will="" go="" into="" the="" getoptimalnumberofspots(...)="" method="" of="" capacityoptimizer.="" this="" method="" writes="" out="" statistics="" to="" the="" standard="" output.="" the="" format="" of="" the="" re-="" ported="" statistics="" is="" straightforward="" and="" illustrated="" below.="" note="" that="" in="" our="" illustration,="" the="" results="" for="" lot="" sizes="" between="" 2="" and="" 13="" have="" been="" removed="" due="" to="" space.="" $="" java="" capacityoptimizer="" 3="===" setting="" lot="" capacity="" to:="" 1="===" simulation="" run="" 1="" (23ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 68="" simulation="" run="" 2="" (11ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 66="" simulation="" run="" 3="" (11ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 73="" simulation="" run="" 4="" (10ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 61="" simulation="" run="" 5="" (10ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 82="" simulation="" run="" 6="" (9ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 61="" simulation="" run="" 7="" (10ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 76="" simulation="" run="" 8="" (9ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 63="" simulation="" run="" 9="" (8ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 61="" simulation="" run="" 10="" (9ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 64="" [...="" results="" for="" lot="" sizes="" 2="" to="" 13="" not="" shown="" due="" to="" space="" ...]="===" setting="" lot="" capacity="" to:="" 14="===" simulation="" run="" 1="" (92ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 1="" simulation="" run="" 2="" (82ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 7="" simulation="" run="" 3="" (103ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 4="" simulation="" run="" 4="" (97ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 18="" simulation="" run="" 5="" (95ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 14="" simulation="" run="" 6="" (94ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 1="" simulation="" run="" 7="" (98ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="" 4="" simulation="" run="" 8="" (81ms);="" queue="" length="" at="" the="" end="" of="" simulation="" run:="">