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
Apps are designed by___.
nadya68 [22]

Explanation:

Apps are designed by___.

A. Software Developer

is the answer

3 0
3 years ago
Read 2 more answers
If a user wants to change one small section of the formatting of a document and leave the rest the same, which
soldi70 [24.7K]
The answer is modifying a style
6 0
2 years ago
What is the impact of information technology in your daily life?
yawa3891 [41]
Technology affects people's lives differently.
Some are bad and some are good.
But for me, technology gives us a chance to collaborate and connect even if we are miles away.
People are opening their mind to new kind of knowledge that can help us improve and grow.
3 0
3 years ago
What statement best describes operating systems?
arlik [135]

Answer: D) Operating Systems manage the computer's random access memory (RAM)

Explanation:

It's not A because all modern computers use some form of an Operating System.

It's not B because some Operating Systems can cost hundreds of dollars.

While C has some truth to it, it's reversed. Operating Systems are there to manage and allocate system resources, and D is the better choice.

6 0
3 years ago
What is one reason why a business may want to move entirely online?
andrezito [222]

Answer:

To focus on global market

Explanation:

Hope this helps! :)

3 0
3 years ago
Other questions:
  • What precaution can you take while using a social networking site to prevent a data breach?
    15·1 answer
  • What are some good editing software apps for pc?
    11·1 answer
  • How to determine if the function f(x) = x^2 + 3 from real numbers to real numbers is Injective, surjective, or bijective
    13·1 answer
  • Which of the following barriers to oral communication is not the fault of the sender or receiver? being unprepared noise not pay
    12·2 answers
  • If you have an equipment failure while driving on an expressway, you should
    8·1 answer
  • Tommy loves taking care of homing pigeons. He sent a note to his crush who lives 24.0 km away from his house. These birds fly at
    9·1 answer
  • What is the benefit of hosting a website on a personali
    6·1 answer
  • What is a database and provide 2 examples of how you are using a database.
    5·1 answer
  • JAVA -Develop a program that prompts the user to enter a series of 10 integers and then determines and displays the largest and
    6·1 answer
  • Network connections implemented with the use of a cable modem take advantage of?
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!