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
What is a good analogy for explaining the actions of a compiler?
kozerog [31]

Answer:

The answer to this question is given below in the explanation section.

Explanation:

This question is about what is a good analogy for explaining the actions of a compiler?  The correct option is <u> automatic programming of kitchen devices .</u>

<u> </u>

a hybrid ability of a car to use multiple energy sources  (false)

this analogy is not correctly mapped on the compiler, becuase the compiler can be designed only for one type of language, for example, the program that calculates the average of students number can be easily programmed in C++ and in C#. But you cannot compile the C# program in C++ compiler and vice versa.  

a street map of a local subdivision  (false)

Because you can design a compiler for a not specific subdivision of programming.

an interpreter who speaks several languages

it is not an analogy, however, an interpreter can handle only one type of language.

an automatic programming of kitchen devices (true)

This is a good analogy of compiler because you give input to the device and that device based on your input gives you back an output. Similarly, you give input to the compiler in form of language syntax, and it automatically give you output based on your input.

3 0
3 years ago
What is network hardware?
vovangra [49]
Modem, router, switch, server, etc. these are hardware meant to facilitate the transfer or storage of remote information.
8 0
3 years ago
16. Budget Analysis Write a program that asks the user to enter the amount that he or she has budgeted for a month. A loop shoul
strojnjashka [21]

Answer:

import java.util.Scanner;

public class num8 {

   public static void main(String[] args) {

       Scanner in = new Scanner(System.in);

       System.out.println("Enter month's budget");

       double monthBudget = in.nextDouble();

       double totalExpenses = 0.0;

       double n;

       do{

           System.out.println("Enter expenses Enter zero to stop");

           n = in.nextDouble();

           totalExpenses += n;

       }while(n>0);

       System.out.println("Total expenses is "+totalExpenses);

System.out.println("The amount over your budget is "+ Math.abs(monthBudget-totalExpenses));

   }

}

Explanation:

  • Using Java programming language
  • Prompt user for month's budget
  • Use Scanner class to receive and store the amount entered in a variable
  • Use a do while loop to continuously request user to enter amount of expenses
  • Use a variable totalExpenses to add up all the expenses inside the do while loop
  • Terminate the loop when user enters 0 as amount.
  • Subtract totalExpenses from monthBudget and display the difference as the amount over the budget

6 0
3 years ago
What is the part of a file, the .pptx, or .txt etc called?
Lunna [17]
It is called the file extension or filename extension. It is a suffix that indicates the file format.
7 0
3 years ago
Read 2 more answers
What may happen if a large number of computer users are attempting to access a web site at the same time that you are?
Andrews [41]
D (you may be unable to link to the site). The site cannot handle the large load of requests and are queued therefore, the response will be slowed down immensely. <span> </span>
5 0
3 years ago
Other questions:
  • âwhat two log files are used by older versions of unix and newer version of linux to store log information
    10·2 answers
  • Assessment timer and count Assessment items Item 6 How many different keys can be used in a single sort? 1 2 3 4
    14·1 answer
  • In c++ 11, the ________ tells the compiler to determine the variable's data type from the initialization value.
    6·1 answer
  • Why is it important to use random assignment when determining which research participants will comprise the different treatment
    12·1 answer
  • For this scenario related to turtle drawing, indicate whether it is better to write a loop or a function (or a set of functions)
    13·1 answer
  • _____ involves storing data and running applications outside the company’s firewall. answer grid computing parallel computing cl
    11·1 answer
  • Does anyone know a working free spotify premium on ios 2021 plz i have had any luck finding anything:(​
    15·2 answers
  • Tools used to type text on Ms paint​
    12·1 answer
  • A central issue of public sharing is:
    13·2 answers
  • Write code to define a function named mymath. The function has three arguments in the following order: Boolean, Integer, and Int
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!