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
Hanging out with friends, watching your favorite TV show, and buying a pair of new shoes are all examples of _____ for doing wel
SpyIntel [72]
<span>Hanging out with friends, watching your favorite TV show, and buying a pair of new shoes are all examples of rewards for doing well in school. As the result of doing well in studies, a person can hang out with friends, watch their own favorite TV show and can buy a new pair of shoes. Hence all these things are the rewards that are being generated for a good performance in school.</span>
8 0
3 years ago
Read 2 more answers
1. True or false: The more pixels per inch in an image, the higher the resolution is. (1 point)
Annette [7]
1. true
2. pixel
3. raster images are built with pixels
4. false
5. image size
6. rollover
7. sharp with clear details
8. 78px
9. 24in
10. scalability
3 0
3 years ago
Print("Weight on Earth?")
Lynna [10]

Answer:

weightEarth = float(input("Enter weight on earth: "))

weightMoon = weightEarth/6

print("Weight on moon:", weightMoon)

Explanation:

You have to convert the string input into a float in order to do calculations with it.

5 0
2 years ago
Which of the following boxes should replace question mark
Rus_ich [418]

Answer:

There is nothing please put it then i will edit this answer.

Explanation:

6 0
3 years ago
Rubbing two sticks together to make a fire is an example what
Jet001 [13]
Rubbing two sticks together will cause friction
7 0
3 years ago
Read 2 more answers
Other questions:
  • Which of the following accurately completes this sentence? The Internet is ____.
    6·2 answers
  • which of the following are used on cable trays to protect the cable insulation from direct sunlight? a. barrier strips b. solid
    5·1 answer
  • The analog signals that carry analog or digital data comprise composites built from combinations of simple sine waves.
    12·1 answer
  • The arithmetic logic unit (alu) controls all of the functions performed by the computer's other components and processes all the
    7·1 answer
  • I Just Realized................
    7·2 answers
  • If data from a DOS system is electronically sent to an EHR or other Windows-based system via an interface to populate an indexed
    7·1 answer
  • Write a full class definition for a class named Counter, and containing the following members:________
    9·1 answer
  • You implement basic version control and go through the phase of creating a local repository. Initiate the commands to set up tha
    7·1 answer
  • What is a key differentiator for Accenture when delivering Artificial Intelligence (AI) solutions to clients?
    11·1 answer
  • Select the correct answer from each drop-down menu.
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!