Due: Thursday October 10th, 6:00 p.m. Weight: 13% of your mark in this course
The main purpose of this assignment is to give you experience with using modules and with manipulating pointers. It will also give you practise managing a reasonably large program. To reduce your workload, we will provide almost all of the code. To make the code easy to use, we have broken it down nicely into modules. You should be able to use each module after having read and understood only its interface; the internal details of the modules should be irrelevant.
This assignment will require you to do a lot of reading (both of this
handout and of the code we provide) and a lot of thinking to understand
the problem and what you are required to do.
You will undoubtedly need to ask questions; leave yourself time for that.
The actual writing of code should be a small part of doing the assignment.
It is impractical to simply build the street and then see how well it works. Instead, we want some way of predicting the outcome in advance. This is a perfect use for a computer simulation. In this assignment, you will build a simulation of one part of the street: a single crosswalk intersection and the people and cars that move through it. We will refer to the crosswalk, people, and cars as the crosswalk system.
The intersection to be simulated is a very simple one:
the street is one-way, so that cars only line up on one side of
the intersection
(for instance, the north side for a street that runs north-south);
and students can only pile up on one side
(for instance, on the east side of a north-south street).
The latter restriction is not realistic,
but it will make the program simpler.
We will examine more realistic simulations in assignment 3.
It is not always easy to decide what is relevant to the simulation (and should therefore be represented) and what is not. The number and placement of trees bordering the road is probably not relevant, whereas the number and placement of crosswalks surely is. Other things are less clear. For instance, does the make or model of the cars matter? Perhaps an older car is more likely to break down in the intersection, but perhaps not, if it is a Volvo rather than a Hyundai. Sometimes the decision on whether or not to model some aspect of the system depends on how detailed we want our simulation to be. For this assignment, we have decided on what is to be modeled and what is to be ignored.
As the program executes, variables will be changed in a way that models the behaviour of the crosswalk system. For instance, to simulate the movement of a car through the crosswalk, a car will be removed from the front of the queue data structure.
There must be some feedback from the simulation; it would be of little use if it only created and modified data structures. One way for the program to provide feedback is by printing out messages that trace what is happening as cars arrive, people cross the street, and so on. By looking at a trace of the program, one can discover interesting patterns. Another way to provide feedback is to gather and print out statistics, such as the average time a car had to wait before going through the crosswalk. Your program will provide both sorts of feedback.
The exact arrival times of people and cars at the crosswalks along St George Street is unpredictable. But what we can predict are the patterns of arrival. We might, for instance, predict that the probability of one or more cars arriving at a given time step is 0.2. We have provided code that uses a ``pseudo-random number generator'' to randomly decide things like how many cars arrive at a given point in time, based on probabilities like this 0.2. As a result, the simulation will be different each time it is run. It will also be different depending on how we set it up the crosswalk (for instance, the number of people who must arrive before the crosswalk opens). Such values are called parameters to the system. Your program will begin by reading in values for the parameters. By changing these inputs, the user can observe the effects of different parameter values on the system.
The course web page contains sample output showing
what a single run of your simulation program might look like.
Input to your program will determine:
At each time step, the following happens:
Your program's output should consist of
a trace of every event that occurs (if event tracing is turned on),
a report of the state of the system at every so many time steps
(as determined by the
state reporting frequency), and
the statistics calculated during the simulation.
Your program must print all of the information in the
example run on the course web page.
Some of the code for this has been provided for you.
The structure of this module has already been written, but you will have to fill in the body of procedure run. You may add other subprograms (that are called by run), but they should be hidden from the rest of the program -- i.e., they should not be exported outside the module.
This module has been completely written for you.
You may notice that some aspects of the program's design are not ideal. For instance, rather than having a specific CarQueue module, it would be better to have a general module that implements the abstract data type known as a queue. However, this is difficult to do nicely with modules. Simply importing the element type (as we do in the lecture notes) is not a general solution. One reason is that if the element type is something other than a basic type, comparisons between elements cannot be done with a simple ``='' test.
With modules, it is also awkward to create more than one instance of an ADT. (We would need this, for example, if we were to permit two sets of students to accumulate on the two sides of the road.) In the Student and Car modules, we are forced to work around this problem because we simply must have multiple students and cars. We can only do so by actually exporting the types that define a student and a car. This goes against the idea of information hiding.
Later in the term, we will learn about ``classes'', which will help
us solve some of these design problems.
Complete the program by writing procedure Simulate.run. Feel free to use additional, non-exported, subprograms to break down the problem. The program as a whole can now be run. Debug your code.
Now that you have the experience of using modules, you will go inside one, module StudentSet, and change some of the details:
Change the StudentSet module so that it uses this approach.
Because of the random aspects of the program, testing it creates some new challenges. For this reason, you are not required to produce complete and thorough testing of the whole program. However, you must still provide the marker with a convincing demonstration that the program as a whole works. Produce several annotated test runs that accomplish this. By carefully setting the parameters to the program, you can force interesting conditions to arise. Use the tracing features judiciously to help show that your program is correct.
This part of the assignment will give you an opportunity to (develop and) demonstrate your skills at testing.
Produce a complete and thorough test plan for your revised StudentSet module -- that is for all of the subprograms in the revised module. In order to execute the tests, you will have to write a small driver program. It can be somewhat general, or it can simply force one specific series of tests to be executed. Either approach is fine. Using your driver, produce annotated test runs. In addition, write up an explanation of your testing strategy.
You can devise your testing strategy and driver program before you have even begun to write your modified StudentSet module.
Pose one interesting question about the behaviour of the crosswalk system, and design an appropriate experiment to answer it. Explain your question, experiment, and results. Where appropriate, summarize your experimental results in a table or graph and refer to them in your answers.
This is meant to be a modest amount of work.
Use simple common sense when designing your experiment and analyzing your results.
Sophisticated statistics are not necessary.
Your writeup should be no more than a page long, including any tables or graphs.
Try to get the programming parts of your assignment finished early.
The computers are likely to be very crowded in the day or two before the
assignment is due. Extensions will not be granted just because
the printers are backed up; this is a normal situation. Get your
printouts well ahead of time.
It is your job, in your testing, to provide evidence that will convince the grader that your program works. If you hand in no test runs, or poor testing, you will get few or no marks for correctness of your program.
Below is the grading scheme that we currently expect to use.
It may be changed somewhat as the assignment unfolds, but should
give you an idea of where to focus your efforts.
part A 65 is Simulate.run and related code correct? 30 is the modified StudentSet code correct? 15 programming style 10 comments 10 part B: annotated test runs 5 part C: thorough testing of StudentSet 15 part D: experiment 10 overall quality of writing 5 TOTAL 100
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -no_navigation a1.
The translation was initiated by Diane Horton on Tue Sep 24 19:55:40 EDT 1996