DPIT113 Problem Solving Assignment 3 Due: 11:55 pm September 27, 2020
Part A: Traversing a maze
Consider the following maze:
Each square in the maze has been labelled with a letter. The starting square is D and the goal square is N. The arrows show the directions north(N), west(W), south(S) and east(E). All squares are reachable and there are no loops.
STRATEGY 1. The maze is to be traversed in the following manner:
Begin on the starting square Start with an empty list While you have not reached the goal square For each square adjacent to your current square (in the order E, S, W, N) If the square has not yet been visited and there is no wall in the way, add it to the start of the list. Visit the square at the start of the list and remove that square from the list.
STRATEGY 2. The maze is to be traversed in the following manner:
Begin on the starting square Start with an empty list While you have not reached the goal square For each square adjacent to your current square (in the order N, W, S, E) If the square has not yet been visited and there is no wall in the way, add it to the end of the list. Visit the square at the start of the list and remove that square from the list.
A B C D E
F G H I J
K L M N O
P Q R S T
N W E S
Tasks
1. Draw a tree representing the maze, rooted at the starting square, with siblings appearing in the order N, W, S, E. (1 mark) 2. List the squares in the order they are visited. Only list a square the first time it is reached. a. Using Strategy 1. (1 mark) b. Using Strategy 2. (1 mark) 3. a. Give the pre-order and post-order traversals of the tree. (1 mark) b. Which one of these is related to the traversal produced by strategy 1 (your answer in question 2.a)? Explain why this relationship exists. (1 mark) 4. What sort of traversal of the tree is produced by strategy 2? (1 mark)
Part B: Weighted Graphs
Consider the following undirected, weighted graph (presented in edge list format). Node 1 Node 2 Weight A B 3 A F 5 B C 5 B G 9 C D 4 C H 2 D E 7 D I 11 E J 8 F G 10 F K 4 G H 4 G L 2 H I 8 H M 6 I J 6 I N 3 J O 9 K L 8 K P 7 L M 3 L Q 10 M N 5 M R 5 N O 4 N S 8
O T 4 P Q 5 P U 6 Q R 4 Q V 8 R S 7 R W 2 S T 9 S X 3 T Y 7 U V 1 V W 7 W X 6 X Y 2
As an example, the notation A B 3 indicates that the path from A to B has a weight of 3.
Tasks
a) Draw the weighted graph. (2 marks)
b) Draw the minimal spanning tree on the 5 by 5 square of nodes. (2 marks)
Submit your assignment, via moodle, as First Name Last Name DPIT113 Ass3.pdf