Part 1

On the left bank of a river are a ferryman, a goat, a boat big enough for four, and an equal number of Bluebeards and Zombies. The latter remain at peace except when one group outnumbers the other. When the ferryman is absent, Bluebeards and Zombies eat goats. Only the ferryman can operate the boat.

 

Part 1.1

Describe an algorithm, in terms of preconditions, postconditions, and a sequence of invariant outcomes, for getting everyone to the right bank without conflict. Don't include a description of how to implement these outcomes yet (that's Part 1.2). Use n as the total number of Bluebeards (and Zombies). Remember that (1) outcomes may introduce variable(s) and (2) code implementing each outcome will also have to restore all prior outcomes. Be precise and concise. 

You can assume that the boat is always at the same location as the ferryman, so there is no need to mention the boat. The outline below divides the preconditions and postconditions in two, and uses three outcomes, but you are free to organize them differently if you wish.

PRECONDITION 1: Please replace this

PRE2: replace this

POSTCONDITION 1: replace this

POST2: replace this

INVARIANT OUTCOME 1: replace this

O2: replace this

O3: replace this

 

Part 1.2

Describe how to implement the outcomes in Part 1 (i.e., in order). A typical line has the form ...

Ferry X, Y, and Z to the right. 

Sometimes it's convenient to implement more than one outcome at a time. Remember to justify that prior outcomes remain true (invariant) at the appropriate places. An example of a heading below is "Implementation of outcomes 1 and 2."

Implementation of Outcome(s) ___ 

 

Implementation of Outcome(s) ___

...

 

Part 1.3

Calculate and clearly explain the efficiency of your algorithm.

replace this

 

Part 1.4

Give your opinion of the process of decomposing an algorithm into invariant outcomes. Justify your opinion.