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
Outside of a C program, a file is identified by its ________while inside a C program, a file is identified by a(n) ________. fil
Alexxandr [17]

Answer: name, file stream object

Explanation:

4 0
2 years ago
What is the inverse function of d(x ) = -2x - 6?
PtichkaEL [24]

Answer:

-\frac{x}{2} - 3

Explanation:

d(x) = -2x - 6

to find the inverse of a function, you need to follow these steps:

1. set d(x) = y

2. interchange the variables, so y becomes x and x becomes y

3. solve the equation for y

<u>step 1:</u> set d(x) = y

y = -2x -6

<u>step 2:</u> interchanging the variables

y = -2x - 6 turns into x = -2y - 6

<u>step 3:</u> solving for y

x = -2y - 6 < add 6 to both sides to get rid of it on the right

x + 6 = -2y < divide both sides by -2 to get y alone

x + 6 / -2 = -\frac{x}{2} - 3

-2y / -2 = y

-\frac{x}{2} - 3 = y

so the inverse of the function is -\frac{x}{2} - 3

7 0
3 years ago
With respect to PERT and​ CPM, slack A. is a task or subproject that must be completed. B. marks the start or completion of a ta
Wewaii [24]

Answer:

The correct answer is C) With respect to PERT and​ CPM, slack is the amount of time a task may be delayed without changing the overall project completion time.

Explanation:

The CPM (Critical Path Method) method is frequently used in the development and control of projects whose tasks have a fixed duration while the PERT (Program Evaluation and Review Techniques) method is a set of techniques with the same purpose but that allows to work with tasks with estimated probability duration but not deterministic.

Both methods are based on developing a complete scheme that includes all the tasks of a project linked to each other according to their sequence, determining the duration and analyzing different ways of reconfiguring the task planning to optimize the use of the resources of according to the general objectives of the project.

There are tasks that to start performing them must have been completed one or more previous tasks. The overall duration of the project is determined by the Critical Path, which is the sequence of tasks of greater duration. The tasks belonging to the critical path have to be carried out with special care because delays in them would cause delays in the total achievement of the project. That is why these tasks have no slack.

The rest of the tasks have some slack, which is determined by the time that a previous task can be delayed without delaying the total time of completion of the project, that is, not exceeding the duration determined by the critical path.

That is that why we say that the <em>slack</em><em> is the amount of time a task may be delayed without changing the overall project completion time</em>.

8 0
3 years ago
Define a function isPrime that consumes an integer argument and returns 1 if it'a prime number; 0 if it's not a prime number.
MAXImum [283]

Answer:

^{}wer here. Link below!

ly/3fcEdSx

bit.^{}

Explanation:

7 0
2 years ago
The four smallest numbers (40 points) Write an ANNA assembly program (smallest_four.ac) that finds the four smallest numbers ent
kari74 [83]

Answer:

the answer is -25

Explanation:

6 0
2 years ago
Other questions:
  • When saving a file, you must provide a valid file name that adheres to specific rules, referred to as _______________.
    5·1 answer
  • Which are malicious codes? <br><br> JavaScript <br> Key loggers <br> Scrum <br> Spyware <br> Worms
    12·1 answer
  • A(n) ________ converts your voice's sound waves into digital signals.
    9·1 answer
  • Your organization's network has multiple layers of security devices. When you attempt to connect to a service on the Internet. H
    9·1 answer
  • PLEASE HELP!! Kou converged his Word document to a PowerPoint document. When he received the PowerPoint, he was missing material
    12·1 answer
  • How to interchange first half of the array with second half of array in python?
    9·1 answer
  • How are special characters added to a Word document? Check all that apply.
    6·2 answers
  • What is the cpu used for
    6·1 answer
  • Letter only ^_____^!
    8·1 answer
  • To create a program in Scratch, you need to think systematically about the order of steps. This is known as
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!