本次澳洲代写是算法和数据结构的一个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 prex 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.)