answer.
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]
2 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]2 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
A school principal trying to find out if parents will help buy new playground equipment shows digital leadership by.
ELEN [110]

Answer:

D. is the correct answer!

8 0
2 years ago
Read 2 more answers
In three to five sentences, explain how you would insert graphics using your word-processing software.
madam [21]
Most word-processing programs allow the user to select a command from the menu to insert a graphic. Clicks in the document where you want your file, choose insert and picture click from file select the image the press open and you picture will become inserted in to the document.
3 0
2 years ago
Read 2 more answers
An array of ints, arr, has been declared and initialized. Write the statements needed to reverse the elements in the array. So,
Yuki888 [10]

Answer:

The sample output is below.

The code is attached.

Explanation:

Sample Output:

Original array is: 1 2 457 4 Reversed array is: 4754 2 1

Code to copy:

import java.io.*;

class Main

{

    /*Define the function revArray passing the array

      and its indices.*/

    static void revArray(int arr[], int start, int end)

    {

         /*Declare an integer variable to store the

           first index.*/

         int temp;

         //Check if array is empty.

         if (start >= end)

             return;

         //Store the first index value.

         temp = arr[start];

         //Swap the last index to first index.

         arr[start] = arr[end];

         //Store the temp value to last index.

         arr[end] = temp;

         /*Call the function recursively to swap

           rest of the values.*/

         revArray(arr, start+1, end-1);

    }  

    public static void main (String[] args)

    {

         //Declare and initialize array.

         int[] arr = {1,2,4,5,7,4};

         /*Declare an integer variable to store the

         * length of array.

         */

         int count=0;

         //Set the length of array to count.

         for(int i=0;i<arr.length;i++)

             count++;

         System.out.println("Original array is:");

         ///Print the original array.

         for(int i=0; i<count;i++)

         {

             System.out.print(arr[i]+" ");

         }  

         /*Call the function to reverse the values in

         * the array itself.

         */

         revArray(arr, 0, count-1);

         System.out.println("\nReversed array is:");

         ///Print the reversed array.

         for(int i=0; i<count;i++)

         {

             System.out.print(arr[i]+" ");

         }  

    }

}

5 0
2 years ago
The height of a small rocket y can be calculated as a function of time after blastoff with the following piecewise function: y 5
SOVA2 [1]

Answer:

High level Language

understand

Explanation:

rocket is 0...4433456u888

5 0
1 year ago
FOREACH, EXPLODE and MAIL are examples of crazy functions.
jenyasd209 [6]
The answer would be B
4 0
2 years ago
Other questions:
  • Susan needs to change the color scheme in all the slides of her multimedia presentation. The presentation software program Susan
    10·2 answers
  • Which of the following statements is not true about proper tire care? a.If you see a wear bar across the width of the tread whil
    14·2 answers
  • A major weakness of a lot of file processing systems is that ____.
    10·1 answer
  • Kleene star of {1} generates {1, 11, 111, 1111, 11111……}.<br> True<br> False
    12·1 answer
  • In the game of $Mindmaster$, secret codes are created by placing pegs of any of seven different colors into four slots. Colors m
    5·1 answer
  • The term that refers to the programmer reading the program from the beginning and stepping through each statement is _________.
    5·1 answer
  • SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA. Assume that the classes listed in the Java Quick R
    9·1 answer
  • In below freezing conditions, keep your fuel level at least _________ full to keep moisture from freezing in your gas line.
    13·1 answer
  • Which is true regarding pseudocode
    8·1 answer
  • A(n) ___________________ is a set of characters that the originator of the data uses to encrypt the text and the recipient of th
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!