COMP4500/7500 Advanced Algorithms and Data Structures - Assignment 1: SNI, directed graph, Strongly connected components and Secret Finder
COMP4500/7500
Advanced Algorithms and Data Structures
Assignment 1
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 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 [20 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) (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. 20.4 of the textbook [4th edition]. 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 ∈ G.V and
for each vertex v ∈ 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.)
Part B (75 marks total): Secret Finder
[Be sure to read through to the end before starting.]
Organisations are interested in discovering secrets. Each secret has a type. There may be zero or more secrets of the same type. Initially, each organisation only knows one or more initial secrets. However, organisations may learn more secrets by invoking exchange pacts that have been formed between organisations.
There is a set of k exchange pacts that have been formed. Each exchange pact {firstOrg 7→ firstType, secondOrg 7→ secondType}
represents an agreement made between distinct organisations firstOrg and secondOrg in which firstOrg agrees to share all of its known secrets of type firstType with secondOrg and secondOrg agrees to share all of its known secrets of type secondType with firstOrg if both (i) firstOrg knows at least one secret of type firstType and (ii) secondOrg knows at least one secret of type secondType. It is permissible for firstType and secondType to be the same type of secret. There may be zero or more exchange pacts between the same two organisations.
When an exchange pact {firstOrg 7→ firstType, secondOrg 7→ secondType} is invoked, then if (i) firstOrg knows at least one secret of type firstType when the pact is invoked, and
(ii) secondOrg knows at least one secret of type secondType when the pact is invoked,
then firstOrg shares all of the secrets of type firstType that it currently knows with secondOrg and secondOrg shares all of the secrets of type secondType that it currently knows with firstOrg. Otherwise (if either firstOrg does not know at least one secret of type firstType or secondOrg does not know at least one secret of type secondType), no secrets are shared. After a pact is invoked, each organisation knows the secrets that it knew before the pact was invoked, in addition to any secrets that were shared with it during the invocation.
Only one exchange pact can be invoked at any one time (so that invocations that have taken place can be represented by a, possibly-empty, sequence of exchange pact invocations), however there are no constraints on the number of times that an exchange pact can be invoked (it can be invoked zero or more times), or the order in which exchange pacts can be invoked.
Given a mapping from each organisation to the set of set of secrets that the organisation knows initially, and a set of exchange pacts that have been formed between those organisations, we say that an organisation
can discover a secret s if and only if there exists a (possibly empty) sequence of invocations of formed
exchange pacts, such that after the exchange pacts have been invoked (in the order described by the sequence
of invocations), that organisation g knows secret s.
Example 1 As a running example, consider the (n = 6) organisations {g0, g1, g2, g3, g4, g5} and their corresponding initial secrets:
g0 : {s3}
g1 : {s3}
g2 : {s2, s4, s5}
g3 : {s3}
g4 : {s0}
g5 : {s1}
where secrets s0, s1 and s2 are of secret type t0, secrets s3 and s4 are of secret type t1, and secret s5 is of secret type t2 (so that the number of secrets initially known by at least one organisation is m = 6); and the following (k = 12) exchange pacts that have been formed between them:
{g0 7→ t0, g1 7→ t2} {g0 7→ t1, g4 7→ t0} {g0 7→ t1, g4 7→ t1} {g0 7→ t2, g3 7→ t1} {g1 7→ t0, g2 7→ t0} {g1 7→ t1, g2 7→ t2} {g2 7→ t1, g4 7→ t2} {g3 7→ t0, g4 7→ t0} {g3 7→ t2, g5 7→ t0} {g4 7→ t0, g5 7→ t1} {g4 7→ t2, g5 7→ t1} {g4 7→ t2, g5 7→ t2}
We have, for example that organisation g0 can discover secret s3 because after the empty sequence of exchange pacts, ⟨⟩, have been invoked, organisation g0 knows s3 (because s3 is one of the initial secrets of g0).
Organisation g0 can also discover secrets s0, s1 and s5 because it will know these secrets after invoking the following sequence of exchange pacts (in the given sequential order):
{g0 7→ t1, g4 7→ t0} {g1 7→ t1, g2 7→ t2} {g0 7→ t0, g1 7→ t2} {g0 7→ t2, g3 7→ t1} {g3 7→ t2, g5 7→ t0} {g3 7→ t0, g4 7→ t0} {g0 7→ t1, g4 7→ t0}
-
When {g0 7→ t1, g4 7→ t0} is first invoked, g0 knows at least one secret ({s3}) of type t1; and g4 knows at least one secret ({s0}) of type t0, and so g0 shares secrets {s3} with g4 and g4 shares secrets {s0} with g1.
-
When {g1 7→ t1, g2 7→ t2} is then invoked, g1 knows at least one secret ({s3}) of type t1; and g2 knows at least one secret ({s5}) of type t2, and so g1 shares secrets {s3} with g2 and g2 shares secrets {s5} with g1.
-
When {g0 7→ t0, g1 7→ t2} is then invoked, g0 knows at least one secret ({s0}) of type t0; and g1 knows at least one secret ({s5}) of type t2, and so g0 shares secrets {s0} with g1 and g1 shares secrets {s5} with g0.
-
When {g0 7→ t2, g3 7→ t1} is then invoked, g0 knows at least one secret ({s5}) of type t2; and g3 knows at least one secret ({s3}) of type t1, and so g0 shares secrets {s5} with g3 and g3 shares secrets {s3} with g0.
-
When {g3 7→ t2, g5 7→ t0} is then invoked, g3 knows at least one secret ({s5}) of type t2; and g5 knows at least one secret ({s1}) of type t0, and so g3 shares secrets {s5} with g5 and g5 shares secrets {s1} with g3.
-
When {g3 7→ t0, g4 7→ t0} is then invoked, g3 knows at least one secret ({s1}) of type t0; and g4 knows at least one secret ({s0}) of type t0, and so g3 shares secrets {s1} with g4 and g4 shares secrets {s0} with g3.
-
When {g0 7→ t1, g4 7→ t0} is then invoked, g0 knows at least one secret ({s3}) of type t1; and g4 knows at least one secret ({s0,s1}) of type t0, and so g0 shares secrets {s3} with g4 and g4 shares secrets {s0, s1} with g0.
Organisation g0 cannot, however, discover secrets s2 or s4.
Your task is to design, implement and analyze an algorithm that takes as input:• A mapping from the organisations to their initial secrets, initialSecrets, • a set of exchange pacts, exchangePacts
• an organisation g ∈ initialSecrets.keySet(), and
• a secret s,and returns true if and only if organisation g can discover secret s; otherwise the algorithm should return false.
For example, given the mapping from organisations to their initial secrets, and exchange pacts from Example 1,
1. given organisation g0, and secret s0, your algorithm should return true. 2. given organisation g0, and secret s1, your algorithm should return true. 3. given organisation g0, and secret s2, your algorithm should return false 4. given organisation g0, and secret s3, your algorithm should return true. 5. given organisation g0, and secret s4, your algorithm should return false. 6. given organisation g0, and secret s5, your algorithm should return true.
You algorithm must be designed and implemented as efficiently as possible.
Question 3: Design and implement an efficient solution (50 marks)
Design and implement an algorithm that answers the question above. Your algorithm should be as efficient as possible. Marks will be deducted for inefficient algorithms (e.g. a brute-force approach is not appropriate). Clearly structure and comment your code. Use meaningful variable names.
-
Your algorithm should be implemented in the static method SecretFinder.canDiscover from the SecretFinder class in the assignment1 package that is available in the zip file that accompanies this handout.
The zip file for the assignment also includes some other code that you will need to compile the class SecretFinder as well as some junit4 test classes to help you get started with testing your code.
-
Do not modify any of the files in package assignment1 other than SecretFinder, since we will test your code using our original versions of these other files.
-
You may not change the class name of the SecretFinder class or the package to which it belongs. You may not change the signature of the SecretFinder.canDiscover method in any way or alter its specification. (That means that you cannot change the method name, parameter types, return types or exceptions thrown by the method.)
-
Your implementation should be in Java 1.8. You are encouraged to use Java 8 SE API classes, but no third party libraries should be used. (It is not necessary, and makes marking hard.)
-
Don’t write any code that is operating-system specific (e.g. by hard-coding in newline characters etc.), since we will batch test your code on a Unix machine. Your source file should be written using ASCII characters only.
-
You may write additional classes, but these must belong to the package assignment1 and you must submit them as part of your solution – see the submission instructions for details.
-
The JUnit4 test classes as provided in the package assignment1.test are not intended to be an exhaustive test for your code. Part of your task will be to expand on these tests to ensure that your code behaves as required.
Your implementation will be evaluated for correctness and efficiency by executing our own set of junit test cases. Code that is submitted with compilation errors, or is not compatible with the supplied testing framework will receive 0 marks. A Java 8 compiler will be used to compile and test the code.
Question 4: Worst-case analysis (25 marks)
This question involves performing an analysis of the worst-case time complexity and worst-case space com- plexity of your algorithm from Question 3.
(a) (5 marks) For the purpose of the worst-case time complexity analysis in Q4(b) and the worst-case space complexity analysis in Q4(c), provide clear and concise pseudocode that summarizes the algorithm you used in your implementation from Question 3. You may use the programming constructs used in Revision solutions, and assume the existence of common abstract data types like sets, maps, queues, lists, graphs, as well as basic routines like sorting etc.
Clearly structure and comment your pseudocode. Use meaningful variable names.
[It should be no more than two pages using minimum 11pt font. Longer descriptions will not be marked.]
(b) (12 marks) Let n be the total number of organisations, m be the total number of initial secrets1, and k be the number of formed exchange pacts.
Provide an asymptotic upper bound on the worst case time complexity of your algorithm in terms of parameters n, m and k. Make your bound as tight as possible and justify your solution using your pseudocode from Q4(a).
You must clearly state any assumptions that you make (e.g. on the choice of implementations of any data structures that you use, and their running time etc.).
To simplify your analysis, you should make the (incorrect but simplifying) assumption that HashSet (or HashMap) operations that have expected-case time complexity O(1) actually have worst-case time complexity O(1). E.g. checking for set-membership in a HashSet has expected-case time complexity that is O(1).
[Make your analysis as clear and concise as possible – it should be no more than a page using minimum 11pt font. Longer descriptions will not be marked. Also note that to receive any marks for this question, you must justify your solution – it is not enough to only give an asymptotic upper bound without explanation.]
(c) (8 marks) As for Q4(b), let n be the total number of organisations, m be the total number of initial secrets, and k be the number of formed exchange pacts.
Provide an asymptotic upper bound on the worst case space complexity of your algorithm in terms of parameters n, m and k. Make your bound as tight as possible and justify your solution using your pseudocode from Q4(a).
You must clearly state any assumptions that you make (e.g. on the choice of implementations of any data structures that you use, and their space usage etc.).
[Make your analysis as clear and concise as possible – it should be no more than a page using minimum 11pt font. Longer descriptions will not be marked. Also note that to receive any marks for this question, you must justify your solution – it is not enough to only give an asymptotic upper bound without explanation.]
