CS 405
Project 2
Feuding Families
The Smiths and the Joneses have been feuding for as long as anyone can
remember. Both families have been settled for more than a century in a
picturesque valley along the Yaak River. It used to be downright dangerous
to stray too far from home because there was always trouble when ANY Smith
was anywhere near ANY Jones.
Well, lately, the situation is better. Territorial boundaries have been
agreed upon and each family has been pretty good about staying off of land
claimed by the opposing family. The one problem that remains to be solved
revolves around the one bridge that spans the Yaak. Both families need
to use the bridge. Neither family wants one of its members to be ON the
bridge at the same time that someone from the other family is also on the
bridge.
You are hired as a peace maker. Your job is to figure out a way for
the bridge to be shared between the two families in a way that does not
cause further commotion. Because you are such a talented computer scientist,
you decide to figure out a solution and simulate it on your computer before
presenting it to the families.
You decide to start as simply as possible and then refine your solution
to be even better. You not only kind of like both the Smiths and the Joneses,
but you don't want any buckshot in your backside, especially given that
the pay isn't all that good. You decide that the first problem that you
will solve and simulate is this:
Level 1 Solution Assumptions:
-
Assume that all Smiths live on the East side of the river and want to get
to the West side.
-
Assume that all Jones live of the West side of the river and want to get
to the East side.
-
Guarantee that whenever there are Smiths crossing from East to West that
there can be no Jones crossing from West to East.
-
Assume that any number of people can be on the bridge at once.
-
Assume that Smiths and Jones can show up at there respective sides of the
river at any time.
-
Assume that there are an "unlimited" number of Smiths and Jones (which
is close to true because there isn't a lot else to do in Yaak valley)
-
Assume that people can cross the river at any speed. The faster ones are
not delayed by the slower ones.
After you've solved the problem for Level 1, you will expand your solution
to handle the following:
Level 2 Solution Assumptions:
-
Assume that the bridge has a capacity of N persons on the bridge at once.
-
Provide a solution such that people should not wait any longer than necessary
to cross the bridge.
How to Begin:
You are not sure how to do some things and don't want that to immobilize
your work. You decide to actively start solving the problem by using some
things you know you will need to do. Here's your initial list of tasks.
-
You know that the most difficult part of your work will be to come up with
an algorithm that solves the problem of only allowing one family access
to the bridge at a time. You understand that you haven't worked with synchronization
mechanisms like monitors or semaphores yet, so you start by working on
your algorithm in terms of real world policies (rules) that could be enforced
to solve the problem.
-
You know that you will need to figure out the skeleton for the simulation
in Java. This will require that you fire off a bunch of "people" threads
at random intervals. Each people thread will either be a Smith or a Jones.
This should be random as well. You decide that as you are figuring other
things out, you should program the simulation shell.
-
You decide to email any questions that you have relating to this project
to a particular person that seems to be in charge of the project (joanf@wind.winona.msus.edu).
You realize that your credibility will be lessened if you ask questions
that are easily answered by a little investigation. You also realize that
the project can be delayed if you DON'T ask questions that you need answered
to solve the problem. You know that asking questions at the last minute
makes it look like the Smiths and Joneses aren't getting their money's
worth so you decide to START IMMEDIATELY.
Formalities:
The project is to be done in 2-person teams. Before your first working
meeting, you should both come up with an algorithm to solve the Level 1
problem and a Java template (compilable code) for your simulation.
Your solutions for Level 1 are due October 11. Your solutions
for Level 2 are due October 23.