M8 GHW

.jpeg

School

Arizona State University *

*We aren’t endorsed by this school

Course

100

Subject

Electrical Engineering

Date

Feb 20, 2024

Type

jpeg

Pages

Uploaded by DeaconRiver11641 on coursehero.com

ASUHome MyASU Colleges & Schools Map & Locations Contact Us 2021Fall-T-CSES51-97519 > Quizzes > Module 8 Graded Homework @ 2021 Fall ¢ MOdU'e 8 Graded Homework AV Submission Details: Account Home T SyNabise Due Nov 29,2021 at 11:59pm Points 5 Questions 5 Time: 2minutes Dashbosrd Available Nov 6, 2021 at 12am - Jan 13 at 11:59pm 2 months Time Limit None Current Score: 5outof 5 Announcements s Kept Score: Soutof 5 Courses |°'"ms Instructions Assignments Suppose you're acting as a consultant for the Port Authority of a small Pacific Rim nation. They're currently doing a Discussions multi-billion-dollar business per year, and their revenue is constrained almost entirely by the rate at which they can unload ships that arrive in the port. Modules Here's a basic sort of problem they face. A ship arrives, with n con- tainers of weight w1, w2, . . ., wn. Standing on the Orades dock is a set of trucks, each of which can hold K units of weight. (You can assume that K and each wi is an integer) People You can stack multiple containers in each truck, subject to the weight restriction of K; the goal is to minimize the number of trucks that are needed in order to carry all the containers. This problem is NP-complete (you don't have to prove this) A greedy algorithm you might use for this is the following. Start with an empty truck, and begin piling containers 1,2, 3, into it until you get to a container that would overflow the weight limit. Now declare this truck “loaded” and send it off; then continue the process with a fresh truck. This algorithm, by considering trucks one at a time, may not achieve the most efficient way to pack the full set of containers into an available collection of trucks. a.) Give an example of a set of weights, and a value of K, where this algorithm does not use the minimum possible number of trucks. b) Show, however, that the number of trucks used by this algorithm is within a factor of 2 of the minimum possible number, for any set of weights and any value of K. This quiz was locked Jan 13 at 11:59pm. Attempt History Attempt Time Score LATEST Attempt 1 2minutes Soutof 5 Score for this quiz: 5 out of 5 Submitted Nov 29, 2021 at 10:01pm This attempt took 2 minutes. Question 1 1/1pts Regarding part a. of the prompt, which of the following is a valid counterexample to the notion that the greedy algorithm described is optimal? Responses are given in the form of a set of item weights and a truck capacity K. 20200 Ke2 Question 2 1/1pts If W is the sum of all weights in the set of weights {w_1,..,w_n}, identify which of the following expressions represents a lower bound of the number of trucks necessary to fit all n items in terms of W and K. Question 3 1/1pts For part b. of the prompt, the remaining questions of this quiz will guide you through the proof strategy. The first part of the proof is as follows: Suppose the number of trucks is the odd number m=2q+1 for some qin {0,1,2,...}, and we denote the set of trucks as {t_1,t_2,...,t_m}. We then divide the trucks into consecutive groups of 2 such that group 1 is {t_1,t_2}, group 2 is {t_3_4} and s0 on until the last group consists only of {t_m}, which is necessary since the total number of trucks is odd. In this construction, which of the following expressions represents the total number of groups created in terms of q? K Question 4 1/1pts Continuing from question 3, consider all groups except the last group that contains only one truck. We note that for any fixed truck group of these remaining groups, the combined weight of both trucks must be at least K, else the greedy algorithm would not have required splitting the items between these two trucks. Which of the following expressions does this observation imply? EE Question 5 1/1pts Use your results from questions 2 through 4 to finish the proof. Which of the following statements completes the proof? (Exercise: use a similar argument to show this is true for an even number of trucks) Thus, the optimum solution uses at least q+1 trucks, which is at least half the number of trucks greedy uses. Quiz Score: 5 out of 5 « Previous Next »

Discover more documents: Sign up today!

Unlock a world of knowledge! Explore tailored content for a richer learning experience. Here's what you'll get: