BU CAS CS 113
Introduction to Computer Science II with Intensive C

Spring 1996

Assignment 6, due Tuesday March 19 at 2PM

In this assignment you will use linked lists to model a real-world simulation. You will first develop linked list routines, and then use these as part of your simulation program.

Your source files are to be electronically submitted by using the submit program on csa. The code you submit should conform with the program assignment guidelines.

The assignment consists of two source files (a6p1.c and a6p2.c) that should be compiled and linked together to make your simulator main program. In addition, you will need to create a header file a6.h that contains the structure type definitions and function prototypes needed for your program. This header file must be included in both a6p1.c and a6p2.c.

Third Harbor Tunnel Toll Booth Simulation

Suppose that Boston's new harbor tunnel has only three toll booths, and we would like to simulate the traffic jams caused by toll-taking. For each car in this simulation we are given:
  1. an arrival time t1
  2. the time needed to process the toll t2
If at time t1 a toll booth is free, then the arriving car can be processed immediately, and the car leaves the toll booth at time t1+t2. The total time spent waiting at the toll booths is t2.

However, it is possible that none of the toll booths is free; they are all servicing cars that have arrived previously. In that case there is a line of one or more cars at each toll booth. The new car proceeds to the shortest line and waits until all cars preceding it in line have paid their tolls. At that time the new car can pay its toll and pass through the tunnel. The customer leaves the toll at t2 time units after reaching the front of a toll booth line. In this case the time spent in the toll is t2 plus the time spent waiting on line.

Part 1: Linked list routines a6p1.c and header file a6.h

Write linked list routines for maintaining lists of cars. You will need to declare a car list node structure type carNodeType that contains the arrival time, duration of toll processing, and pointer to the next car in the toll line.

To manage your lists, you must implement (at least) the following functions:

carNodeType *insertCar(int arrivalTime, int processingTime, carNodeType *listPtr);
Use dynamic memory allocation to allocate a new car node, initializes it, and place at the end of the list pointed to by *listPtr. Return pointer to updated linked list. Note that the function argument *listPtr will be null if the list is empty.

carNodeType *removeCar(carNodeType *listPtr);
Remove first car node from the linked list and free the node memory. Return pointer to updated linked list. Returns NULL if the list becomes empty.

int countCars(carNodeType *listPtr);
Count the number of cars currently in a list.

Create a header file a6.h that contains the structure type definition and function prototypes for your list management routines. This header file must be included in both a6p1.c and a6p2.c.

Part 2: Toll booth simulator a6p2.c

Write a computer simulator to find the average waiting time at the toll booths. Use an array of three linked lists to model the cars waiting at the toll booths. As each car arrives, two facts are known: the car's arrival time t1 and the amount of time needed to process the car's toll t2.

Arrival and processing time will be expressed in integer units. Thus your simulator's main loop should probably increment a integer time counter by one tick each pass.

Your program should print out the avarage waiting time.

The data pairs are stored in an input file ordered by increasing arrival time. The simulation input file will be read from standard input. Here is an example simulation input file. Each line in the input file consists of two positive integer values: arrival time and processing time.

To start you in testing your simulator, here is a simple example where the average waiting time is easy to compute. Here is another simple example where the average waiting time is easy to compute.

Extra Credit: Different Queueing Policy a6p3.c

In the simulation described above cars choose to wait at the toll booth with the shortest line. As an alternative cars could choose to wait at the toll booth with the line of cars requiring the smallest total processing time. This alternative queueing policy was discussed in class.

For extra credit, modify your simulator in a6p2.c to create a new simulator that implements this different queue policy. Your program should print out the avarage waiting time under the alternative policy.

You will submit three files for this assignment: a6p1.c, a6p2.c, and a6.h. If you do the extra credit, submit a fourth file a6p3.c.

Programming assignments are due before class on the assignment due date.

Late assignments will be levied a late penalty of 10% per day. Late assignments will only be accepted up to 4 days late.

Academic Honesty and Collaboration

It is reasonable to discuss with others possible general approaches to problems. It is unreasonable to work together on a detailed solution, to copy a solution, or to give away a solution. If your common discussion can be detected by looking at the solutions, then there is too much collaboration. Such instances of academic dishonesty will result in a course grade of F or expulsion from Boston University.

Do not allow your work to be used by others:

Warning: If someone cheats by using your work, you will also be penalized


Page Created: Feb 6, 1995      
Maintained by: Stan Sclaroff