Explain algorithm which gives initial infection of computer

Assignment Help Data Structure & Algorithms

Reference no: EM1354502

You are helping some security analysts monitor a collection of networked computers tracking the spread of an online virus. There are n computers in the system, labeled C1, C2,...,Cn and as input you are given a collection of trace data indicating the times at which pairs of computers communicated. Thus the data is a sequence of ordered triples (Ci,Cj,tk) such a triple indicates that Ci and Cj exchanged bits at time tk. There are triples total. We will assume that the triples are presented to you in sorted order of time.

The security analysts you are working with would like to be able to answer questions of the following form: if 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 Cj exchanges bits with an uninfected computer at time tk (that is, if either of the triples (Ci,Cj,tk) or (Cj,Ci,tk) appears in the trace data) then Cj becomes infected as well, starting at time tk Infection can thus spread from one machine to another through a sequence of communications, which must happen in non-decreasing order of time. Describe an O(m+n) algorithm which, given an initial infection of a computer Ca at time t determines for each other computer the earliest time at which it can become infected. Your algorithm should keep track of enough information so that, for any computer Cb it is possible to retrieve in O(n) time a sequence of communications by which Cb could have become infected.

Reference no: EM1354502

Questions Cloud

How long does the electron take to travel : At a waterpark, sleds with riders are sent along a slippery,horizontal surface by release of a large, compressed spring.The spring with a force constant k= 3700 N/m and negligible mass rests on the frictionless horizontal surface.

Expalin about organizational development and benefits : Show organizational Development is used within your organization to bring about change at the individual, group and organizational level.

Explain how many fish should a commercial fisherman try : Explain how many fish should a commercial fisherman try to catch a day. Should he catch as many as possible or return to dock before filling the boat with fish.

Benefits and limitations of audit : Explain the economic benefits provided by a financial statement audit. Explain the inherent limitations that might prevent auditors from finding every potential material misstatement in financial statements.

Explain algorithm which gives initial infection of computer : Explain an O(m+n) algorithm which, given an initial infection of a computer Ca at time t determines for each other computer the earliest time at which it can become infected.

Improve organizational performance-employee character : Show which of the subsequent employee characteristics have the greatest impact on employee behavior: general attitudes, job satisfaction, emotions and moods, personality, values, or perception

Explain advertisers can then create a profile of you : Explain Advertisers can then create a profile of you based on your browsing behavior as well as store your browsing history as long as they like.

What make both the farmer and the rancher willing to trade : What make both the farmer and the rancher willing to trade with one another.

Equity valution for bank of america : You are considering an investment in Bank of America (BAC, NYSE). From your analysis, you believe this stock should be valued so as to produce a 9.5 percent long-term rate of return.

User Account

All Pages