Assignment 2
Topic: Crossing the river, when you come to
it. Without Crying Wolf, Getting to your goat,
and being a cabbage?
Due on:
09 October (Saturday), 2021
Maximum Marks: 10
This is an assignment motivated by hard-core Electrical
Engineering: state space methods, in discrete-time Control Theory.
A person is travelling with a wolf, a goat, and a bag of
cabbages. Coming to a river, the person finds a small boat,
capable of holding only him/her, and one more animal or item: the
wolf, the goat, or the cabbage sack. The animals are well-behaved
when the person is with them i.e., the wolf doesn't try to think
of the goat when it comes to getting hungry, and the goat is least
interested in the cabbages in a similar situation.
However, the person would not dare to
leave these pairs on one side of the river to themselves, lest
anarchy rule. In how many ways can the river crossing be done?
You are to model the system in terms of states. The start state
is one with the person, the wolf, the goat and the cabbages on
one side of the river. You have to enumerate all possible state
changes so that the final state (all four on the other side of
the river) is reached. You have to use a linked representation for
a state, and state transitions, and evaluate all possibilities.
You will end up creating a search tree (no cycles!), where each
path from the root (the start state) to a leaf node (a feasible
solution) will also show the path (the steps involved).
Rules of the game
Programming is to be done in C/C++/Java. All assignments are to
be individual efforts in programming (no shared code, or
libraries or other code downloaded from the Internet): the entire
set of programs must be yours. We will use plagiarism detection
tools, and any violations will lead to your score being the magic
number said to have been discovered by the ancient Indians, and a
possible further disciplinary action based on the severity of the
offence. Assignment submission: on the day of the demo, please
submit your programs to the TAs immediately after the demo. You
will submit all your program files (and nothing else: no object
code, executables and the works) in ONE FLAT directory, with no
sub-directories.
Demo Schedule:
Venue: Online
Demos:
Sumeet Agarwal,
Sumantra Dutta Roy,
Department of Electrical Engineering, IIT Delhi, Hauz Khas,
New Delhi - 110 016, INDIA.
sumeet@ee.iitd.ac.in,
sumantra@ee.iitd.ac.in