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...

I attached the requirements file


Microsoft Word - Ass01-2017.docx 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? b) 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 repeated states) e) What sequence of states leads to the solution of 30 minutes? 2. A bit further along, the friends arrive 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? b) 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? b) 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