[Solved]1 Overview Suppose Monitoring Collection N Networked Computers Labeled Cc2 Cn Order Track Q37227899
I need help with the following Java code
1. OVERVIEW Suppose you are monitoring a collection of n networked computers, labeled CC2….. Cn, in order to track the spread of an online virus. You are given a collection of trace data indicating the times at which pairs of computers communicated. The data is provided as a sequence of mordered triples (Ci, Cj.f). Such a triple indicates that C, and Cj communicated at time t For simplicity let us assume that each pair of computers communicates at most once during the interval under consideration. Your goal is to devise an efficient data structure to answer infection queries; that is, queries of the following form: f the virus was inserted into computer Ca at time x, could it possibly have infected computer Cb by time y? The mechanics of infection are simple: if an infected computer Ci communicates with an uninfected computer Cj at time tk (in other words, if one of the triples (Ci, Cj,tk) or (Cj, Ci,tk) appears in the trace data), then computer Ci becomes infected as well, starting at time k Infection can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backward in time. Thus, for example, if C, is infected by time tk, and the trace data contains triples (Ci,Cjl and (Cj,Cat), where t r then Ca will become infected via Ci. Example I. Suppose that n = 4, the trace data consists of the triples (Ci. C2.4). (C2. C4.8), (C3, C4.8), (Ci, C4, 12), and that the virus was inserted into computer G at time 2·Then C3 would be infected at time 8 by a sequence of three steps: first C2 becomes infected at time 4, then C4 gets the virus from C2 at time 8, and then C3 gets the virus from C4 at time 8. Example 2. Suppose that n-4, the trace data consists of (C2. C3, 8), (C1, C4. 12), (C1. C2. 14) and that the virus was inserted into computer Ci at time 2. Then Cs would not become infected during the period of observation: although C2 becomes infected at time 14, C3 only communicates with C2 before C2 was infected. There is no sequence of communications moving forward in time by which the virus could get from C1 to C3. Project objective. Write a program that takes a collection R of m triples, corresponding to the trace data for n computers, and preprocesses R in O(n mlogm) time2 to build a data structure G We allow t to be equal to t. This just means that Cj had open connections to both Ci and C at the same time, and so a virus could move from C to C Worst-case or expected time bounds are equally acceptable for this project. We were unable to transcribe this imageAssume that G has been constructed. To determine whether a virus introduced at computer Ca . walk through the list for Ca until we reach the first reference to a node (Саґ) such that If a node (Cn y with y’ S y is reachable from (Ca x), then we declare that Cb could have You should verify for yourself that this algorithm indeed answers infection queries correctly in at time x could have infected computer Cb by time y, we do the following. Run BFS or DFS on G to determine all nodes reachable from (Ca become infected by time y; otherwise, we declare that this is impossible. O(m) time. Cs, 8 C4, 8 Cs. 8 Cs, 12 Ci. 4 C2. 4 C.12 C2 Ca FIGURE 1. The graph G for the trace data of Example 1 3. SPECIFICATIONS Your submission must be a Java program that contains the two classes described in this section: CommunicationsMonitor and ComputerNode. You must make these classes and their methods public. Each of the classes may contain additional methods apart from the required ones. Be judicious in designing the classes and the data structures. 3.1. CommunicationsMonitor. The CommunicationsMonitor class represents the graph G built to answer infection queries. It has the following methods. CommunicationsMonitorO: Constructor with no parameters. . void addCommunication(int cl, int c2, int timestamp): Takes as input two integers c1, c2, and a timestamp. This triple represents the fact that the computers wit!h IDs c1 and c2 have communicated at the given timestamp. This method should run in O(1) time. Any invocation of this method after createGraph is called will be ignored. void createGraph(): Constructs the data structure as specified in the Section 2·This method should run in O(nmlogm) time List<ComputerNode> queryInfection (int cl, int c2, int x, int y): Deter mines whether computer c2 could be infected by time y if computer c1 was infected at time x. If so, the method returns an ordered list of ComputerNode objects that represents the transmission sequence. This sequence is a path in graph G. The first ComputerNode object on the path will correspond to c1. Similarly, the last ComputerNode object on the path will correspond to c2. If c2 cannot be infected, return null Example 3. In Example l , an infection path would be (C-4), (GA), (С. 8). (C4.8), (C3.8) This method can assume that it will be called only after createGraph) and that xSy This method must run in O(m) time. This method can also be called multiple times with different inputs once the graph is constructed (i.e., once createGraph(O has been invoked. HashMap<Integer, List<ComputerNode getComputerMappingO: Returns a HashMap that represents the mapping between an Integer and a list of ComputerNode objects. The Integer represents the ID of some computer Ci, while the list consists of pairs (Ci,t1), (Ci,t2), (Ci, t), represented by ComputerNode objects, that specify that Ci has communicated with other computers at times ti, .. ., 4. The list for each computer must be ordered by time; i.e., ti < 12 < .< k . List<ComputerNode> getComputerMapping(int c): Returns the list of ComputerNode objects associated with computer c by performing a lookup in the mapping. .2. ComputerNode. The ComputerNode class represents the nodes of the graph G, which are pairs (Ci, t). int getIDO: Returns the ID of the associated computer. int getTimestamp(): Returns the timestamp associated with this node. » List<ComputerNode> getOutNeighbors O: Returns a list of ComputerNode objects to which there is outgoing edge from this ComputerNode object. Show transcribed image text 1. OVERVIEW Suppose you are monitoring a collection of n networked computers, labeled CC2….. Cn, in order to track the spread of an online virus. You are given a collection of trace data indicating the times at which pairs of computers communicated. The data is provided as a sequence of mordered triples (Ci, Cj.f). Such a triple indicates that C, and Cj communicated at time t For simplicity let us assume that each pair of computers communicates at most once during the interval under consideration. Your goal is to devise an efficient data structure to answer infection queries; that is, queries of the following form: f the virus was inserted into computer Ca at time x, could it possibly have infected computer Cb by time y? The mechanics of infection are simple: if an infected computer Ci communicates with an uninfected computer Cj at time tk (in other words, if one of the triples (Ci, Cj,tk) or (Cj, Ci,tk) appears in the trace data), then computer Ci becomes infected as well, starting at time k Infection can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backward in time. Thus, for example, if C, is infected by time tk, and the trace data contains triples (Ci,Cjl and (Cj,Cat), where t r then Ca will become infected via Ci. Example I. Suppose that n = 4, the trace data consists of the triples (Ci. C2.4). (C2. C4.8), (C3, C4.8), (Ci, C4, 12), and that the virus was inserted into computer G at time 2·Then C3 would be infected at time 8 by a sequence of three steps: first C2 becomes infected at time 4, then C4 gets the virus from C2 at time 8, and then C3 gets the virus from C4 at time 8. Example 2. Suppose that n-4, the trace data consists of (C2. C3, 8), (C1, C4. 12), (C1. C2. 14) and that the virus was inserted into computer Ci at time 2. Then Cs would not become infected during the period of observation: although C2 becomes infected at time 14, C3 only communicates with C2 before C2 was infected. There is no sequence of communications moving forward in time by which the virus could get from C1 to C3. Project objective. Write a program that takes a collection R of m triples, corresponding to the trace data for n computers, and preprocesses R in O(n mlogm) time2 to build a data structure G We allow t to be equal to t. This just means that Cj had open connections to both Ci and C at the same time, and so a virus could move from C to C Worst-case or expected time bounds are equally acceptable for this project.
Assume that G has been constructed. To determine whether a virus introduced at computer Ca . walk through the list for Ca until we reach the first reference to a node (Саґ) such that If a node (Cn y with y’ S y is reachable from (Ca x), then we declare that Cb could have You should verify for yourself that this algorithm indeed answers infection queries correctly in at time x could have infected computer Cb by time y, we do the following. Run BFS or DFS on G to determine all nodes reachable from (Ca become infected by time y; otherwise, we declare that this is impossible. O(m) time. Cs, 8 C4, 8 Cs. 8 Cs, 12 Ci. 4 C2. 4 C.12 C2 Ca FIGURE 1. The graph G for the trace data of Example 1
3. SPECIFICATIONS Your submission must be a Java program that contains the two classes described in this section: CommunicationsMonitor and ComputerNode. You must make these classes and their methods public. Each of the classes may contain additional methods apart from the required ones. Be judicious in designing the classes and the data structures. 3.1. CommunicationsMonitor. The CommunicationsMonitor class represents the graph G built to answer infection queries. It has the following methods. CommunicationsMonitorO: Constructor with no parameters. . void addCommunication(int cl, int c2, int timestamp): Takes as input two integers c1, c2, and a timestamp. This triple represents the fact that the computers wit!h IDs c1 and c2 have communicated at the given timestamp. This method should run in O(1) time. Any invocation of this method after createGraph is called will be ignored. void createGraph(): Constructs the data structure as specified in the Section 2·This method should run in O(nmlogm) time List queryInfection (int cl, int c2, int x, int y): Deter mines whether computer c2 could be infected by time y if computer c1 was infected at time x. If so, the method returns an ordered list of ComputerNode objects that represents the transmission sequence. This sequence is a path in graph G. The first ComputerNode object on the path will correspond to c1. Similarly, the last ComputerNode object on the path will correspond to c2. If c2 cannot be infected, return null Example 3. In Example l , an infection path would be (C-4), (GA), (С. 8). (C4.8), (C3.8) This method can assume that it will be called only after createGraph) and that xSy This method must run in O(m) time. This method can also be called multiple times with different inputs once the graph is constructed (i.e., once createGraph(O has been invoked. HashMap
Expert Answer
Answer to 1. OVERVIEW Suppose you are monitoring a collection of n networked computers, labeled CC2….. Cn, in order to track the… . . .
OR
