本次澳洲代写是算法和数据结构的一个assignment

Part A (25 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 prex 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 for i = 2 to 12
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 [20 marks total]

Given a directed graph G = (V;E), a subset of vertices U (i.e., U  V ) is a strongly connected component
of G if, for all u; v 2 U such that v = 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 2 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 = f(u; v) j (v; u) 2 Eg (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) (10 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. That means that you should draw the annotated graph for each stage of the
search. (We want to make sure that you understand how the algorithm works.) 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 2 G:V and
for each vertex v 2 G:Adj[u].

(b) (2 marks) Perform step 2 of the SCC algorithm and draw ST .

(c) (8 marks) Perform steps 3, 4 of the SCC algorithm. In your solution you must list (and draw) the
trees in the depth-first forest in the order in which they were constructed. (You do not need to show
working.)