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
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)}.
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
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:
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.