B. You are given a pyramid of boxes each of which contains a number. You start...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
B. You are given a pyramid of boxes each of which contains a number. You start at one at the top and at each step you move to the level below in one of the adjacent boxes. Your goal is to find the path with minimum sum of entries. For example, in the image below the largest sum is achieved by the path shown: 3 5 7 6 2 3 4 1 3 (i) Find a counterexample for each of the following greedy algorithms: Start from the root and always follow the smallest value. Start from the bottom and always follow the smallest value. Start from the root and always choose the next step that would give the optimal path when looking at most two steps ahead. [5 marks] [5 marks] (ii) Design an algorithm to efficiently solve this problem and give pseudocode for your algorithm, explaining clearly which algorithmic principles you are using. [5 marks] [15 marks] (iii) Argue about correctness of your algorithm and determine the time and space complexity. [10 marks] B. You are given a pyramid of boxes each of which contains a number. You start at one at the top and at each step you move to the level below in one of the adjacent boxes. Your goal is to find the path with minimum sum of entries. For example, in the image below the largest sum is achieved by the path shown: 3 5 7 6 2 3 4 1 3 (i) Find a counterexample for each of the following greedy algorithms: Start from the root and always follow the smallest value. Start from the bottom and always follow the smallest value. Start from the root and always choose the next step that would give the optimal path when looking at most two steps ahead. [5 marks] [5 marks] (ii) Design an algorithm to efficiently solve this problem and give pseudocode for your algorithm, explaining clearly which algorithmic principles you are using. [5 marks] [15 marks] (iii) Argue about correctness of your algorithm and determine the time and space complexity. [10 marks]
Expert Answer:
Related Book For
Introduction to Data Mining
ISBN: 978-0321321367
1st edition
Authors: Pang Ning Tan, Michael Steinbach, Vipin Kumar
Posted Date:
Students also viewed these programming questions
-
Date Level SLOPE CURVATURE SLOPE CURVATURE 9/26/2008 2.14% 3.64% 2.04% 1.57% 9/10/2008 2.40% 2.07% 0.59% -0.06% 8/25/2008 2.51% 2.13% 0.63% -0.09% 8/11/2008 2.69% 2.22% 0.78% -0.19% 7/25/2008 2.75%...
-
Discuss which organizational structure (i.e. functional, product-market divisional, matrix) you would recommend Guelph General Hospital implement, assuming the hospital moves forward with the...
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
If the resultant force acting on the hook is F R = {? 200i + 800j + 150k} lb, determine the magnitude and coordinate direction angles of F. 30 F= 600 ib
-
Let T: be the linear transformation such that T(e1) and T(e2) are the vectors shown in the figure. Using the figure, sketch the vector T(2,1). Tie2 T(e)
-
Solve the optimization problem using SA \[\min f(X)=100\left(x_{1}^{2}+x_{2} ight)^{2}+\left(1-x_{1} ight)^{2}\] subject to $X \in[0,7]$
-
On the Internet find the KPMG India Fraud Survey Report, 2002. a. How many chief executive officers re- ceived the questionnaire? b. How many of the respondents do not have a written fraud policy? c....
-
Presented below are a series of unrelated situations. 1. Spock Company's unadjusted trial balance at December 31, 2008, included the following accounts. Spock Company estimates its bad debt expense...
-
Access and print all necessary forms and schedules from the IRS webpage (www.irs.gov (Links to an external site.)) or from Canvas, review and prepare a joint Form 1040 (Federal Income Tax return)...
-
of Aston Bridge Inc., is a food manufacturing company specializing products is based in the United States. Its sales have seen a minimal increase of 5% over the last 5 years and the company is...
-
Boys get more attention in the classroom than girls. There's no doubt about it. Reams of studies show that teachers, from preschool to grade school, interact more with males than females. Especially...
-
1)XYZ Inc. is evaluating the purchase of a new machine.The cost of the machine is $500.The incremental cash flows due to the machine are expected to be as follows: Year 1$150 Year 2$200 Year 3$250...
-
Calculate the following reel integrals by using a given contour in the complex domain. (Hint: The contour is the semi circle with radius R, when R o. Think that the result of contour equals result of...
-
You are the HR Director for a large manufacturing organization with plants located across the United States. About half are currently unionized, however your plant is not unionized. One of the goals...
-
XYZ Corporation started three years ago. Operations were smooth until December 20 of this year, when their cost accountant, named Cutie Pie, went AWOL (absence without leave). The management was...
-
Farmer Giles opens part of his farm as a children's farm, where children can meet and hold small animals and learn about farm life. The children's farm is in a separate area of the farm, with 6 foot...
-
Feller Company purchased a site for a limestone quarry for $100,000 on January 2, 2019. It estimate that the quarry will yield 400,000 tons of limestone. It estimates that its retirement obligation...
-
You are given a set of m objects that is divided into K groups, where the ith group is of size mi. If the goal is to obtain a sample of size n < m, what is the difference between the following two...
-
Draw all candidate subgraphs obtained from joining the pair of graphs shown in Figure 7.2. Assume the edge-growing method is used to expand the subgraphs.
-
The RIPPER algorithm (by Cohen [1]) is an extension of an earlier algorithm called IREP (by F¨urnkranz and Widmer [3]). Both algorithms apply the reduced-error pruning method to determine whether...
-
On May 20, 2016, when the spot rate is \($1.28/,\) a U.S. company buys merchandise from a supplier in Italy, at a cost of 100,000. The spot rate is \($1.25/\) on June 30, the companys year-end....
-
On November 15, 2016, a U.S. company takes delivery of merchandise costing C\($1,000,000\) from a Canadian supplier and records an account payable. On the same date, the company enters a forward...
-
On April 10, 2016, when the spot rate is \($1.30/,\) a U.S. company sells merchandise to a customer in Italy. The spot rate is \($1.31/\) on June 30, the companys year-end. Payment of 100,000 is...
Prolific Hustle Turn Your Pain To Passion And Profits 1st Edition - ISBN: 979-8388823489 - Free Book
Study smarter with the SolutionInn App