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