In stores, boxes should be placed in an organized way otherwise it will be messy. Given...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
In stores, boxes should be placed in an organized way otherwise it will be messy. Given a collection of boxes, it is requested to place them on top of each other to reach the minimum possible height. There is a condition, where a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box. It is allowed to rotate any box to use any two sides as its base. For example, consider below 4 boxes where each box has the following dimensions Input: Box 1: (2,1,3), Box 2:(6,3,8) Box 3: (4,2,5), Box 4:(3,1,6). Output: From bottom to top as follows: In the bottom → Box 2 on the base (6,8) and height 3, On top of it →→ Box 3 on the base (4,5) and height 2, Then → Box 4 on the base (6,3) and height 1, Finally → Box 1 on the base (2,3) and height 1. The total height is 7 [Explanation: as we can see that the first box in the bottom is the box 2 with base 6x8 and height 3, then box3 with base 4x5 and height 2, and so on. This arrangement of boxes fulfils the constraint mentioned above: "the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box". This solution also satisfies the shortest possible stack] a) Describe how a brute-force approach algorithm would solve the above problem (4 marks), and explain its complexity (2 marks). b) Design an algorithm to solve the above scenario for N boxes. (6 marks) [The efficiency of your algorithm is the main driver of the mark], and analyze the complexity of your solution. (2 marks) [full explanation of your answer should be provided] c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case] d) Prepare a brief report (250 words) comparing the two algorithms (6 marks) In stores, boxes should be placed in an organized way otherwise it will be messy. Given a collection of boxes, it is requested to place them on top of each other to reach the minimum possible height. There is a condition, where a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box. It is allowed to rotate any box to use any two sides as its base. For example, consider below 4 boxes where each box has the following dimensions Input: Box 1: (2,1,3), Box 2:(6,3,8) Box 3: (4,2,5), Box 4:(3,1,6). Output: From bottom to top as follows: In the bottom → Box 2 on the base (6,8) and height 3, On top of it →→ Box 3 on the base (4,5) and height 2, Then → Box 4 on the base (6,3) and height 1, Finally → Box 1 on the base (2,3) and height 1. The total height is 7 [Explanation: as we can see that the first box in the bottom is the box 2 with base 6x8 and height 3, then box3 with base 4x5 and height 2, and so on. This arrangement of boxes fulfils the constraint mentioned above: "the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box". This solution also satisfies the shortest possible stack] a) Describe how a brute-force approach algorithm would solve the above problem (4 marks), and explain its complexity (2 marks). b) Design an algorithm to solve the above scenario for N boxes. (6 marks) [The efficiency of your algorithm is the main driver of the mark], and analyze the complexity of your solution. (2 marks) [full explanation of your answer should be provided] c) Develop a python code to implement your efficient algorithm. (10 marks) [The marks depend on the correctness of the code, indentation, comments, test-case] d) Prepare a brief report (250 words) comparing the two algorithms (6 marks)
Expert Answer:
Answer rating: 100% (QA)
a A bruteforce approach algorithm would solve the above problem by generating all possible arrangements of the boxes and checking if each arrangement ... View the full answer
Related Book For
Posted Date:
Students also viewed these accounting questions
-
Given a collection of points (x1, y1). (x2 > y2),. . . . . . . . , (xn, yn)> let and let y = c0 + c1x be the linear function that gives the best least squares fit to the points. Show that if = 0 then...
-
A collection of five routers is to be connected in a point-to-point subnet. Between each pair of routers, the designers may put a high-speed line, a medium-speed line, a low-speed line, or no line....
-
Given a collection of particles with positions ri, let the force on the ith particle, due to all the others, be Finti . Assuming that the force between any two particles is directed along the line...
-
Find the smallest positive angle and the smallest negative angle (numerically) coterminal with but not equal to the given angle. 47.0
-
If you are a U.S. firm and owe someone 10,000,000 in 180 days, what is your transaction exchange risk?
-
An important part of the accounting for minority passive investments is the distinction between investments categorized as trading, available-for- sale, or he Id-to maturity. Required: 1. When a...
-
The Billboard Company has a deferred tax liability in the amount of \(\$ 14,000\) at December 31, 2020, relating to a \(\$ 40,000\) installment sale receivable, \(\$ 20,000\) of which is collected in...
-
Losses have been incurred at Millard Corporation for some time. In an effort to isolate the problem and improve the companys performance, management has requested that the monthly income statement be...
-
You analyze a leveraged buyout. The (LTM) EBITDA of the targetat the time of the buyout is $50M, and it is expected to grow at arate of 6% in each of the next 3 years. The PE firm intends toacquire 2...
-
There are only two risky assets (stocks) A and B in the market. Mean 20% B 10% The returns on the two assets have zero correlation. A Standard Deviation 10% 5% A. Assume that there is no risk-free...
-
Create a program that will scan all open ports (from 1 to 1024) of a computer (localhost or any computer within a network). *Make the first line in your main method with the statement: String host=...
-
Mary is reviewing the availability controls for the system architecture shown here. What technology is shown that provides fault tolerance for the database servers?
-
1- Describe one job that once existed but today is obsolete (or is slowly becoming obsolete) because of technology. 2- Define an Enterprise system and describe the uses and benefits of at least 2...
-
:06 Custom Company reports the following (partial) T-account activity at the end of its first year of operations. Factory Overhead Debit Credit 81,000 392,400 130,600 185,200 ces 1. Compute the...
-
Activity and selected costs for three production departments (Training, Independent, and Commercial) and two service departments (Accounting and Facilities) at DuBay Films for the past month follow:...
-
Consider the Verilog code below. Determine the function of this circuit. Rewrite the codeusing case statement, with z [ i ] declared as a vector.module prob 1 ( A , en , z 0 , z 1 , z 2 , z 3 )...
-
For this assignment, you may examine a toy marketed for infants (36 months and under ...you can tell the age range based on the packaging information) and determine how appropriate the toy is for...
-
H.J. Heinzs annual dividends were as follows: 1990 ..............$0.540 1991.............. 0.620 1992 .............. 0.700 1993.............. 0.780 1994 .............. 0.860 1995 .............. 0.940...
-
A spool consists of an axle of radius r and an outside circle of radius R which rolls on the ground. A thread is wrapped around the axle and is pulled with tension T, at an angle ? with the...
-
A beach ball is thrown upward with initial speed v0. Assume that the drag force from the air is F = mv. What is the speed of the ball, vf , when it hits the ground? (An implicit equation is...
-
In As frame, B moves to the right with speed u, and C moves to the left with speed v. What is the speed of B with respect to C? In other words, use 4-vectors to derive the velocity-addition formula.
-
1.12 Andreas Delon's Compensation. Andreas Delon is a French citizen who has been offered the position of CEO of LakePharma, a large French pharmaceuticals firm. LakePharma produces high-quality...
-
1.11 Peng Plasma Pricing. Peng Plasma is a privately held Chinese business. It specializes in the manufacture of plasma cutting torches. Over the past eight years, it has held the Chinese renminbi...
-
1.13 Euro Virtual's Consolidated Earnings. Euro Vir- tual pays different tax rates for each of its country operations. a. What are its earnings per share in euros after deducting taxes? b. What is...
Study smarter with the SolutionInn App