### 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.

### Write a Review

#### Creating financial tracking program

Acme Inc. is making next generation financial tracking program, and Alice has been provided the task of writing encryption component.

#### Describe a fair coin algorithm to returns either 0 or 1

Describe a FAIRCOIN algorithm that returns either 0 or 1 with equal probability, using ONEINTHREE as your only source of randomness.

#### Polynomial time algorithm for rooted directed acyclic graphs

Illustrate that if you were given a polynomial time algorithm for determining whether two rooted directed acyclic graphs are isomorphic, then polynomial time algorithm for testing.

#### Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

#### Write down the algorithm to insert an item

Write down the sample code to create a Linked List and allocate storage space for a node Write down the algorithm to insert an item At the beginning of a linked list

#### Algorithm for finding smallest element in unsorted array

Consider the following algorithm for finding the smallest element in an unsorted array: RANDOMMIN(A[1 .. n]). What is the exact expected number of executions of line ( )?

#### Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

#### Use a search tree to find the solution

Explain how will use a search tree to find the solution.

#### Give time algorithm that outputs satisfying assignment

Find out  whether there is an assignment of true/false values to the literals such that at least a*m clauses will be true. Note that 3-SAT(1) is exactly the 3-SAT problem. Give an O(m*n)-time algorithm that outputs a satisfying assignment for 3-S..

#### Calculate worst-case run-time complexity of algorithm

Calculate the worst-case run-time complexity of your algorithm and prove optimality of the solution it gives. Suppose that the road is a straight line with a western end and an eastern end.

#### Explain compression algorithms are often used in forensics

"Compression algorithms are often used in forensics. Suppose you are involved in a case and have been asked by the lawyer to explain, in general terms.

#### Determine the inorder, preorder and postorder traversal

Determine the Inorder, preorder and postorder traversal