Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4500/7500 Assignment 1 (August 27, 2019) 2 Part A (35 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 [30 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
COMP4500/7500 Assignment 1 (August 27, 2019) 3
(a) (15 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].
(b) (3 marks) Perform step 2 of the SCC algorithm and draw ST .
(c) (12 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 (65 marks total): Warehouse shuffle
[Be sure to read through to the end before starting.]
You are in charge of storing items of different possible types in a set of warehouses.
Each warehouse has a capacity, denoting the maximum number of items that can be stored in the warehouse, and a defined set of types of items that are able to be stored in the warehouse. The capacity of a warehouse, and the set of types of items that can be stored in a warehouse cannot change. At any point in time, a warehouse keeps track of the number of each different type of item it has stored. The total number of items stored in a warehouse at any point in time cannot exceed the capacity of the warehouse, and the warehouse can only store items of types that can be stored in that warehouse. If the total number of items currently stored in the warehouse equals the capacity of the warehouse, then we say it is full.
A transfer of one item of stock of a given type x can be made from a source warehouse s to a destination warehouse d, if warehouse s currently contains at least one item of type x, and warehouse d is not currently full, and it is able to store items of type x.
From time to time a new item of stock is purchased and needs to transferred from a depot to one of the warehouses that you are in charge of. (For simplicity, a depot is a warehouse that is not in the set of warehouses that you are in charge of.) If you are in charge of a warehouse that is not full that can store the type of the new item, then this can be achieved easily by performing a single transfer of the new item of stock from the depot, to the warehouse. On the other hand, if all the warehouses that are able to store items of the given type are currently full, then it may be necessary to first transfer items between the existing warehouses, in order to make room for the new item, before transferring the new item from the depot to an available warehouse. In some circumstances, there may be no way to rearrange the items in the existing warehouses (by making transfers between them) in order to make room for the new item.
Example 1 For example, imagine that you are in charge of the following set of warehouses:
W 1 : 2 : (T 8, 0)
W2 : 2 : (T3,0),(T6,1),(T7,1)
W3 : 1 : (T1,0),(T2,1),(T9,0)
W4 : 2 : (T4,1),(T6,1)
W5 : 3 : (T1,1),(T3,2),(T6,0),(T8,0) W6 : 3 : (T4,0),(T8,1)
W 7 : 4 : (T 8, 4)
W8 : 3 : (T2,0),(T7,0),(T8,0),(T9,3)
COMP4500/7500 Assignment 1 (August 27, 2019) 4
where each warehouse above is described first by its name, then its capacity, and thirdly, a list of the types of items that can be stored in the warehouse and the number of items of that type that are currently stored in the warehouse. E.g. warehouse W 6 has a capacity of 3 and can store items of type T 4 or T 8. It currently stores zero items of type T4 and one item of type T8.
If a new item of stock of type T8 was purchased and needed to be transferred from the depot W 0 : 1 : (T 8, 1)
to one of the warehouses that you are in charge of, then this could be accomplished (easily) by performing the following sequence of transfer operations:
⟨(W0,W1,T8)⟩
where each transfer in the list above is being represented by a tuple of the source warehouse, followed by the destination warehouse, and then the type of the item that is transferred. Other sequences of transfers operations would also work, e.g. ⟨(W0,W6,T8)⟩.
Example 2 If you are still in charge of the same set of warehouses (in the same initial state) from Example 1, and a new item of stock of type T1 was purchased and needed to be transferred from the depot
W 0 : 1 : (T 1, 1)
to one of the warehouses that you are in charge of, then this cannot be achieved by one transfer operation, because all the warehouses that can store items of type T 1 are currently full. The item of stock can, however, be transferred from the depot to one of the warehouses by performing the following sequence of transfer operations (in the order they are given):
⟨(W4,W6,T4),(W2,W4,T6),(W5,W2,T3),(W0,W5,T1)⟩
That is, an item of type T4 can first be transferred from W4 to W6; and then an item of type T6 can be transferred from W2 to W4; then an item of type T3 can be transferred from W5 to W2; and then finally the new item of type T1 can be transferred from the depot, W0, to warehouse W5. There are other sequences of valid transfer operations that would also work.
Example 3 If you are now in charge of the following set of warehouses (note that these differ from those in the above examples only in the current contents of W6);
W 1 : 2 : (T 8, 0)
W2 : 2 : (T3,0),(T6,1),(T7,1)
W3 : 1 : (T1,0),(T2,1),(T9,0)
W4 : 2 : (T4,1),(T6,1)
W5 : 3 : (T1,1),(T3,2),(T6,0),(T8,0) W6 : 3 : (T4,3),(T8,0)
W 7 : 4 : (T 8, 4)
W8 : 3 : (T2,0),(T7,0),(T8,0),(T9,3)
a new item of stock of type T1 was purchased and needed to be transferred from the depot W 0 : 1 : (T 1, 1)
to one of the warehouses that you are in charge of, then this cannot be done. Not only are all of the warehouses that can store items of type T1 currently full, but there is also no way to rearrange the items in the existing warehouses (by making transfers between them) in order to make room for the new item.
COMP4500/7500 Assignment 1 (August 27, 2019) 5 You task is to design, implement and analyze an algorithm that takes as input:
• A depot that is non-null and contains exactly one item of a particular type. The depot may not contain any items of any other type and must have a capacity of one,
• A set of warehouses that is non-null, does not contain null warehouses, and does not include the depot, and, without modifying the state of the depot or any of the warehouses in any way (e.g. items should not be
added or removed from the depot or any of these warehouses), it returns as output either:
(a) A non-null list of transfers such that
(i) each transfer is non-null and takes place either between two warehouses in the given set of warehouses, or between the given depot and a warehouse in the set of warehouses;
(ii) given the initial state of the depot and warehouses, all the transfers can be performed in the order in which they appear in the list; and
(iii) the depot is empty when all transfers in the list are completed (in order, starting from the initial state of the depot and warehouses).
OR
(b) the value null if and only if no such list of transfers, as described in part (a), exists.
You algorithm must be designed and implemented as efficiently as possible.