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
(NumberFormatException)Write the bin2Dec(String binaryString) method to convert a binary string into a decimal number. Implement
tresset_1 [31]

The following program will be used that prompts the user to enter a binary number as a string and displays decimal equivalent of the string.

<u>Explanation:</u>

NumberFormat.java

import java.util.Scanner;

public class NumberFormat{

public static void main(String[] args) {

      Scanner scan = new Scanner(System.in);

      try{

      System.out.println("Enter a binary string:");

      String s = scan.next();

      int integerValue = bin2Dec(Integer.parseInt(s));

      System.out.println("The decimal value of "+s+" is "+integerValue);

      }

      catch(NumberFormatException e){

          System.out.println(e);

      }

  }  

  public static int bin2Dec(int binaryNumber) throws NumberFormatException{

  int decimal = 0;

  int p = 0;

  try{

  while(true){

  if(binaryNumber == 0){

  break;

  } else {

  int temp = binaryNumber%10;

  decimal += temp*Math.pow(2, p);

  binaryNumber = binaryNumber/10;

  p++;

  }

  }

  }

  catch(NumberFormatException e){

      throw new NumberFormatException("Invalid binary number");

  }

  return decimal;

  }

}

Output:

Enter a binary string:

1011000101

The decimal value of 1011000101 is 709

5 0
2 years ago
The hostel in which you plan to spend the night tonight offers very interesting rates, as long as you do not arrive too late. Ho
faust18 [17]

Answer:

Answered below

Explanation:

// Python implementation

incrementAmount = 5

basePrice = 10

price = 0

arrivalHour = int(input("Enter arrival hour 0-12: ")

if arrivalHour < 0 or arrivalHour > 12:

print ("Invalid hour")

if arrivalHour == 0:

price = basePrice

else:

price = arrivalHour * incrementAmount

totalPrice = price + basePrice

if totalPrice > 53:

totalPrice = 53

print ("Your bill is $totalPrice")

4 0
2 years ago
Go to the Creamy Ice Corporation passage on the next page. Insert the trademark sign after the word “Corporation'' in the first
GuDViN [60]

Answer:

v

Explanation:

because it is

5 0
2 years ago
You and your friend who lives far away want to fairly and randomly select which of the two of you will travel to the other’s hom
Phantasy [73]

Answer:

c. your friend can hash all possible options and discover your secret.

Explanation:

SHA-256 is a set of hash functions that was designed by the NSA. SHA-2 is considered an upgrade on the set that was its predecessor, SHA-1. A hash is a mathematical function that condenses data in a process of one-way encryption. SHA-256 creates hash algoritms that are considered irreversible and unique. However, one of the properties of hashing algorithms is determinism, which means that any computer in the world would be able to compute a particular hash and get the same answer.

6 0
2 years ago
What is wrong with line 1?
Gelneren [198K]

Answer:

The set is a object of the class 'H' and the setY method is a member of G class which is not called by the object of H class.

Explanation:

  • If a user calls the G function which is not a private by the help of H class objects then it can be called. It is because all the public and protected methods of A class can be accessed by the B class if B extends the A-class.
  • If any class is extended by the other class then the derived class holds the property of the base class and the public and protected method can be accessed by the help of a derived class object.
  • The derived class object can be created by the help of base class like written in the "line 1".
  • But the base class can not call the member of the derived class.
5 0
2 years ago
Other questions:
  • Mary can view the thumbnails of her presentation slides when she is creating the slides. Which element of the program’s interfac
    5·2 answers
  • In an ethernet network, the signal that is sent to indicate a signal collision is called a ________ signal.
    7·1 answer
  • Which process is used to protect transmitted data in a vpn?
    12·1 answer
  • Zoey has brought her computer in for servicing. When she dropped off her computer, she mentioned that her computer will sometime
    15·2 answers
  • Consider an application that transmits data at a steady rate (for example, the sender generates an N-bit unit of data every k ti
    8·1 answer
  • Write a program that prints the U.S. presidential election years from 1792 to present day, knowing that such elections occur eve
    9·1 answer
  • A _________________________ can use SOAP headers to carry meta information in its messages. A. Web service B. REST Service C. Co
    14·1 answer
  • 3. Personal Trainer is very concerned about the security and protection of the information they collect in the new information s
    10·1 answer
  • Describe the indicators and hazards of a metal deck roof fire in an unprotected steel joist warehouse as well as the techniques
    6·1 answer
  • Create a stored procedure named prc_inv_amounts to update the INV_SUBTOTAL, INV_TAX, and INV_TOTAL. The procedure takes the invo
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!