程序代写案例-COMP4500/7500-Assignment 1

COMP4500/7500 Assignment 1 (August 30, 2021) 2
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 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 ∈ U such that v 6= 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
COMP4500/7500 Assignment 1 (August 30, 2021) 3
(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 ∈ 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): Trade manager
[Be sure to read through to the end before starting.]
You are in charge of regulating the trade of items of different possible types between a set of traders.
Each trader has one type of item that it produces, and a set of types of items that the trader is willing to
trade. A trader is always willing to trade the type of item that they produce. More than one trader can
produce the same type of item. The types of items that a trader is willing to trade never changes.
Just because a trader is willing to trade a particular type of item, doesn’t mean that they can trade that
item. Initially, each trader can only trade the type of item that they produce. In order to be able to trade
any other types of items, they need to form trade agreements with other traders.
For any two different traders, ta and tb, and two different types of item, gx and gy, we say that a trade
agreement
(ta, tb, gx, gy)
can be formed between traders ta and tb in which ta agrees to trade items of type gx with tb in exchange for
items of type gy from tb if and only if
• trader ta can trade items of type gx,
• trader tb can trade items of type gy,
• trader ta is willing to trade items of type gy, and
• trader tb is willing to trade items of type gx.
After agreement (ta, tb, gx, gy) is formed
• Trader ta can trade items of type gy, as well as all of the other types of items that it could trade before
the agreement was formed, and
• Trader tb can trade items of type gx, as well as all of the other types of items that it could trade before
the agreement was formed.
COMP4500/7500 Assignment 1 (August 30, 2021) 4
The agreement has no other side effects. (E.g. it does not change the types of items that any other trader
can trade, nor does it change any of the types of items that any trader (including ta and tb) is willing to
trade.)
Given a set of traders, T , and a (possibly empty) sequence of trade agreements between traders from T ,
〈(ta0, tb0, gx0, gy0), (ta1, tb1, gx1, gy1), . . . , (tan, tbn, gxn, gyn)〉
where, for i ∈ {0, 1, . . . , n}, tai ∈ T and Tbi ∈ T , tai 6= tbi and gxi 6= gyi, we say that the sequence of
agreements can be formed if and only if for every i ∈ {0, 1, . . . , n}, the agreement (tai, tbi, gxi, gyi) can be
formed, given that the only agreements that have already been formed so far are the ones that appear before
it in the linear ordering, i.e. agreement (tai, tbi, gxi, gyi) can be formed, given that the only agreements that
have already been formed so far are
(ta0, tb0, gx0, gy0), (ta1, tb1, gx1, gy1), . . . , (ta(i−1), tb(i−1), gx(i−1), gy(i−i)) .
Recall here that before any agreements have been formed, each trader can only trade the type of item that
they produce. This means, for example, that the first agreement in any non-empty sequence, (ta0, tb0, gx0, gy0),
must be able to be formed before any other agreements have been formed, i.e. when each trader can only
trade the type of item that they produce.
Example 1 As a running example, consider the following set, T , of traders:
t0 : (g0, [g0, g1, g2, g7, g8])
t1 : (g1, [g1, g5])
t2 : (g2, [g0, g2, g3, g4])
t3 : (g3, [g1, g2, g3, g4])
t4 : (g4, [g4, g6])
t5 : (g5, [g1, g4, g5])
t6 : (g6, [g0, g4, g6])
t7 : (g7, [g7, g8])
t8 : (g8, [g7, g8])
where each trader above is described first by their name, then the type of item that they produce, and then
by the set of types of items that they are willing to trade. E.g. trader t0 can produce items of type g0 and
is willing to trade items of either type g0, g1, g2, g7, or g8.
Initially, each trader can only trade the type of item that they produce. For example, initially t0 can only
trade items of type g0. That is to say, t0 can trade g0 after the empty sequence of trade agreements, 〈〉,
have been formed.
After forming the following sequence of trade agreements,
〈(t0, t2, g0, g2)〉
we have that t0 can trade g2 as well as g0, and t2 can trade g0 as well as g2. Agreement (t0, t2, g0, g2)
can be formed before any other agreements have been made because trader t0 can initially trade g0, the
item it produces, and is willing to trade g2, and trader t2 can initially trade g2, the item that it produces,
and is willing to trade g0.
If trader t0 would like to be able to trade items of type g1, then a longer sequence of trade agreements
is required. In this example, there is only one producer of items of type g1, trader t1. No agreement can
ever be formed directly between traders t0 and t1 because they have only one type of item in common that
they are willing to trade (g1). There are two other traders, t3 and t5 who are also willing to trade items
of type g1. Trader t0 will never be able to form an agreement directly with t5 because they have only one
COMP4500/7500 Assignment 1 (August 30, 2021) 5
type of item in common that they are willing to trade (g1). Trader t3 is eventually able to form the trade
agreement (t3, t0, g1, g2) with t0, after which t0 can trade g1, but this is only after a number of other
trade agreements have been formed. (Note that initially, before any trade agreements have been formed, t3
cannot yet trade items of type g1, and t0 cannot yet trade items of type g2.). Trader t0 can trade g1 (as
well as g0 and g2), for example, after the following sequence of trade agreements have been formed (between
traders in T ):
〈(t0, t2, g0, g2), (t4, t6, g4, g6), (t2, t6, g0, g4), (t2, t3, g4, g3), (t1, t5, g1, g5), (t5, t3, g1, g4), (t3, t0, g1, g2)〉
Note that the sequence of trade agreements above can be formed (in the order given), because:
• As per the earlier reasoning, agreement (t0, t2, g0, g2) can be formed before any other agreements
have been made.
• Next, it is possible to form agreement (t4, t6, g4, g6), because trader t4 can trade g4, the item it
produces, and is willing to trade g6, and trader t6 can trade g6, the item that it produces, and is
willing trade g4.
• It is possible to next form agreement (t2, t6, g0, g4) because after forming agreement (t0, t2, g0, g2),
t2 can trade g0, and after forming agreement (t4, t6, g4, g6), t6 can trade g4. Trader t2 is also willing
to trade g4, and t6 is willing to trade g0.
• Next, it is possible to form agreement (t2, t3, g4, g3) because after forming agreement (t2, t6, g0, g4),
t2 can trade g4, t3 can trade g3, the item that it produces; and t2 is willing to trade g3 and t3 is
willing to trade g4.
• Next, it is possible to form agreement (t1, t5, g1, g5), because trader t1 can trade g1, the item it
produces, and is willing to trade g5, and trader t5 can trade g5, the item that it produces, and is
willing trade g1.
• Next, it is possible to form agreement (t5, t3, g1, g4) because after forming agreement (t1, t5, g1, g5),
t5 can trade g1; after forming agreement (t2, t3, g4, g3), t3 can trade g4; and t5 is willing to trade
g4 and t3 is willing to trade g1.
• Finally, it is possible to next form agreement (t3, t0, g1, g2), because after forming agreement
(t5, t3, g1, g4), t3 can trade g1; after forming agreement (t0, t2, g0, g2), t0 can trade g2; and t3 is
willing to trade g2 and t0 is willing to trade g1.
There is no sequence of trade agreements that can be formed such that trader t0 can trade items of either
type g7 or g8. The only traders who are willing to trade items of these types are t0, t7 and t8. Even though
t7 and t8 can form agreement (t7, t8, g7, g8), after which both t7 and t8 can both trade items of type
g7 and g8, there is no way for t0 to form an agreement with either of them to trade g7 or g8 without first
being able to trade one of these two items (which it cannot do, until one of these two agreements has been
formed).
Your task is to design, implement and analyze an algorithm that takes as input:
• A set of traders, T ,
• a trader t ∈ T , and
• the type of an item g that trader t is willing to trade
COMP4500/7500 Assignment 1 (August 30, 2021) 6
and returns true if and only if there exists a (possibly empty) sequence of agreements between traders in
the set T that can be formed, such that after those agreements are formed, trader t can trade items of type
g; otherwise the algorithm should return false.
For example, given the set of traders T from Example 1,
1. given traders, T , trader t0, and item type g0, your algorithm should return true.
2. given traders, T , trader t0, and item type g1, your algorithm should return true.
3. given traders, T , trader t0, and item type g2, your algorithm should return true.
4. given traders, T , trader t0, and item type g7, your algorithm should return false.
5. given traders, T , trader t0, and item type g8, your algorithm should return false.
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 TradeFinder.canTrade from the TradeFinder
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
TradeFinder 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 TradeFinder, since we will test
your code using our original versions of these other files.
• You may not change the class name of the TradeFinder class or the package to which it belongs.
You may not change the signature of the TraderFinder.canTrade 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.)
• Dont 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.
COMP4500/7500 Assignment 1 (August 30, 2021) 7
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 x be the number of traders in T , and let y be the number of different types of items
in the set that is formed by merging all of the types of items that each trader in T is willing to trade
into one set (i.e. y is the number of different types of items involved in the problem input).
Provide an asymptotic upper bound on the worst case time complexity of your algorithm in terms
of parameters x and y. 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 x be the number of traders in T , and let y be the number of different types
of items in the set that is formed by merging all of the types of items that each trader in T is willing
to trade into one set (i.e. y is the number of different types of items involved in the problem input).
Provide an asymptotic upper bound on the worst case space complexity of your algorithm in terms
of parameters x and y. 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.]
COMP4500/7500 Assignment 1 (August 30, 2021) 8
Evaluation Criteria
Question 1
• Question 1 (a) (1 mark)
1 : correct answer to question given
0 : answer not given or contains one or more mistakes
• Question 1 (b) (4 marks)
4 : The answer to question 1(a) is 100% correct, and the correct graph is given.
0 : If the answer to question 1(a) is not 100% correct, or the answer contains at least one mistake.
Question 2
If the graph produced for Question 1 is given and 100% correct, then the following marking scheme applies.
If the graph produced for Question 1 is mostly correct (but contains a minor error), then the student will
receive 2/3 of the marks obtained using the following marking criteria. Else, if the graph produced for
Question 1 contains more than a minor error, zero marks will be given for all aspects of this question.
• Question 2 (a) (10 marks)
10 : Correct answer given.
8 : All stages of the traversal shown on an annotated graph (like CLRS Fig. 22.4), including relevant
features for each vertex (colour, immediate parent and start and finish times), but there are one
or two minor mistakes.
6 : All stages of the traversal are shown on an annotated graph (like CLRS Fig. 22.4), however at
most one of the relevant features for each vertex (e.g. start-time) may not be included and there
may be up to three mistakes.
4 : Most stages of the traversal are shown on an annotated graph (like CLRS Fig. 22.4), however
at most two of the relevant features for each vertex (e.g. start-time) may not be included and
there may be up to four mistakes.
2 : Most stages of the traversal are shown on an annotated graph (like CLRS Fig. 22.4), however
at most two of the relevant features for each vertex (e.g. start-time) may not be included and
there may be up to five mistakes.
0 : Otherwise.
• Question 2 (b) (2 marks)
2 : correct answer to question given
0 : answer not given or contains one or more mistakes
• Question 2 (c) (8 marks)
This part of the question will be marked correct with respect to the finishing times for each vertex
calculated in Q2(a). If those finishing times are not given in Q2(a) then no marks will be awarded for
this section. Otherwise, the following marking criteria applies.
8 : All the trees in the depth-first forest are listed in the order in which they were constructed. All
aspects of the depth-first forest are correct.
COMP4500/7500 Assignment 1 (August 30, 2021) 9
6 : All the trees in the depth-first forest are listed in the order in which they were constructed, but
there was an error in the traversal that produced the forest.
4 : All of the trees in the depth-first forest are listed, however the order in which the trees were
created may not be clear, or there may be one or two errors in the traversal that produced the
forest.
2 : Either: (i) all of the strongly connected components of the graph are correctly listed, but the
trees (from the depth-first forest) from which these connected components were derived are not
clearly listed, or (ii) all of the trees in the depth-first forest are listed, however the order in which
the trees were created may not be clear and there may be up to three errors in the traversal that
produced the forest.
0 : Otherwise.
Question 3 (50 marks)
Your implementation will be evaluated for correctness and efficiency by executing our own set of junit test
cases.
50 : All of our tests pass
45 : at least 90% of our tests pass
40 : at least 80% of our tests pass
35 : at least 70% of our tests pass
30 : at least 60% of our tests pass
25 : at least 50% of our tests pass
20 : at least 40% of our tests pass
15 : at least 30% of our tests pass
10 : at least 20% of our tests pass
5 : at least 10% of our tests pass
0 : less than 10% of our test pass or work with little or no academic merit
Note: 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
For any marks to be received for this section, a plausible solution to Question 3 must have been presented
in Q3. If a plausible solution to Q3 has been attempted, the following marking criteria applies.
• Question 4(a) (5 marks)
For this question, the pseudocode given must be no longer than two pages using minimum 11pt font.
Longer solutions will receive 0 marks, otherwise the following marking criteria applies.
5 : Clear and concise pseudocode that summarizes the algorithm you used in your implementation
from Question 3. Clearly commented, and clear correspondence between the implementation
from Q3 and the pseudocode.
COMP4500/7500 Assignment 1 (August 30, 2021) 10
3 : Mostly clear and concise pseudocode that summarizes the algorithm you used in your imple-
mentation from Question 3. Mostly clearly commented, and mostly clear correspondence between
the implementation from Q3 and the pseudocode.
2 : Pseudocode given that summarizes the algorithm you used in your implementation from Ques-
tion 3. Potentially more verbose than necessary. May not be commented, or have a very clear
correspondence between the implementation from Q3 and the pseudocode.
1 : Pseudocode given that attempts to summarize the algorithm you used in your implementation
from Question 3. Aspects are unclear, or overly verbose, or the correspondence to the actual
implementation may be confusing.
0 : Work with little or no academic merit
• Question 4(b) (12 marks)
For this part of the question, the analysis should be no more than one page using minimum 11pt font.
Longer solutions will receive 0 marks. Also, Q4(a) must have been answered and received a mark of
at least 2. Otherwise the following marking criteria applies.
12 : A correct asymptotic upper bound on the worst-case time complexity of the algorithm from
Q3 is given and justified in terms of parameters x and y. The asymptotic upper bound should
be as tight as reasonably possible for the algorithm at hand. The worst-case time complexity
analysis is clearly justified with respect to the pseudocode from Q4(a). Any assumptions made
in the analysis are reasonable and clearly stated. Asymptotic notation should be used correctly
and the asymptotic time complexity given has been simplified to remove lower order terms and
unnecessary constant factors.
9 : A correct asymptotic upper bound on the worst-case time complexity of the algorithm from Q3
is given and justified in terms of parameters x and y. The asymptotic upper bound should be
reasonably tight for the algorithm at hand. The worst-case time complexity analysis is mostly
clearly justified with respect to the pseudocode from Q4(a). Any assumptions made in the analysis
are mostly reasonable and clearly stated.
6 : A reasonable attempt has been made to give and justify a reasonably-tight asymptotic upper
bound on the worst-case time complexity of the algorithm from Q3 in terms of parameters x
and y, however either it contains some minor mistakes but is otherwise reasonably justified, or
aspects of the justification of the analysis with respect to the pseudocode from Q4(a) are unclear.
Assumptions made in the analysis may be unclear.
3 : An attempt has been made to give and justify an asymptotic upper bound on the worst-case
time complexity of the algorithm from Q3 in terms of parameters x and y, however it contains
either a major mistake, or many mistakes, or gives an unreasonably loose upper bound, or the
justification for the analysis with respect to the pseudocode from Q4(a) may be poor (even if the
bound is correct).
0 : Work with little or no academic merit.
• Question 4(c) (8 marks)
For this part of the question, the analysis should be no more than a page using minimum 11pt font.
Longer solutions will receive 0 marks. Also, Q4(a) must have been answered and received a mark of
at least 2. Otherwise the following marking criteria applies.
8 : A correct asymptotic upper bound on the worst-case space complexity of the algorithm from
Q3 is given and justified in terms of parameters x and y. The asymptotic upper bound should
be as tight as reasonably possible for the algorithm at hand. The worst-case space complexity
COMP4500/7500 Assignment 1 (August 30, 2021) 11
analysis is clearly justified with respect to the pseudocode from Q4(a). Any assumptions made
in the analysis are reasonable and clearly stated. Asymptotic notation should be used correctly
and the asymptotic space complexity given has been simplified to remove lower order terms and
unnecessary constant factors.
6 : A correct asymptotic upper bound on the worst-case space complexity of the algorithm from
Q3 is given and justified in terms of parameters x and y. The asymptotic upper bound should be
reasonably tight for the algorithm at hand. The worst-case space complexity analysis is mostly
clearly justified with respect to the pseudocode from Q4(a). Any assumptions made in the analysis
are mostly reasonable and clearly stated.
4 : A reasonable attempt has been made to give and justify a reasonably-tight asymptotic upper
bound on the worst-case space complexity of the algorithm from Q3 in terms of parameters x
and y, however either it contains some minor mistakes but is otherwise reasonably justified, or
aspects of the justification of the analysis with respect to the pseudocode from Q4(a) are unclear.
Assumptions made in the analysis may be unclear.
2 : An attempt has been made to give and justify an asymptotic upper bound on the worst-case
space complexity of the algorithm from Q3 in terms of parameters x and y, however it contains
either a major mistake, or many mistakes, or gives an unreasonably loose upper bound, or the
justification for the analysis with respect to the pseudocode from Q4(a) may be poor (even if the
bound is correct).
0 : Work with little or no academic merit.

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie