Part A (30 marks total)

Question 1: Constructing SNI and directed graph [5 marks total]

(a) (1 mark) Creating your SNI. In this assignment you are required to use your student number to

generate input.

Take your student number and prefix it by “98” and postfix it by “52”. This will give you a twelve digit initial input number. Call the digits of that number d[1], d[2], . . . , d[12] (so that d[1] = 9, d[2] = 8,...,d[12] = 2).

Apply the following algorithm to these twelve digits:

1 fori=2to12

2 if d[i]==d[i−1]

3 d[i] = (d[i]+3) mod 10

After applying this algorithm, the resulting value of d forms your 12-digit SNI. Write down your initial number and your resulting SNI.

(b) (4 marks) Construct a graph S with nodes all the digits 0,1,...,9. If 2 digits are adjacent in your SNI then connect the left digit to the right digit by a directed edge. For example, if “15” appears in your SNI, then draw a directed edge from 1 to 5. Ignore any duplicate edges. Draw a diagram of the resulting graph. (You may wish to place the nodes so that the diagram is nice, e.g., no or few crossing edges.)

Question 2: Strongly connected components [25 marks total]

Given a directed graph G = (V, E), a subset of vertices U (i.e., U ⊆ V ) is a strongly connected component

ofGif,forallu,v∈U suchthatv̸=u, a) u and v are mutually reachable, and

b) there does not exist a set W ⊆ V such that U ⊂ W and all distinct elements of W are mutually reachable.

For any vertices v,u ∈ V, v and u are mutually reachable if there is both a path from u to v in G and a

path from v to u in G.

The problem of finding the strongly connected components of a directed graph can be solved by utilising the depth-first-search algorithm. The following algorithm SCC(G) makes use of the basic depth-first-search algorithm given in lecture notes and the textbook, and the transpose of a graph; recall that the transpose of a graph G = (V,E) is the graph GT = (V,ET), where ET = {(u,v) | (v,u) ∈ E} (see Revision Exercises 3: Question 6). (For those who are interested, the text provides a rigorous explanation of why this algorithm works.)

SCC(G)

1 call DFS(G) to compute finishing times u.f for each vertex u

2 compute GT , the transpose of G

3 call DFS(GT ), but in the main loop of DFS, consider the vertices in order of decreasing u.f

4 output the vertices of each tree in the depth-first forest of step 3 as a separate

strongly connected component

(a) (12 marks) Perform step 1 of the SCC algorithm using S as input. Do a depth first search of S (from Question 1b), showing colour and immediate parent of each node at each stage of the search as in Fig. 22.4 of the textbook and the week 3 lecture notes. Also show the start and finish times for each vertex.

For this question you should visit vertices in numerical order in all relevant loops: for each vertex u ∈ G.V and

for each vertex v ∈ G .Adj[u].

T

(c) (10 marks) Perform steps 3, 4 of the SCC algorithm. List the trees in the depth-first forest in the order

in which they were constructed. (You do not need to show working.)

Part B (70 marks total)

[Be sure to read through to the end before starting]

There is a virus called COMP-4500 in a population. You are in charge of determining the most likely path that this virus could have been transmitted through the population between two people.

Every person within the population is assigned with a unique identifier. An ‘interaction’ takes place between two people, at a given time, and has a probability score describing how likely the virus is transmitted from the transmitter to the receiver. A single interaction is represented as a tuple;

            (personFrom, personTo, timeOfInteraction, transmissionProbability)

Where:

• 0 < transmissionProbability ≤ 1.

• timeOfInteraction is a non-negative integer.

For example, the tuple (P1, P2, 8, 0.8) represents an interaction that took place between persons P1 and P2, at time 8, which has a probability of transmitting COMP-4500 from P1 to P2 of 0.8 (80%).

One person within the population is known to have COMP-4500 at time 0, this person will be referred to as the startPerson. There is another person within the population who is confirmed case of COMP- 4500, who is labelled as the endPerson. Additionally, there is a set of interactions that took place between members of the population (provided as a list).

A ‘valid path’ is a sequence of interactions such that:

• all times are non-decreasing.

• the personTo identifier of one interaction matches the personFrom identifier of the next interaction

The probability of COMP-4500 being transmitted along a path is the product of the transmissionProbability fields of all interactions along that path. We aim to find a valid path from the startPerson to the endPerson with the highest probability of transmission.