1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
kakasveta [241]
3 years ago
10

Timing circuits are a crucial component of VLSI chips. Here’s a simple model of such a timing circuit. Consider a complete balan

ced binary tree with n leaves, where n is a power of two. Each edge e of the tree has an associated length le, which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.
The root generates a clock signal which is propagated along the edges to the leaves. We’ll assume that the time it takes for the signal to reach a given leaf is proportional to the distance from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then the signal will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we’re not able to shrink edge lengths). If we achieve this, then the tree (with its new edge lengths) will be said to have zero skew. Our goal is to achieve zero skew in a way that keeps the sum of all the edge lengths as small as possible.

Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew and the total edge length is as small as possible.
Computers and Technology
1 answer:
gregori [183]3 years ago
5 0

Answer:

Let L and R be the sub-trees underneath the root r.

If the height of L (where we consider height to be the maximum length of all root-leaf paths) is ∆ more than that of R, ∆ ≥ 0, then the length of the edge  (r, R) is increased by ∆.

Then, we separately perform the same cycle over L and R.

Once more, by induction, argue that this greedy algorithm is efficient –

when it does not increase the length of (r, R) edge by ∆, then prove that the solution can be improved.

You might be interested in
Which of the following can you use to attach external hardware devices to a computer?
Genrish500 [490]

The answer is c that what a lot of people use☻

5 0
3 years ago
Read 2 more answers
One way to protect against a security threat to a computer system is to __________. Avoid external links with inconsistent URLs
Makovka662 [10]

One way to protect against a security threat to a computer system is to Avoid external links with inconsistent URLs.

<h3>What is malware?</h3>

Malware is any programme that is purposely designed to disrupt a computer, server, client, or computer network, leak private information, obtain unauthorised access to information or systems, deny users access to information, or otherwise interfere with the user's computer security and privacy.

One way to protect against a security threat to a computer system is to Avoid external links with inconsistent URLs. The reason for this is that such links may contain malware or spyware.

Learn more about Malware:

brainly.com/question/14276107

#SPJ1

7 0
2 years ago
Why should a user preview the document before printing?​
Margarita [4]
The user should preview a document first to make sure the layout is correct, so as not to waste paper if a font size or layout is incorrect.
5 0
3 years ago
Read 2 more answers
Suppose you have two arrays of ints, arr1 and arr2, each containing ints that are sorted in ascending order. Write a static meth
telo118 [61]
Since both arrays are already sorted, that means that the first int of one of the arrays will be smaller than all the ints that come after it in the same array. We also know that if the first int of arr1 is smaller than the first int of arr2, then by the same logic, the first int of arr1 is smaller than all the ints in arr2 since arr2 is also sorted.

public static int[] merge(int[] arr1, int[] arr2) {
int i = 0; //current index of arr1
int j = 0; //current index of arr2
int[] result = new int[arr1.length+arr2.length]
while(i < arr1.length && j < arr2.length) {
result[i+j] = Math.min(arr1[i], arr2[j]);
if(arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
boolean isArr1 = i+1 < arr1.length;
for(int index = isArr1 ? i : j; index < isArr1 ? arr1.length : arr2.length; index++) {
result[i+j+index] = isArr1 ? arr1[index] : arr2[index]
}
return result;
}


So this implementation is kind of confusing, but it's the first way I thought to do it so I ran with it. There is probably an easier way, but that's the beauty of programming.

A quick explanation:

We first loop through the arrays comparing the first elements of each array, adding whichever is the smallest to the result array. Each time we do so, we increment the index value (i or j) for the array that had the smaller number. Now the next time we are comparing the NEXT element in that array to the PREVIOUS element of the other array. We do this until we reach the end of either arr1 or arr2 so that we don't get an out of bounds exception.

The second step in our method is to tack on the remaining integers to the resulting array. We need to do this because when we reach the end of one array, there will still be at least one more integer in the other array. The boolean isArr1 is telling us whether arr1 is the array with leftovers. If so, we loop through the remaining indices of arr1 and add them to the result. Otherwise, we do the same for arr2. All of this is done using ternary operations to determine which array to use, but if we wanted to we could split the code into two for loops using an if statement.


4 0
4 years ago
A file that is 242 megabytes is being downloaded. if the download is 15.4% complete, how many megabytes have been downloaded? ro
Lunna [17]
37.26 megabytes have been downloaded
5 0
3 years ago
Other questions:
  • Select the correct answer.
    6·1 answer
  • Identify the parts used in an electric circuit- Tiles
    9·2 answers
  • We must know the Inflation Rate and the Nominal GDP in order to calculate Real GDP.
    15·1 answer
  • Select the correct answer.
    12·2 answers
  • 1. Do you consider Facebook, MySpace, and LinkedIn forms of disruptive or sustaining technology? Why?
    15·1 answer
  • There are a few simple rules that you can follow to store and manage files and folders in your computer. What is the most import
    9·2 answers
  • Spoken word and written word are different because what
    9·1 answer
  • 2. a computer system designed to run games is called what?
    11·1 answer
  • Which of the following might an interior designer in the retail industry specialize in?
    9·1 answer
  • 8.1.4: Ghost Invasion!
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!