CSCI 104代做、代写Data Structures、C++编程语言代写、代做c/c++代写

日期：2020-04-10 09:46

CSCI 104 - Spring 2020

CSCI 104 - Spring 2020

Data Structures and

Object Oriented Design

HOMEWORK 5

Due: (See assignments page )

Directory name in your github

repository for this homework (case

sensitive): hw5

Any skeleton code for this

assignment will be available in

homework_resources/hw5 .

Do a git pull in your

homework-resources repo.

Then copy the homeworkresources/hw5

folder into your

hw-username repo and use the

skeletons provided to start work

in that hw5 folder.

Objective

In this assignment we will review recursion,

traversals, and heaps.

Introductory Notes

In this assignment you will need to submit:

Your completed tree traversal

(expression solver)

files/implementations in

hw5/traversal/ folder as well as a

Makefile in that folder to compile

your code to an executable exprtester

by running make in that folder.

Your heap operations answers in a file

named hw5.pdf in your hwusername/hw5

folder

Your completed heap files in the

hw5/heaps/ folder. You should have

some test file and a Makefile that

can be used to compile a test

program named heap-test by

running make in that folder.

Your completed eventsim

files/implementations in

hw5/eventsim/ as well as a Makefile

in that folder to compile your code to

an executable eventsim by running

make in that folder.

1. Binary Tree Traversals

(30%)

It is common to represent expressions (e.g.

arithmetic) as a tree where internal nodes

(non-leafs) are operators and leaf nodes are

values (literals (constants) or variables). In

this problem you will use a tree to represent

arithmetic expressions and perform several

operations on the tree that require recursive

traversals of the tree.

We will provide an expression reader that

will construct the tree so that you can focus

on the various processing operations.

Expression Format

This problem will process expressions that

contain the 4 basic arithmetic operations:

+ , - , * , / , integer literals, and

parentheses: ( , ) .

As an early example, consider ( ( 4 / 3 )

+ 96 + 104 ) would produce a tree:

Every unique operation (+,-,,/) must be

enclosed by parenthesis () (i.e. there is no

implicit order of operations allowed). So we

cannot write ( 2 * 4 + 3 ) , but instead

must write ( ( 2 * 4 ) + 3 ) . In addition,

every operator, parenthesis, or literal **must

be separated by spaces*.

So that the tree will contain nodes of the

same same type, each node will store a

string. That string will contain the operator

(e.g. "+") or the integer literal (e.g. "96") but

as a string. (You will convert to an integer

when you validate and/or solve the

expressions.)

Our reader roughly implements the following

rules/grammar for expressions:

op := '+' | '-' | '*' | '/'

literal := string

expr := literal | '(' expr ')' | expr op

expr

root-expr := '(' expr ')'

Each internal node of the tree should be an

operator and each leaf should be a numeric

string literal (string representing a valid

integer including negative numbers). The

provided reader will read in an expression

from any provided input stream (our test

program uses stdin by default but you can

use I/O redirection to redirect the contents

of a file as input) and return a pointer to the

root node or throw std::runtime_error if

the grammar is not met.

Expression Operations

You will implement three operations on the

expression tree that require recursive

traversals:

Validating the Expression: While our

expression reader detects most

syntax errors, it does not validate the

each leaf node contains a string that

can be converted to a valid integer.

Your task is to write a recursive

traversal of the tree that will return a

bool indicating that entire expression

contains valid integers as leaves. That

is all it needs to check for (no other

forms of errors). Consider which form

of traversal is most appropriate for

this task (pre-, in-, post-order). A

prototype for this function is provided

in the skeleton and you may not

change it. However, you may add

helper function(s), if necessary.

Printing the Expression: You should

implement a recursive traversal of the

tree that converts the internal tree

representation back to a correct/valid

text based representation and output

it to a provided std::ostream .

Assuming the tree represents a valid

expression, the text expression you

output should be correct, such that it

could be provided as input in a

subsequent run and generate the

same tree. Consider which form of

traversal is most appropriate for this

task (pre-, in-, post-order). A

prototype for this function is provided

in the skeleton and you may not

change it. However, you may add

helper function(s), if necessary.

Evaluating the Expression: You

should implement a recursive

traversal of the tree that evaluates the

expression and returns the integer

result. You may assume the tree

represents a valid expression.

Consider which form of traversal is

most appropriate for this task (pre-,

in-, post-order). A prototype for this

function is provided in the skeleton

and you may not change it. However,

you may add helper function(s), if

necessary. (Note: If the expression

contains a divide-by-0, you do not

have to handle it specially. Just let it

fault.)

Testing

We have provided a test-driver application

that you can use to verify your functions. It

will call our reader function and return the

pointer to the root of the tree or throw

std::runtime_error . It will then call your

functions to validate, print, and solve the

expression.

Other Requirements

You must use recursion to process

each node but can use a loop to

iterate through children.

You may not modify the signatures of

the functions we provide but may add

helper functions.

You should only edit expr-ops.cpp .

2. Heap Operations (10%)

You will answer several questions about

Heaps in this problem.

For this problem, you can choose to draw

this by hand and scan it (and submit as a

JPG or PDF), or to use some graphics

software (and produce a JPG or PDF), or

draw it using ASCII art (this may be a lot of

work). Name your file hw5.pdf .

Part a (3%)

Indicate whether the following arrays are

valid binary Min Heaps (assuming the root is

at index 0 of the array). For each array

which is not, indicate which child(ren)

violate the heap property (i.e. are out of

place).

[6, 2, 26, 24, 22, 20, 48, 46, 44]

[2, 16, 4, 50, 18, 5, 28, 71]

[2, 16, 4, 10, 18, 26, 28, 11]

Part b (5%)

Draw the tree representation of the following

binary Min Heap in its initial configuration,

and after each operation. Make sure to

clearly indicate each of your final answers.

This is a sequence of operations, meaning

one affects the next.

Initial Configuration: [2, 4, 6, 8, 10, 12,

14, 16]

Insert 3

Pop (top element)

Pop (top element)

Insert 5

Part c (2%)

Given the following array, perform the build

heap (make heap process) to convert the

array into a valid min-heap. Show the array

contents after each step. More specifically,

show what index you are calling

heapify/trickle-down on (e.g. heapify(8) )

and the entire array contents after each call.

[38, 8, 29, 15, 53, 20, 24, 18, 7 ]

3. Heaps (25%)

Build your own m-ary Heap class whose

public definition and skeleton code are

provided in the hw5 folder of the homeworkresources

with the interface given below.

Rather than specifying a specific type of

heap (Min- or Max-Heap) we will pass in a

PComparator (P for Priority) object so that if

the comparator object functor implements a

less-than check then we will have a minheap.

If the PComparator object functor

implements a greater-than check we will

have a max-heap.

template template <typename typename T, typename typename PComparator = std::less<T> >

class class Heap Heap

{

public public:

/// Constructs an m-ary heap for any m >= 2

Heap(int m, PComparator c = PComparator() );

// other stuff

};

You may use the STL vector<T> container

if you wish. You should of course NOT use

the STL priority_queue class or

make_heap , push_heap , etc. algorithms.

You may add private helpers, if you like.

As you implement the heapify() process

when popping the heap, recall that a parent

would swap with its best child if the best

child is "better" than the parent. However,

what if we have a tie for the best child?

Choosing either to swap with is technically

fine, but for the sake of the next homework

problem where you will use the heap, let us

choose the left-most of the children tied for

the "best" (first one encountered if you are

iterating in order).

Notice we can provide a default template

type for the Comparator so that the client

doesn't have to specify it if they are happy

with the std::less (i.e. which assumes a

built-in operator< is available for type T

and calls it).

Notice the constructor also provides a

default value for the Comparator which is a

default-constructed Comparator. Default

parameter values will be used if the client

does not supply them. Also if a default

parameter is used then all parameters after

it must also have default values (i.e. default

parameters must be at the end of the

declaration). The last thing to note is you

only supply the default value in the

declaration of the function. When you

define the function (i.e. write the

implementation below) you would not

specify the default value again but just

leave the argument types/names. For

example, when implementing the function

you'd just define:

template template <typename typename T, typename typename PComparator>

Heap<T,PComparator>::Heap(int m, PComparator c /* Don't specify the default value here, only above */

// Your code here

So with these defaults in place, the client

that wants a min-heap with a type that has

a less-than operator need only write:

Heap<string> h1(2); // std::less<string> is used as the

// default template type for Comparator

// and std::less<string>() (i.e. the default

// constructor) will be the comparator object

// comparator object created by the constructor

or the client who wants a some custom

method of comparison so that they can

implement a max-heap or some other

alternative using a custom comparator can

write:

ObjAComparator c1( /* some arguments as desired */ );

Heap<ObjA, ObjAComparator> h1(2, c1);

We will provide a very basic set of tests for

the heap a few days after releasing the

homework. However, you should also test

your heap either using gtest or another test

driver program. Be sure it works as a minheap

and as a max-heap using different

comparators. For reference if your type T

has a < operator, then C++ defines a less

functor which will compare the type T

items using the operator<() . Similar there

is a greater functor already defined by

C++ that will compare using the operator>

() . They are defined in the functional

header ( #include <functional> ) and you

can look up their documentation online for

further information. This is meant to save

you time writing functors for types that can

easily be compared using built in

comparison operators.

The tests you write will not be graded but

should give you confidence that when we

test your heap it will work. Also, you will

need to use your heap in the next problem

and you don't want to be debugging two

pieces of code at once, but instead have

confidence that your heap is working and

any bugs in problem 4 are only due to

problem 4 code.

4. Event Simulator (Heap

Application) (35%)

In this problem we will perform a discrete

event simulation which requires use of a

priority queue to simulate traffic in a grid of

streets. Event simulations schedule events

and always process the next event in time

order. The priority queue is necessary to

track and ensure we choose the next,

appropriate event to be processed. Events

will each contain a time stamp for when

they occur in our "simulated time" and we

will always want to choose to process

events in order of simulated time. However,

processing events may lead to new events

being added (some may have timestamps

that are sooner that events already being

stored and some may have timestamps that

are later), thus requiring a priority queue to

ensure we always process the next event in

simulated time order.

The context for our simulation will be traffic

flow. Suppose you are given a grid-like

street layout of an urban area with a set of

n eastbound (row) streets {r0, r2, ..., rn-1}

and m southbound thoroughfares {c0, c2,

..., cm-1 }. Each thoroughfare has a

particular capacity, Cri or Cci loosely

representing the number of vehicles they

can transport at full speed per unit of time (if

more vehicles use the street than its

capacity, their travel time on that segment

will increase).

1 2 <-- column street capacities

====================

1 | + - +

| | |

1 | + - +

| | |

1 | + - T (Terminal location)

^ |

|

row street capacities

We will simulate rush hour where vehicles

start from a particular vertex of the grid (say

a parking garage at an intersection) at a

specified time and are all traveling to a

common destination (e.g. the freeway

entrance) at the BOTTOM-RIGHT (i.e.

vertex rn-1,cm-1 ). At each intersection

(vertex) vehicles will choose to go either

south (down a column) or east (along a row)

by choosing the fastest of the neighboring

row- or column- street segment (this is a

local decision based on the current fastest

next-segment, though this may not lead to

an optimal choice for a fastest, overall path).

We will assume each street segment is 1

unit of distance. To compute the time that a

car will require to travel on a particular street

segment we will use the number of cars

currently on that street segment. More

precisely, if there are num_vehicles cars

ALREADY on a segment currently and that

street has a capacity of street_capacity ,

then the time required for the next car to

traverse that segment is given by:

time = max(1, (1+num_vehicles) /

street_capacity) * SCALE_FACTOR

Initially, all street segments have 0 cars. The

SCALE_FACTOR is just there so we can use

integers rather than doubles. In our case,

SCALE_FACTOR = 1000 so that the minimum

time to traverse a street segment is 1000.

Other events such as new vehicles entering

the street system may occur at anytime.

Special note for choosing when both

directions will require the same amount

of time: If a vehicle may choose either

direction and their time/delay is equal, the

vehicle MUST choose the opposite

direction as the LAST vehicle that passed

through that intersection that encountered

equal times in both directions (starting by

choosing the row-wise street for the first

vehicle at this intersection that encounters

equal times). (Normally we could just

choose randomly but we want the same

results for all simulations and so define this

deterministic approach.)

The Events

The simulation will contain 4 kinds of events

(each derived from a base Event class).

Vehicle Add Event: Adds a new

vehicle to the simulation at the

specified time starting from the given

intersection. Unless the vehicle is

added to the terminal location directly

(in which case it can be completed

and removed from the simulation

immediately), the processing of this

event should determine which street

segment to choose (based on the

rules defined elsewhere) and create a

new Arrival event for the next

intersection.

Vehicle Arrival Event: Indicates a

given vehicle has successfully

traversed a specific street segment

and arrived at the next intersection at

a particular time. If the vehicle has

reached the terminal location, it can

be completed and removed from the

simualtion. Otherwise, it should

determine which street segment to

choose (based on the rules defined

elsewhere) and schedule a new Arrival

event for the next intersection.

Set/Clear Blockage Event: Indicates

a given street segment is unblocked

(or blocked) and can(not) be

traversed. One event will be used to

block the street segment and a

subsequent event would be used to

unblock the segment. Blocking a

street segment only means that NO

vehicles arriving at that intersection

after the time of the blockage may

enter. Vehicles already on that

segment may obviously continue

traversing that segment. Also,

because we are not including a

method to stall cars at an intersection

once they have arrive there, it is

considered INVALID/UNDEFINED

behavior to:

Block a row segment on the

bottom row

Block a column segment on the

right-most column

Block both the row and column

segment from an interior

intersection at the same time

Blocking an already blocked segment

and unblocking an already unblocked

segment should do nothing,

This means we will not do that in our

testing nor should you do that in your

testing. If it is done, the results of the

simulation can legally be anything (i.e.

undefined behavior).

Monitor Event: Every SCALE_FACTOR

time units ah monitor event should be

processed (and schedule the next

Monitor event) to print the state of the

street grid to the screen, periodically.

We have provided a member function

of the StreetGrid class to do this for

you and your monitor event can

simply call that member function.

Note that processing events (especially Add

and Arrival events) will cause another event

to be generated that should be scheduled.

These new events should be returned in the

EventList of the process function and

scheduled into the priority queue. While

currently only one new event will be

generated by processing the current event,

we could envision additions to this

simulation where one event spawns multiple

more. Thus we chose a list of events as the

return value and not just a single event

because a list can easily handle the case of

0, 1, or many events being generated during

processing of another.

The Simulation

To review, we will simulate the traffic system

through a discrete-event based simulation.

By storing events that each contain a time

stamp for when that event will occur, we

can use a priority queue to get the next

event to be processed. Discrete-event

simulation essentially passes "simulated"

time by simply removing the next (timeordered)

event from the priority queue.

Pseudocode for the main simulation

algorithm is shown below:

Listing 1:

PQ = new new PriorityQueue;

// Read input file for configuration and initial events

// Add all initial events

while while(!PQ.empty())

e = PQ.top();

PQ.pop();

new_events = process(e);

for for n in new_events

PQ.push(e);

The Input File

We will use an input file to specify the

configuration of the grid as well as the userspecified

events (adding a vehicle and

setting/clearing a street blockage).

The format of the file will be as follows. The

first 2 lines will contain the number of rows

(followed by their capacities) and the

number of columns (followed by their

capacities).

<n-rows> <r0_capacity> <r1_capacity> ... <rn-1_capacity>

<m-cols> <c0_capacity> <c1_capacity> ... <cm-1_capacity>

After the first 2 lines there will any number

of remaining lines consisting of either

vehicle addition events or street blockage

events. A vehicle addition event has the

format:

A <unique-id> <start-timestamp> <start-row> <start-col>

A street blockage event has the format:

B <start-timestamp> <row> <col> R|C 1|0

In the above specification R indicates that

the row segment starting from row,col is

being blocked/unblocked and C indicates

that the column segment starting from

row,col is being blocked/unblocked. For

the 1|0 , 1 indicates the segment is

blocked and 0 indicates unblocked.

Let us look at an example. Consider the

following file:

3 1 1 1

2 1 2

B 500 1 0 C 1

B 2500 1 0 C 0

A a2 1002 0 0

A a1 1001 0 0

A b1 3750 1 1

The first 2 lines indicate 3 rows x 2 columns.

All the row-wise streets and the left-most

column street have capacity of 1 vehicle

while the right-most column street has a

capacity of 2 vehicles. Our provided monitor

function would show the following at time 0

for this configuration. the row and column

headers indicate the capacity of the 3 row

strees and 4 column streets. The +

indicates an intersection. The 0 s indicate

that 0 vehicles are on each street segment.

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0 0

1 | + 0 +

|

Next in the input file we have blockage

events for the column street segment

originating from row 1, column 0. It will be

blocked at time 500 and unblocked at time

2500. Three vehicle additions are also

scheduled in the following 3 lines: vehicle

a1 is added at time 1001 at intersection

0,0 . Vehicle a2 should be added at time

1002 also at intersection 0,0 . Finally a

third vehicle, b1 is scheduled to start from

intersection 1,1 at time 3750 . Notice that

the order the events appear does not matter

in the configuration file as the priority queue

will ensure we process them in simulatedtime

order.

Completion and Expected Results

Your simulation should run until no more

events exist in the priority queue and all

vehicles that were to be added by the

configuration file have arrived at the terminal

location. Our monitor event will stop

scheduling future monitor events once all

vehicles have arrived and thus the priority

queue should go empty at that point. Once

complete, you should create the specified

output file (given on the command line) and

ouptut the arrival times of each vehicle

(along with its ID) ordered from earliest to

latest arriving vehicle.

4001 a1

4002 a2

5250 b1

Code Structure

Vehicle struct ( vehicle.h ):

[COMPLETED] Models a vehicle and

relevant data. Note since a vehicle

only stores what intersection it WAS

at we need to know if it chose to go

down the row street or column street.

The rowDir member tracks this

decision (true = on a row segment,

false = on a column segment) so that

we know how to update occupancies,

etc. when processing Arrival events.

Event class ( event.h ):

[COMPLETED] Base class modeling

an event. All events have a timestamp

when they should be processed. Each

derived event should implement the

process() function which will

process the event and return a list of

new Event(s) to be scheduled for the

future. Each derived event will also

return a subPriority to break ties

between events that have the same

time stamp so that certain events are

processed before others if their

timestamp matches. Just as smaller

timestamps should be handled first, if

two events are tied, the one with the

smaller subpriority should be

processed first.

AddEvent, ArrivalEvent,

BlockageEvent, MonitorEvent

classes ( derived_events.h/cpp ):

[COMPLETED] Implements the

derived event types. Several

process() implementations simply

call corresponding StreetGrid public

functions to carryout the desired task.

You will be responsible for

implementing those StreetGrid

functions.

Input reader functions

( input_reader.h/cpp ):

[COMPLETED] Read in the

configuration file to fill in data

structures necessary to create the

StreetGrid object and fill the priority

queue with initial events (vehicle

additions and blockages).

Heap<T> class ( heap.h ): **You should

copy your completed heap.h file from

the hw5/heaps folder to your

hw5/eventsim folder so it may be

used in this problem.

StreetGrid class ( streetgrid.h/cpp ):

[TO BE FINISHED] Models the street

grid and tracks vehicles, street

capacities, street occupancies,

blockages, and all other data

necessary to determine the state and

operation of the simulation. There are

several public member function you

must implement and one private

member function

( shouldChooseRow() ) that we

recommend you write to abstract the

task of determining whether a vehicle

at a certain intersection should

choose the row or column street. We

have provided some simple accessor

member functions and a set of

required data members. You will need

to add more data members to

correctly track and store other

relevant data such as street

occupancy, blockages, etc.

Note: There are a few ways to

model the street segments:

One approach is to

consider the segments as

two separate 2D arrays.

There are n x (m-1) row

segments and (n-1) x m

column segments.

Alternatively you can think

of the street segments as

a 3D array (rows x

columns x 2 street

segments [1 for row and 1

for column]). In this

model, the top two

dimensions represent an

intersection and the last

(lower) dimension

represents the two

directions of street

segments. Note however,

there are no column

segments originating from

the last row and no row

segments origninating

from the last column.

Be sure to complete the

specified member functions

according to their

documentation in the header

file. Be sure to throw the

exceptions specified in the

documentation.

main() function ( eventsim ): [TO BE

FINISHED] Declares functors for the

priority queue (your Heap<T> class to

use) and implements the main

simulation logic (see Listing 1). This is

where you should use your Heap as a

priority queue to store Events, pull out

the next event, process it, and

schedule any new events that the

processing generates. You will need

to complete the Comparator functor

your heap can use to compare to

Event* pointers. Be sure to clean up

Events when appropriate as they

are/should be dynamically allocated.

Finally, be sure to output the ordered,

completed vehicles to the specified

output file by calling

streets.outputCompletedVehicles()

once the simulation ends.

Notes and Requirements

You should write a Makefile that

correctly produces an executable

eventsim .

We expect your executable will be run

with command line arguments for the

input file and output file. Example:

./eventsim events0.in events0.out

The order of processing events

scheduled for the same time stamp

AND sub-priority is undefined. That

means we will not expect a certain

ordering if two events have the same

timestamp and sub-priority. So no

need to worry about this case.

Be sure to handle the selection of

which segment to use when a vehicle

at an intersection can use either the

row or column street segment and

both have equal time/delay. We

outline this above.

You should not change code provided

except where indicated in the

comments of the skeleton code.

There should be no memory errors or

leaks.

Example Run

Let us look at a sample run. Again, assume

the input file is events0.in which contains:

3 1 1 1

2 1 2

B 500 1 0 C 1

B 2500 1 0 C 0

A a2 1002 0 0

A a1 1001 0 0

A b1 3750 1 1

Then the program is run from the command

line as:

$ ./eventsim events0.in events0.out

We schedule monitor events every

SCALE_FACTOR time units.

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0 0

1 | + 0 +

|

Dequeued event at time = 500,2

BlockageEvent::process()

Blocking col at 1,0

Dequeued event at time = 1000,0

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0B 0

1 | + 0 +

|

Adding event for time=2000,0

Here we see the initial state at time 0 (called

at the end of the StreetGrid constructor)

and then the first 2 events: The blockage of

the column segment originating from 1,0

and the next monitor event at time 1000

(which then schedules the next monitor

event for 2000 ).

Dequeued event at time = 1001,1

StreetGrid::AddVehicle - vehicle a1 now at 0,0

StreetGrid::AddVehicle - vehicle a1 will go row = 1000

Adding event for time=2001,3

Dequeued event at time = 1002,1

StreetGrid::AddVehicle - vehicle a2 now at 0,0

StreetGrid::AddVehicle - vehicle a2 will go col = 1000

Adding event for time=2002,3

Dequeued event at time = 2000,0

State:

1 2

====================

1 | + 1 +

| 1 0

1 | + 0 +

| 0B 0

1 | + 0 +

|

Adding event for time=3000,0

Next we see the first two vehicles added.

Vehicle a1 would see equal time options

for the row and column street segments

originating from 0,0 and thus the

requirement was that when times were

equal each vehicle should choose the

opposite of the previous vehicle that used

that intersection with equal row and column

stree times, starting with the row segment

for the first vehicle (i.e. this case). Thus it will

take a1 1000 time units to get to

intersection 0,1 and thus a new arrival event

is scheduled for 2001 .

When the second vehicle is added 1 time

unit later it will choose the column segment

because the row segment time would be

SCALE_FACTOR*((1 + segment_occupancy) /

street_capacity) = 1000*((1 + 1)/1) =

2000 . The column segment time is only

1000*((1 + 0)/1) = 1000 . By choosing

the smaller, a2 will schedule an arrival

event for 2002 at intersection 1,0.

Dequeued event at time = 2001,3

StreetGrid::processArrival - vehicle a1 now at 0,1

StreetGrid::processArrival - vehicle a1 will go col = 1000

Adding event for time=3001,3

Dequeued event at time = 2002,3

StreetGrid::processArrival - vehicle a2 now at 1,0

StreetGrid::processArrival - vehicle a2 will go row = 1000

Adding event for time=3002,3

Dequeued event at time = 2500,2

BlockageEvent::process()

Unblocking col at 1,0

Dequeued event at time = 3000,0

State:

1 2

====================

1 | + 0 +

| 0 1

1 | + 1 +

| 0 0

1 | + 0 +

|

Adding event for time=4000,0

In the above section, vehicle a1 arrives at

intersection 0,1 at time 2001 and can only

use the column segment (since we are on

the eastern boundary) which will take 1000

time units and so we schedule an arrival

event for 3001 . a2 arrives at intersection

1,0 at time 2002 and, due to the blockage, it

must use the row segment and go to 1,1.

That takes 1000 time units. and so an arrival

event is scheduled for 3002 . At time 2500,

the column segment from 1,0 is unblocked.

And at time 3000 the next monitor event is

processed.

Dequeued event at time = 3001,3

StreetGrid::processArrival - vehicle a1 now at 1,1

StreetGrid::processArrival - vehicle a1 will go col = 1000

Adding event for time=4001,3

Dequeued event at time = 3002,3

StreetGrid::processArrival - vehicle a2 now at 1,1

StreetGrid::processArrival - vehicle a2 will go col = 1000

Adding event for time=4002,3

Dequeued event at time = 3750,1

StreetGrid::AddVehicle - vehicle b1 now at 1,1

StreetGrid::AddVehicle - vehicle b1 will go col = 1500

Adding event for time=5250,3

Dequeued event at time = 4000,0

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0 3

1 | + 0 +

|

Adding event for time=5000,0

At time 3001, a1 arrives at 1,1 and can

only travel the column segment which will

take 1000*max( 1, ((1+0)/2) ) = 1000

time units. a2 arrives at 1,1 and can only

travel the column segment. Since a1 is

already on that segment a2 will require

1000*max( 1, ((1+1)/2) ) = 1000 time

units. b1 is added at 3750 and can only

use the column segment. This will require

1000*max( 1, ((1+2)/2) ) = 1500 time

units. These events will be scheduled and a

monitor event will take place at 4000 .

Dequeued event at time = 4001,3

StreetGrid::processArrival - vehicle a1 now at 2,1

StreetGrid::processArrival - At terminal location

Dequeued event at time = 4002,3

StreetGrid::processArrival - vehicle a2 now at 2,1

StreetGrid::processArrival - At terminal location

Dequeued event at time = 5000,0

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0 1

1 | + 0 +

|

Adding event for time=6000,0

Dequeued event at time = 5250,3

StreetGrid::processArrival - vehicle b1 now at 2,1

StreetGrid::processArrival - At terminal location

Dequeued event at time = 6000,0

State:

1 2

====================

1 | + 0 +

| 0 0

1 | + 0 +

| 0 0

1 | + 0 +

|

Here we see the arrivals of the vehicles at

the terminal location at the given times.

Once the monitor event at 6000 takes place

we will see that all expected vehicles have

arrived and thus NOT schedule another

monitor event. This will make the priority

queue go empty and the simulation to end.

At the point we write the final arrival times of

each vehicle in time order to events0.out :

4001 a1

4002 a2

5250 b1

Assignment Checklist

Directory name for this homework

(case sensitive): hw5

This directory should be in your

hw-username repository

This directory needs its own

README.md file briefly describing

your work.

Double check the FAQ page for any

updates to requirements or

clarifications that might apply to your

implementation.

A README.md and your completed

hw5.pdf in the hw-username/hw5

folder.

Your completed traversal

files/implementations in traversal/

as well as a Makefile in that folder to

compile your code to an executable

expr-tester .

Your completed heap

files/implementations in heaps/ as

well as a Makefile in that folder to

compile your code to an executable

heap-test .

Your completed eventsim

files/implementations in eventsim/ as

well as a Makefile in that folder to

compile your code to an executable

eventsim .

You can use the submission link here.

WAIT! You aren't done yet. Complete the

last section below to ensure you've

committed all your code.

Commit then Re-clone your

Repository

Be sure to add, commit, and push your

code in your hw5 directory to your hw-uscusername

repository. Now double-check

what you've committed, by following the

directions below (failure to do so may result

in point deductions):

1. Please make sure you have read and

understood the submission

instructions.

2. Go to your home directory: $ cd ~

3. Create a verify directory: $ mkdir

verify

4. Go into that directory: $ cd verify

5. Clone your hw-username repo: $ git

clone git@github.com:usc-csci104-

spring2020/hw-username.git

6. Go into your hw5 folder $ cd hwusername/hw5

7. Recompile and rerun your programs

and tests to ensure that what you

submitted works.

8. Go to the Assignments page and click

on the submission link.

9. Find your full commit SHA (not just

the 7 digit summary) and paste the full

commit SHA into the textbox on the

submission page.

10. Click Submit via Github

11. Click Check My Submission to

ensure what you are submitting

compiles and passes any basic tests

we have provided.

USC > UCLA Muahaha