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
Your computer is crashing on a regular basis. Which of the following is an operation available to the user that should help rese
Neko [114]

Answer

System restore

Explanation

System restore is a recovery feature that helps restore your system to the previous condition or point. Most computers have system restore disks which are an advantage to the users especially when the computer clashes.These disks are very effective when it comes to restoring the system to its initial state.

6 0
3 years ago
Read 2 more answers
In the game of economics, producers look to technological improvements to increase which of the following?
Vaselesa [24]
They're looking to increase productivity 
7 0
3 years ago
Read 2 more answers
What's your opinion on Pokemon​ and pixeldip
faust18 [17]

Answer:

Its a good game but an amazing show. 10/10

Explanation:

7 0
2 years ago
Rapid va rog!!!!!!! Am 30 minute la dispozitie!! PLSSS !!!!!
Stella [2.4K]

uhhk if r dB BBL I 6th cnn he'll of

8 0
3 years ago
1. A green traffic sign means
NeX [460]

Answer:

general regulatory and speed control.

7 0
3 years ago
Other questions:
  • In a program called Nature's Notebook, citizen volunteers make and report observations about seasonal changes in plants and anim
    15·1 answer
  • if i set my payment and use free trial on Scribd website, can i cancel my payment and NOT PAYING after one month??
    8·1 answer
  • When you compose a message, you want your audience to find the information it needs quickly and to understand what it finds. You
    11·1 answer
  • HELP FOR JAVASCRIPT: 01. What is prototypical inheritance? 02. How can JavaScript be used to improve accessibility on the web? I
    6·1 answer
  • 1. Which of the following is not related to a buffer overflow? A. Static buffer overflow B. Index error C. Canonicalization erro
    10·1 answer
  • Which type of computer graphic can be blown up to a much larger size without getting distorted or losing quality?
    5·1 answer
  • Here is a list of storage devices:
    5·1 answer
  • Who watches the show gravity falls, if you do, if you play the theme song for the first episode backwards you get a hiding messi
    11·2 answers
  • 3. Why is human resource plan made​
    11·1 answer
  • Choose the response that best completes the following statement.
    14·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!