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
A computer system has a 32KB, 8-way set associative cache, and the block size is 8 bytes. The machine is byte addressable, and p
vagabundo [1.1K]

Answer:

Offset bits: 3-bits

Set number of cache: 12-bits

Tag bits: 7-bits

22-bit physical address

Explanation:

Since the system is 32K so,

=2⁵.2¹⁰

=2¹⁵

As we know that it is 8-way set associative so,

=2¹⁵/2³

=2¹⁵⁻³

=2¹²

2¹² are cache blocks

22-bit physical address

Off-set bits are 3 as they are calulated from 8-way set associative information.

Set number of cache : 12-bits

For tag-bits:

Add off-set bits and cache bits and subtract from the total bits of physical address.

=22 - (12+3)

=22 - 15

=7

3 0
3 years ago
Please fill these out. I really need this done.
tatyana61 [14]

Answer:

i can't see this

Explanation:

5 0
3 years ago
toThePowerOf is a method that accepts two int arguments and returns the value of the first parameter raised to the power of the
inessss [21]

Answer:

cubeVolume = toThePowerOf(cubeSide, 3)

Explanation:

The function toThePowerOf, receives two int arguments say, a and b, where a is the first argument and b is the second argument as follows:

toThePowerOf(a,b)

The function returns the first argument(a) raised to the power of the second argument (b) i.e a ^ b as follows:

toThePowerOf(a, b){

return a^b

}

In the call to the function, the first argument a, is replaced with the variable cubeSide and the second argument b is replaced with the value 3.

Hence, the returned result becomes cubeSide ^ 3 which is then stored in a variable cubeVolume as follows:

cubeVolume = toThePowerOf(cubeSide, 3)

6 0
2 years ago
________ tells users how to use software and what to do if software problems occur.
vitfil [10]

Answer:

Documentation tells users how to use software and what to do if software problems occur.

Explanation:

Documents and Standard Operating Procedures (SOPs) help users use the software that they want to use. This is an advantage to whoever is selling the software so that they don't receive customer complaints and people continue to buy their product.

4 0
1 year ago
7.3 Code Practice edhesive
sladkih [1.3K]

Answer:

def print_sum(a,b,c):

 print(a+b+c)

one = int(input("Enter the 1st number: "))

two = int(input("Enter the 2nd number: "))

three = int(input("Enter the 3rd number: "))

print_sum(one,two,three)

Explanation:

hope this helped :)

5 0
2 years ago
Read 2 more answers
Other questions:
  • Olivia needs to get permission to use a graph of data gathered by a trade association she plans to include the graph in a report
    10·2 answers
  • When approved for a loan, an individual essentially applied for aid in the area of...
    15·1 answer
  • Why is charles babbage known as father of computer?​
    10·1 answer
  • ____ is a method of querying and reporting that takes data from standard relational databases, calculates and summarizes the dat
    11·1 answer
  • Four differences between fourth and fifth generation of computers​
    12·1 answer
  • A browser allows you to set preferences for using the browser. These preferences include all of the following except
    7·1 answer
  • Need help please. this effect my technology
    15·1 answer
  • Hellpppp please I need it!
    15·1 answer
  • You Could Never Size Me UP! Been Doing This Sh*t A Long ⏱time
    15·1 answer
  • Complete the function favoriteFlower(). Note that the program will not run as is because the function is incomplete. The purpose
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!