introduction |
objectives |
overview |
specifications |
written work
resources |
hints and tips |
submission |
files |
announcements
Residents of Port Townsend find the ferry a convenient way to get to Seattle for work, classes at UW, or just for fun. However, budget-conscious public officials want to cut ferry service, saying it is underutilized and that people would be happier driving the whole way anyway. At the same time, a citizen group called SAVE OUR FERRIES is lobbying for increased service, pointing to ever-growing demand.
Both groups come to your dot-com computer consulting company for help. They want you to make a computer model of the system, so that they can predict the effect many variables: the effect of more frequent (or less frequent) ferry departures; how many cars and passengers could be served, under different models of how often the cars arrive; how different ferry sizes would affect the situation; how long cars would have to wait to board, etc.
Your plan is to write one program that is capable of modeling (i.e. simulating) the ferry system. Then you can run the program with different sets of data, record the results, and collect fees from both groups.
As with past homeworks, a major part of this assignment is understanding provided code and specifications well, so take the time to read both closely and thoroughly. Even with that, you might find that the code you need to write is longer and more complicated than for past assignments. But of course, you're more experienced now, too, and you've learned to use tools like the debugger to help find problems (right?). There will be quite a bit to turn in during the first week.
The following concepts and technical knowledge are the focus of this homework:
You will complete a partially implemented project which is an outline for the ferry simulation.
The basic operation of the simulation is as follows: The ferries have a given capacity for passengers and cars. The ferry arrives at a certain time, and then cars go aboard, until it is full or until its scheduled departure time. Cars can arrive at the ferry dock at any time, e.g. before the ferry arrives. They get in line to purchase tickets and are served on a first-come, first-served basis. When a car gets to the head of the ticketing line, it pays a fare based on the number of passengers in the car. The operation of paying fare consumes a small amount of time, which is taken into account in the simulation. After ticketing is completed, the car enters a second line in the ferry boarding area, where the cars wait for the next available ferry. Run the sample program to make sure you understand how the two car lines and ferry work together in the simulation.
We provide a simple, graphical visualization of this simulation that shows cars lining up in the ticketing and boarding lines, as well as the ferry. You are required to make only minor modifications to it for this homework, but looking at the code will help you prepare for the next homework, which will also involve graphics.
The simulation uses two data files, which specify the ferry schedule and when cars arrive and with how many passengers. For simplicity, time in the simulation is represented by an integer which starts at 0 (the beginning of the simulation's world) and goes up as time passes by 1 per minute.
ferry.txt - contains only one line with four integers, giving the time of the first ferry's arrival, the time between consecutive arrivals (which determines the ferry schedule), the number of cars the ferry can hold, and the number of passengers it can hold
cars.txt - many lines long, with each line specifying the arrival of one car; each line consists of two integers, giving the time of the car's arrival and number of passengers inside (not including the driver)
As in the previous homework, understanding the provided code and what it implies about the sections of code you must fill in will be crucial to the correct, timely completion of the project. During the week prior to the final due date for the programming part of this project, you will be asked to submit several items, including a static call graph of the whole program as you would expect it to look when the program is completed.
As the simulation runs, it should display statistics like the total number of ferry departures, cars, passengers; average number of passengers per car; average wait in each queue, etc.
Under files below, you are given all of the files needed to build a program that works just like the sample executable, but some of them are incomplete. This homework has two parts. In addition to work specified below under written work, your programming tasks for Part I are as follows:
Your programming tasks for Part II are as follows:
As usual, start by spending some time familiarizing yourself with the sample executable, then make sure to study all of the provided code. As you study, make notes that will help you draw the static call graph to be submitted in Part I.
class CarQueue and driver
You are given a starting version of the header file for a queue of Car pointers, carqueue.h. Complete the header and implement the queue as a linked list.
Your driver for CarQueue should be called driver.cpp and define a main function whose sole purpose is to comprehensively test the class by systematically invoking each public method. Your driver should instantiate CarQueue, then repeatedly enqueue and dequeue items from it to demonstrate proper FIFO ordering. The driver should test boundary conditions (such as queue empty) and test whether large numbers of cars can be enqueued. You should not need to read car data from a file. Simply instantiate Car objects directly inside main.
running the debugger on your driver
With your Part I paper submission, you are required to include a printout of a screen snapshot showing the debugger stopped at a breakpoint somewhere in driver.cpp. Run your driver in debug mode, and place a breakpoint just after dequeue method call. Using the Variables debugger window, examine the Car * that the dequeue returned and the Car member variable that contains the number of passengers in this car (Make sure this is visible on the screen.). Then take a screen snapshot, print it, put your name, student number, and section on it, then submit the printout with your other Part I materials.
With Windows, you can capture and print a snapshot of the screen as follows:
If you are not using Windows, you should submit a screen snapshot using the debugger included with your development environment or run the MSVC debugger on your code in MGH lab and submit a Windows snapshot.
(Macintosh users: Press Apple/Command-Shift-3 to save a screen snapshot to your default hard drive. You should hear the "shclick" of a camera shutter when you do this, if you have your sound volume up.)
class FerrySimEventList
You are given a starting version of the header file for an event list, ferrysimeventlist.h. An instance of this class holds the events which will take place in the simulation, sorted in order by the time when they will occur and by event type (see method FerrySimEvent::compare). The front of the list always contains the next event which will occur; the tail of the list has the event which is furthest out in time. Implement this class using a statically allocated array.
An enumeration (using enum) in the related class FerrySimEvent (see ferrysimevent.h) lists several suggested types of events. Study this list and the corresponding methods in class FerrySim carefully until you understand what each type of event is, and what kind of processing has to take place when it occurs. This will help you to understand how the simulation progresses.
GP142 graphics package
The visualization for this simulation was written using the C++ version of the GP142 graphics library (see ferrysimview.h,cpp). You should familiarize yourself with GP142 enough to understand how FerrySimView's methods work in preparation for modifying class FerrySimView (see below). For web documentation on GP142, see under resources below.
important note: In order for graphics to work, when you create an MSVC project for this homework, you must choose Win32 Application, not the usual Win32 Console Application.
class FerrySim
FerrySim is the heart of the simulation. It contains the overall framework, including instances of the queue and event list classes. It also has a very important method called "run", which drives the simulation forward in time. Most of this code is given to you; study it carefully. You may have to make some modifications, depending on exactly how you implement some of the other classes.
You also need to modify it to generate and compute the simulation statistics that are required. These statistics are important and might be helpful as you test and debug your CarQueue and FerrySimEventList implementations, but they can be added in the final stages of your work, after you have more basic aspects of the program fully operational. By adding private member variables and public methods, modify FerrySim so that it computes the following simulation run statistics:
class FerrySimView
To display the above statistics, you will have to modify FerrySimView, adding some code that uses GP142. (Start by studying how the given version of this class displays the statistics which are already implemented.)
The help further familiarize you with GP142 (which you will use extensively in Homework 5), you are also required to make a change to the on-screen representation of the ferry (currently just a rectangle). The change does not have to be significant. Minimally, simply change the shape and color of the figure. You're welcome to make further changes, e.g. adding windows, smokestacks, etc., but they are by no means required.
additional requirements
To save time, you may use or adapt code from the textbook or lecture slides for the queue and event list classes. However, if you do, you are required to give credit by citing your sources in the comments in your code.
As usual, we expect you to always be considering invariants, and you should use assertions throughout your code.
Finally, remember that the only code files you are allowed to modify are the following:
static call graph (for Part I)
Your call graph should include all of the functions and methods that can be called, starting from main, when the program is complete. (My main, we mean the given main.cpp's main definition, not your driver.cpp's main definition.) As before, write only function/method names on the graph, omitting parameter lists. For a method name, remember to include the class name using :: notation, e.g. "FerrySim::run". Do not include implicit constructor invocations---your graph will be cluttered enough without them.
Your call graph will end up being rather large and complicated, so we strongly suggest you write on a large sheet of paper and start with main in the center. Write small but neatly, fold your call graph into a reasonable size (e.g. 8.5 x 11 inches) for submission, and make sure your name, student number, and section are written in a visible location. Before you submit your call graph, make sure to make a photocopy for your own use as you work on Part II.
project report (for both Part I and Part II)
In addition to your turn-in receipt print-out, you are required to submit the following on paper with each of the two parts' submissions.
It may be that your project does not meet the specifications given above. Write a short statement that either says you are in full compliance with the requirements, or lists the ways in which you are not (things that don't work, etc.).
You may decide that the program you turn in is not ideal in some respects. If your boss or fellow programmers were looking at it, what do you think they would find to like or dislike? Write a short paragraph evaluating the project. You could focus on the way it's designed and programmed, or focus on what usefulness the program has. You are required to do more than just make observations about the code or program design. You must explain why some aspect of the program is good/bad or interesting.
Write a statement of acknowledgements. If you took code from anywhere (except what the assignment gives you directly), say where you got it from and who the original author is. You must do this even if you modified the code considerably. If you received help on the assignment from anyone other than course staff (TA, instructors, consultants), please list the name of the person and the extent of their help.
Your answers may be handwritten if they are 100% legible. If your TA can't read it easily, he or she may require you to resubmit it word-processed. Your answers must be on a separate sheet of paper, and not embedded in comments in the program. Please write your name, student number, and section on the page.
As always, be sure to read the official homework submission policy, linked on the course web on the Homework page. For each of the two parts, you will have to submit your work (1) via the web using the page linked below and (2) on paper.
Your web turn-in for Part I should consist of the files listed below. The form will not accept any other files.
Your web turn-in for Part II should consist of the files listed below. The form will not accept any other files.
You should not need to modify carqueue.h and carqueue.cpp from your Part I turn-in.
Your paper submission for each part should consist of the following:
As stated on the official homework submission policy page, all parts and pages of your paper submission must be stapled together and sealed in a large envelope. (Don't expect the TA to have a stapler in section, either!) You can lose points for not following these instructions (crazy, but true!) For this homework, you will submit your paper submissions in quiz section on the due dates at the top of this page.
hw4.exe (PC, Windows)
If any clarifications or changes need to be made for this homework, they will be posted to the cse143-announce e-mail list and linked here.
not clarifications or changes, per se, but other relevant postings:
Save paper. Read documents on the web and, if you must print, print two-sided. Recycle this when you're done.