CS 525, Simulation

Quiz 2, 16 February 2005

  1. A colleague of yours thinks that using trace data as simulation input makes it possible to avoid using contingent events. For example, in a simulation of table-occupancy rates at an n-table restaurant, customer arrival events are contingent on the most recent some tables free or all tables occupied event. However, if all customer arrivals are known before the simulation starts, the unseatable customers can be removed from the input, eliminating the contingency.

    Give and explain your opinion of your colleague's idea.

    Your colleague's idea comes up short. To be able to know when arriving customers should be turned away, you need to know when the current customers leave (or, more accurately, haven't left). Without knowing how many empty tables there are, you can't accurately turn away arriving customers.

    Although a few answers came close to the problem of unjustified data culling, most of the answers to this question were far more elaborate than they needed to be and, while not wrong, missed the point. Answers on these quizzes are usually one or two small, logical steps away from the question; if you find yourself giving answers that require elaborate leaps of reasoning, you should probably stop, calm down, and try again, starting from the problem.

  2. Deleting things - for example, events from an event list - is usually a pain: it may take a long time (that is, linear time) to find the event to be deleted, and it may be complicated to actually remove the event from the list.

    Briefly describe (no code) a scheme to avoid both these issues when deleting. For full credit your scheme should delete in constant time (at least theoretically).

    The easiest way to avoid the problems associated with deleting from the event list is to avoid deleting from the event list by keeping a second list of delete requests. As events are pulled off the event list, they can be compared to delete requests and tossed if there's a match. Because it's an unordered list that's only inserted into, searched, and deleted from, the delete list can be managed as a hash table, which provides (theoretical) constant-time access.

    "delete in constant time (at least theoretically)" was the clue here; the only common data structure with that property is some form of hash table. A few answers picked up on this, but didn't combine hash tables with the event list to give constant-time deletes (one answer replaced the event list with a hash table, which is difficult to do because the event list needs to maintain trigger-time order).

This page last modified on 22 February 2005.