Microsoft Word - Ass XXXXXXXXXXdocx
DPIT113 Problem Solving Assignment 1
Due: 11:59 pm July 26, 2020
Four people, Alice, Bob, Carol and Dave are travelling along a road when they come
to a cave entrance. Outside are two signs.
The first sign reads:
Quivering Cave
Maximum of two people to enter at any time.
The second reads:
Beware of the Grue If you are in the
dark, you will be eaten.
The cave is, in fact, a tunnel which the group must pass through.
The group has a single torch.
If two people travel together they travel at the speed of the slower person.
The problem is to find a way to get the entire group through the cave as quickly as
possible.
1. The individual crossing times are as follows:
Alice: 3 minutes
Bob: 5 minutes
Carol: 9 minutes
Dave: 12 minutes
a) What is the initial state?
) What is the goal state?
c) What possible states can be reached after a single trip through the cave
(one or two people crossing)?
d) Which of these states are promising? (May lead to a solution without
epeated states)
e) What sequence of states leads to the solution of 30 minutes?
2. A bit further along, the friends a
ive at a second, identical cave. Sadly,
Bob has sprained his ankle and cannot walk as quickly as before. The
new crossing times are as follows:
Alice: 3 minutes
Bob: 7 minutes
Carol: 9 minutes
Dave: 12 minutes
a) What total crossing time does the strategy you used in part 1 give?
) Is this the best possible time?
c) If it is not – what is the best time?
d) What is the new strategy (if any)?
3. We now generalise the times crossing times in this way:
Alice: a minutes
Bob: b minutes
Carol: c minutes
Dave: d minutes
with a ≤ b ≤ c ≤ d
a) What results are given by the two possible fastest time strategies?
) What determines which time is the better one?
Assignments should be converted to pdf format and submitted via moodle as
ass01.pdf
NOTE: This is not a group assignment. Plagiarism, copying someone else’s
work, will result in you both being given a mark of zero.
It doesn’t matter if you copy from as friend or the internet; both count
as plagiarism.
Marking Criteria
Questions Criteria Total
1 Successfully addresses the specs of the task fully. Any issues
or gaps missing of the tasks specs, reduction of 0.25 marks
each time.
4
2 Successfully addresses the specs of the task fully. Any issues
or gaps missing of the tasks specs, reduction of 0.25 marks
each time.
4
3 Successfully addresses the specs of the task fully. Any issues
or gaps missing of the tasks specs, reduction of 0.25 marks
each time.
2
Total 10