- June 10, 2020

CS220 Semester 1 2020 Assignment 4 (traversal and optimisation) Due date June 10, 2020, 10pm 100 Marks in total This assignment requires you to submit programs in Python that you have written yourself to the automarker, http://www.cs.auckland.ac.nz/automated-marker. Your imple- mentation must be from first principles and cannot use an existing library methods that might solve the problem (eg graph search algorithms etc). You can use libraries for stan- dard implementations of data structures such as queues, stacks and priority queues. The automarker runs on a Linux box. Read the automarker help and FAQ for more details. Please submit only Python source code (.py extensions only). 1. Directed girth of a digraph 30 Marks For a digraph G, the length of the shortest cycle is called the directed girth of the graph. If the digraph has no cycle then the girth is undefined, and we will say it has girth 0. Your task is to determine the directed girth of each input digraph. Input format: described below under the heading, “Digraph input format”. Output format: Output will be just one integer per line sent to the console. For the example input given below we would output the following two integers denoting the directed girth of the two digraphs, using 0 to indicate the digraph has no cycle. 3 0 2. Tree and cross arcs in a DFS 30 Marks For a given set of digraphs, write a program that performs DFS on each digraph starting at node 0 and prints out the total number of tree arcs and cross arcs resulting from the traversal. Use our standard convention that when there is a choice of white or grey nodes, the one with the lowest index should be chosen. Input format: described below under the heading, “Digraph input format”. Output format: For each input digraph, print out a line with the number of tree arcs and the number of cross arcs separated by a comma. For the example input shown below, the output would be 3,0 2,1 Digraph input format: A sequence of one or more digraphs is taken from the keyboard (sys.stdin). Each graph is represented by an adjacency list. The first line is an integer n in- dicating the order of the graph. This is followed by n white space separated lists of adjacen- 1 cies for nodes labeled 0 to n – 1. The lists are sorted. The input will be terminated by a line consisting of one zero (0). This line should not be processed. The sample input below shows two digraphs, the first has node set {0, 1, 2, 3} and arc set {(0, 1), (0, 3), (1, 2), (1, 3), (2, 0)}, the second has node set {0, 1, 2} and arc set {(0, 1), (0, 2), (2, 1)}. 4 1 3 2 3 0 3 1 2 1 0 3. Optimisation 40 Marks A frog needs to navigate its way from its current position to its next meal through a dangerous landscape. To do so, it leaps from boulder to boulder, but it can jump at most 1m. Your aim is to find the length of the shortest path to get the frog to its next meal using only boulders. The landscape is a n × n square (units are cm) with boulders at exact positions given by coordinates (x, y) where 0 ≤ x, y ≤ n. Boulders are scattered across the landscape. Use Euclidean distance to calculate the distance between boulders. Input format: The input is taken from the keyboard (e.g. by sys.stdin) as multiple lines of comma separated integers. Each line has 2p + 1 numbers where p ≥ 2. The first number on each line is the size of the landscape, n. The following 2p numbers give locations of p boulders, so the jth boulder is at (2j, 2j + 1). The first position listed on each line is the frog’s current position, the final position listed is the target boulder where the frog will find its next meal. For example: 100,0,0,0,100,100,100 1000,20.892,986,602,138.97,206.2,10.44 200,25,25,10,1,50,25,140,30 Output format: For each line of input, output a single number to the console which is the length of the shortest path from the origin town to the desitination town. Use str.format to give this value to 2 decimal places. Precisely, format 2 x using ’{:.2f}’.format(x). Do not use any other rounding throughout your algorithm. If the destination town is unreachable from the origin, output -1. For the example input above, output would be: 200.00 -1 115.14 Marking The maximum number of submissions for each problem is fixed at 10. Each problem has four test cases associated with it worth one quarter of the marks for that problem. Some of the test cases will be large to test for speed. You get full marks if you pass all test cases. 3