Question on greedy algorithm. A sculptor starts with n metal pieces which are to be pairwise...

Question on greedy algorithm.

A sculptor starts with n metal pieces which are to be pairwise forged together until one piece (the sculpture) emerges. The forging process melds two pieces into one with an energy cost directly proportional to the product of the sizes of the two pieces forged together. For example, melding three pieces of sizes x, y and z could be done in different orders, yielding different costs ( x*y + x*y*z OR x*z + x*z*y OR y*z + y*z*x). Write the C-like pseudocode needed to determine the cheapest order of pairwise forging and analyze the complexity of your code.

Expert Solution

The solution is sketched in the pictures below.The solution shows a Greedy approach to solve the problem which ultimately leads to sorting the metal pieces according to their sizes.The Time Complexity of the algorithm is thus O(N.logN).

venereology answered 1 year ago

A machine produces metal pieces that are cylindrical in shape. A sample of these pieces is...

A machine produces metal pieces that are cylindrical in shape. A sample of these pieces is taken and the diameters are found to be 1.02, 0.95, 1.03, 1.07, 0.98, 0.98, 0.99, 1.01, and 1.06 centimeters. Compute the sample mean x, the sample standard deviation s and the median of the sample. Determine the 95% confidence interval for the mean. Assume an approximately normal distribution for the diameter random variable. (Hint: Use the t–distribution.)

Give a greedy algorithm to make a reasonable attempt at coloring a graph in ?(? +...

Give a greedy algorithm to make a reasonable attempt at coloring a graph in ?(? + ?) time. In pseudo code

A machine is producing metal pieces that are cylindrical in shape. A sample of 12 pieces...

A machine is producing metal pieces that are cylindrical in shape. A sample of 12 pieces is taken and the diameters are: 1.01, 0.97, 1.03, 1.04, 0.8, 0.78, 1.06, 0.95, 0.87,1.0,0.88 and 0.90 centimeters. a. Find 98% confidence interval for the true average diameter of metal pieces produced by the machine. We would like to test whether the true average diameter of metal pieces produced by the machine is less than 1 centimeter. b. Assuming the population distribution is approximately...

Code in C# please. Write a program that will use the greedy algorithm. This program will...

Code in C# please. Write a program that will use the greedy algorithm. This program will ask a user to enter the cost of an item. This program will ask the user to enter the amount the user is paying. This program will return the change after subtracting the item cost by the amount paid. Using the greedy algorithm, the code should check for the type of bill. Example: Cost of item is $15.50 User pays a $20 bill $20...

Give an example that shows the greedy algorithm for activity selection that picks the activity with...

Give an example that shows the greedy algorithm for activity selection that picks the activity with the smallest start time first (and continues in that fashion) does not solve the activity selection problems correctly. Please show your work! I will rate quality answers. Thank you.

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a)...

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3

What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in...

What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in an optimal substructure.

1. A machine produces metal pieces that are cylindrical in shape. A sample of 36 metal...

1. A machine produces metal pieces that are cylindrical in shape. A sample of 36 metal pieces is taken and the mean diameters for this sample was 6.21 centimeters. In addition from previous studies it is know that the population is approximately Normal with a standard deviation 1.84centimeter. Note: Do the calculations by hand, but show the R code and output for the z-value, t-value or for finding area under the standard normal curve. Note: Round your numbers to exactly...

java code for scheduling problem (start time,end time , profite) using greedy algorithm

Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory,...

Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory, Algorithms, and Systems.)

Question