Given a set of n weights (ww) and a rod of length n-1 inches, we can...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Given a set of n weights (ww) and a rod of length n-1 inches, we can attach the weights to the rod at hooks placed at one inch distances apart as shown in the figure below. 10 2 3 12 2 We can attach a weight to any hook but no two weights can be attached to the same hook and we have to attach all the weights. For any given assignment of weights to hooks, we can compute the location of the center of mass of the rod and the weights according to the following equation (neglecting the weights of the rod and the hooks). P c= where 0 p n-1 is the position of weight i along the rod. For example, in the figure shown above, the center of mass is computed as 10-0+2-1+3-2+4-3+12-4+2-5 78 = = 2.36 33 10+2+3+4+12+2 The problem is to find an assignment of weights to hooks that makes the center of mass as far as possible to the left, i.e.,. minimize the value of c. 1. (1 point) Describe a greedy algorithm that finds the assignments that minimizes the value of c. 2. (1 point) Write a pseudo-code for your algorithm. 3. (1 points) Establish the running time of your algorithm. 4. (3 points) Prove the optimality of your algorithm. Given a set of n weights (ww) and a rod of length n-1 inches, we can attach the weights to the rod at hooks placed at one inch distances apart as shown in the figure below. 10 2 3 12 2 We can attach a weight to any hook but no two weights can be attached to the same hook and we have to attach all the weights. For any given assignment of weights to hooks, we can compute the location of the center of mass of the rod and the weights according to the following equation (neglecting the weights of the rod and the hooks). P c= where 0 p n-1 is the position of weight i along the rod. For example, in the figure shown above, the center of mass is computed as 10-0+2-1+3-2+4-3+12-4+2-5 78 = = 2.36 33 10+2+3+4+12+2 The problem is to find an assignment of weights to hooks that makes the center of mass as far as possible to the left, i.e.,. minimize the value of c. 1. (1 point) Describe a greedy algorithm that finds the assignments that minimizes the value of c. 2. (1 point) Write a pseudo-code for your algorithm. 3. (1 points) Establish the running time of your algorithm. 4. (3 points) Prove the optimality of your algorithm.
Expert Answer:
Answer rating: 100% (QA)
1 Greedy Algorithm Description Sort the weights in nondecreasing order Start with an empty rod and p... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
(iii) Now express your decision rule instead using only the quantities p(Ck), p(Cj ), p(x|Ck), p(x|Cj ), and relate it to the diagram above. [2 marks] (iv) If the classifier decision rule assigns...
-
Define the contextual-equivalence relation ` M =ctx M0 : for pairs of PCF terms M, M0 , PCF types , and PCF type environments . [3 marks] (ii) For PCF terms M and N with respective typings ` M : and...
-
Reid Corporation's balance sheet at January 1, 20X9 reflected the following balances: Cash & Receivables $ 30,000 Inventory $ 75,000 Land $125,00 Building & Equipment (net) $850,000 Common Stock...
-
How can verbal feedback affect customer encounters?
-
The table that follows lists four pairs of initial and final angles of a wheel on a moving car. The elapsed time for each pair of angles is 2.0 s. For each of the four pairs, determine the average...
-
What is the As-Verified Configuration, and when is it established?
-
Nick Cola Corporation produces a new soft drink brand, Sweet Spring, using two production departments: mixing and bottling. Nicks beginning balances and data pertinent to the mixing departments...
-
Assume that you are the portfolio manager of the TTY Fund, a $5 million hedge fund that contains the following stocks. The required rate of return on the market is 12.00% and the risk-free rate is...
-
Explore the Types of Aid links (Federal and DSC pages) found on the Online Lecture page. Describe the differences between the types of aid and how each can assist with college costs.
-
REI sells snowboards. Assume the following information relates to REI's purchases of snowboards during September. During the san month, 106 snowboards were sold. REI uses a periodic inventory system....
-
(a) During lunch hour, arrivals of customers at a pizza hut restaurant follows a Poisson process with the rate of 120 customers per hour. The restaurant has one line, with three workers taking food...
-
Compute the cost assigned to ending inventory using ( a ) FIFO, ( b ) LIFO, ( c ) weighted average, and ( d ) specific identification. For specific identification, units sold include 8 5 units from...
-
What role does the cellular microenvironment play in the progression of metastatic cancer, and how do tumor cells interact with stromal cells, the extracellular matrix, and immune cells to facilitate...
-
Flint Ltd. issued a $1,010,000, 10-year bond at par on January 1, 2023. The bond paid 11% interest each January 1 and July 1. The company's year end was December 31. Prepare the journal entries to...
-
President Obama and the Republicans in Congress have different proposals to increase employment throughout the US? Consider this issue from both the perspective of government regulation and free...
-
A circular concrete shaft liner with Youngs modulus of 3.4 million psi, Poissons ratio of 0.25, unconfined compressive strength 3,500 psi and tensile strength 350 psi is loaded to the verge of...
-
What are vertical and horizontal financial statement analyses? What are their advantages?
-
Which form of financing requires repayment, regardless of whether the company receiving the funds does well or not? a. A loan b. An investment c. Both a loan and an investment d. Neither a loan nor...
-
Which form of financing allows the source of the funds to share in the wealth if the company which received the financing does well? a. A loan b. An investment c. Both a loan and an investment d....
Study smarter with the SolutionInn App