Algorithm to keep track of sufficient information

Assignment Help Data Structure & Algorithms

Reference no: EM1369140

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: EM1369140

Questions Cloud

Evaluate archiver-s method opitmally : You've been hired as the outside consultant to evaluate archiver's method, in part as company is interested in automating this phase of process. Is archiver's method optimal?

What is profit selling price if you make a sell : You do not incur any cost to produce goods you sell and thus your profit equals selling price if you make a sell. Or three sellers do not have any costs either.

Process company contacts : If costs about the same amount per minute for processing with either of the two methods, when should each be used?

Question on expansionary fiscal policy : In an expansionary fiscal policy to overcome current recession, the Federal Government increases its expending to improve the nation's physical infrastructure

Algorithm to keep track of sufficient information : Your algorithm must keep track of sufficient 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.

Example on line balancing : A representative of the human resources department has just called complaining that the company hasn't been receiving the agreed-upon number of students.

Illustrate market tax and label tax revenues : Suppose government now impose a tax, , on every unit of cheese produced. Graphically illustrate market after tax. Label tax revenues collected. Who bears more of burden.

Why to take an electric potential to be zero at infinity : Two point charges q_1 = 2.10 nC and q_2 = -6.10 nC are 0.100 {rm{ m}} apart. Point A is midway between them; point B is 0.080 {rm{ m}} from q_1 and 0.060 {rm m} from q_2 Take an electric potential to be zero at infinity.

Create program which calculate distance travelled by boat : Create a program which calculate distance a boat travels across a river, given the width of the river, the boat's speed perpendicular to the river.

User Account

All Pages