Today we look at a new puzzle:
A transposition of a vector is created by switching exactly two entries of the vector. For example, (1,4,3,4,2,6,7) is a transposition of (1,2,3,4,5,6,7). Find the vector X if S = (0,0,1,1,0,1,1), T =(0,0,1,1,1,1,0), U=(1,0,1,0,1,1,0) and V=(1,1,10,1,0,1,0) are all transpostions of X Describe your method of finding X.
Intuitively many of the positions in a vector will remain unchanged if only two of the positions are exchanged in a transposition. If we are given a set of transpositions, a majority of them will share the common positions. Thus if a position has three or four occurrences of 1 in the given four transpositions, it is highly likely that the X also has 1 in those positions. Similarly a position with one occurrence among all the transpositions indicates a zero in the corresponding position with X.
We therefore start with X as follows:
0011011
0011110
1010110
1101010
?011?10 - X
With this candidate as X and switching the position of ? with the occurrence of extra 1 in a given transposition we eliminate the occurrence of ? and replace it with 1 or 0. In this case, it results in X as (1,0,1,1,0,1,0)
Alternatively we can also work through the problem in a systematic manner.
We enumerate all possible transpositions of S, T, U, and V in four columns by exchanging only two elements from their corresponding vector. Then we look for the vector that is common to all the possible enumerated transpositions. The nice thing about this method is that we can reduce the search space as we move from the transpositions in one column to the next and the number of candidates reduces to finally one in the last column. Given that there are 7 positions, each column may have 14 entries using the value of 0 or 1 for each of those seven positions. Candidates found in the first column will reduce to candidates found in the second column as the criteria that S and T will share the same transposition is restrictive. This further reduces as we include U with S and T and finally to the solution with S, T, U and V.
#explain ethernet protocol
The Exponential backoff algorithm is an example of the ethernet protocol
When a collision first occurs, a jamming signal prevents further data
a frame is sent again immediately or after 51.2 micro-seconds called an interval
If it fails, the frame is sent again in multiples of that interval
If it still fails, it is resent after a multiple that is in an integer between 0 and 7 (one less than a power of two)
If it fails after nth attempt, the frame is sent again at a multiple k where k is between 0 and one less than the nth power of 2
A transposition of a vector is created by switching exactly two entries of the vector. For example, (1,4,3,4,2,6,7) is a transposition of (1,2,3,4,5,6,7). Find the vector X if S = (0,0,1,1,0,1,1), T =(0,0,1,1,1,1,0), U=(1,0,1,0,1,1,0) and V=(1,1,10,1,0,1,0) are all transpostions of X Describe your method of finding X.
Intuitively many of the positions in a vector will remain unchanged if only two of the positions are exchanged in a transposition. If we are given a set of transpositions, a majority of them will share the common positions. Thus if a position has three or four occurrences of 1 in the given four transpositions, it is highly likely that the X also has 1 in those positions. Similarly a position with one occurrence among all the transpositions indicates a zero in the corresponding position with X.
We therefore start with X as follows:
0011011
0011110
1010110
1101010
?011?10 - X
With this candidate as X and switching the position of ? with the occurrence of extra 1 in a given transposition we eliminate the occurrence of ? and replace it with 1 or 0. In this case, it results in X as (1,0,1,1,0,1,0)
Alternatively we can also work through the problem in a systematic manner.
We enumerate all possible transpositions of S, T, U, and V in four columns by exchanging only two elements from their corresponding vector. Then we look for the vector that is common to all the possible enumerated transpositions. The nice thing about this method is that we can reduce the search space as we move from the transpositions in one column to the next and the number of candidates reduces to finally one in the last column. Given that there are 7 positions, each column may have 14 entries using the value of 0 or 1 for each of those seven positions. Candidates found in the first column will reduce to candidates found in the second column as the criteria that S and T will share the same transposition is restrictive. This further reduces as we include U with S and T and finally to the solution with S, T, U and V.
#explain ethernet protocol
The Exponential backoff algorithm is an example of the ethernet protocol
When a collision first occurs, a jamming signal prevents further data
a frame is sent again immediately or after 51.2 micro-seconds called an interval
If it fails, the frame is sent again in multiples of that interval
If it still fails, it is resent after a multiple that is in an integer between 0 and 7 (one less than a power of two)
If it fails after nth attempt, the frame is sent again at a multiple k where k is between 0 and one less than the nth power of 2
No comments:
Post a Comment