CS2402: Lab assignment #3
--------------------------

Due date: October 31st, at midnight
Send your report (YourName.doc or YourName.pdf) and a zipped file of your program 
(YourName.tar.gz or YourName.zip) to your TA (Carlos Acosta, ceacosta@utep.edu) and 
cc to me (mceberio@cs.utep.edu). 

--------------------------
* Topics covered in this lab assignment:

discrete event simulation (DES), queues (priority queues and plain queues)

* Objective of this lab assignment:
- understand the workings of queues, including priority queues
- manipulate queues in a complex program
- be able to design a discrete event simulation: define the events, manage them in a time-based simulation
- define a testing strategy: define and justify a set of test cases to put your program to test
- run appropriate experiments to point out the difference between two methods applied to the same problem 

---------------------------
Description of the problem:

Let us consider the following problem of managing the traffic at an intersection with lights.

        |    |
        |    |
   ------    -------
   road 1	
   ------    -------
        |    |
        | ^  |
	  |
	road 2

Traffic is coming (which are cars) on roads 1 and 2. Some go straight, others turn right or left.

The objective of the discrete event simulation of the traffic at this intersection is to control the frequency of green and red lights on both roads.

---------------------------
What you are expected to do:

Answer the following question:
1. What are the events you have to consider in this problem?
2. What are the data structures that you are going to use to solve this DES problem?
3. What are the parameters of your simulation?
4. What is the main algorithm for the simulation?
5. What kind of information do you seek out of this simulation? How do you retrieve it? How do you process it?

Implement a program:
- whose input is 
	1. a series of events to be enqueued at the beginning of the simulation:
	each event is represented by:
	* the street where the car comes from: 1 or 2;
	* direction: W or E (on road 1), N or S (on road 2);
	(* the direction after the lights: S (straight), R (right) or L (left);)
	* the time at which the car arrives.
	2. the frequency of the green and red lights:
	* time of green light for road 1
	* time of green light for road 2 
		
- whose output is: the information obtained from the simulation, printed out of the screen and
	in a file.

Run experiments:
- to point out the difference between running DFS without or with constraint propagation.
- note: you are not compelled to actually run DFS without using constraints: you can just
  do a theoretical study of this option, and compare it against the practical experiments
  run when using constraints 

Write a report, whose general outline is described in the policy rules for labs, available at
www.cs.utep.edu/mceberio/teaching, under Current Semester, and CS2402.

---------------------------
Example of an input file:

1 W 8:00  // a car arrives on road1 W at 8:00
2 N 8:00  // a car arrives on road2 N at 8:00
...
1 2       // light on road 1 stays green during two minutes
2 1       // light on road 2 stays green during one minute

In order to test your program, in addition to special test cases, you will generate randomly input files of the above-described kind.
In order to run efficient simulation, you will have to run several simulations for the same series of coming cars, with different frequencies of the green/red lights. 

NOTE:
1. you can also generate test cases using a method whose parameters are the frequency of the car arriving and the lights changing colors.
2. the time of green light translates into a number of cars that can go through the crossing during this time.
---------------------------