2. Dynamic Programing - City Planning. (10 points): A city planner is asked to organize grocery...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
2. Dynamic Programing - City Planning. (10 points): A city planner is asked to organize grocery shops in a new city. The city has a straight line main street that goes throughout the city. The city planner is asked to position where should the city provide permits to build new grocery shops so that people of the new city can have the shortest distance to their grocery markets. The population density is not constant along both sides of the main street. A higher density is around multiple city centers or crossroads along side the main street. Your task is to develop an algorithm, given the positions of the city centers and the number of grocery shops, computes the least possible sum of all distances between each city centers and its nearest grocery shop. Input to your Algorithm: 1. List of city centers coordinate positions along the main street (each an integer number between 1 and 1000). This is a sequence of numbers. 2. Number of city centers is an integer between 2 and 100. 3. Number of grocery shops (an integer number between 2 and 30). 4. The number of shops is smaller than the number of city centers. Output of your algorithm: A single integer, which is the sum of all distances between each city center and its nearest grocery market. Sample Input: 5 [123679 11 21 40 50] Sample Output: 9 Positions City Centers Grocery Shops 1 2 3 *** 1 S1 4 5 6 7 * * 8 9 10 11 12 13 14 21 * * * 32 S 2 S 40 * S *** 60 * S Figure 1: A visualization of City Center Positions and Grocery Shops. (Numbers in grocery shop row is the distance to the nearest shop. ) Tasks: • Task 2.1. What are the sub-problems in this case? What is the counts of sub-problems? Provide a brief description of your solution. (2 points) • Task 2.2. Write up your algorithm in Pseudocode or python implementation. (6 points) • Task 2.3. What is the run time complexity of your algorithm? (2 points) 2. Dynamic Programing - City Planning. (10 points): A city planner is asked to organize grocery shops in a new city. The city has a straight line main street that goes throughout the city. The city planner is asked to position where should the city provide permits to build new grocery shops so that people of the new city can have the shortest distance to their grocery markets. The population density is not constant along both sides of the main street. A higher density is around multiple city centers or crossroads along side the main street. Your task is to develop an algorithm, given the positions of the city centers and the number of grocery shops, computes the least possible sum of all distances between each city centers and its nearest grocery shop. Input to your Algorithm: 1. List of city centers coordinate positions along the main street (each an integer number between 1 and 1000). This is a sequence of numbers. 2. Number of city centers is an integer between 2 and 100. 3. Number of grocery shops (an integer number between 2 and 30). 4. The number of shops is smaller than the number of city centers. Output of your algorithm: A single integer, which is the sum of all distances between each city center and its nearest grocery market. Sample Input: 5 [123679 11 21 40 50] Sample Output: 9 Positions City Centers Grocery Shops 1 2 3 *** 1 S1 4 5 6 7 * * 8 9 10 11 12 13 14 21 * * * 32 S 2 S 40 * S *** 60 * S Figure 1: A visualization of City Center Positions and Grocery Shops. (Numbers in grocery shop row is the distance to the nearest shop. ) Tasks: • Task 2.1. What are the sub-problems in this case? What is the counts of sub-problems? Provide a brief description of your solution. (2 points) • Task 2.2. Write up your algorithm in Pseudocode or python implementation. (6 points) • Task 2.3. What is the run time complexity of your algorithm? (2 points)
Expert Answer:
Answer rating: 100% (QA)
Task 21 What are the subproblems in this case What is the counts of subproblems Provide a brief description of your solution In this problem the subproblems would be finding the nearest grocery shop f... View the full answer
Related Book For
Statistics For Business And Economics
ISBN: 9780132745659
8th Edition
Authors: Paul Newbold, William Carlson, Betty Thorne
Posted Date:
Students also viewed these algorithms questions
-
The norm of a linear transformation TA: Rn Rn can be defined by where the maximum is taken over all nonzero x in Rn. (The subscript indicates that the norm of the linear transformation on the left is...
-
17. What is the mass percent (%) for O in SO2? (b) 45.41 (a) 38.09 (c) 50.00 (d) 53.86 (e) 56.43 18. Which of the following is the empirical formula? (a) CSH18 (c) C4H1002 Hint: Empirical formula is...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Your input file contains sentences. A sentence contains words seperated with one space or more spaces. And a sentence ends with a "." Symbol. Write appropriate lex code to create desired outputs....
-
Imagine that you are the head coach of a college sports team. One of your most important objectives is to win as many games as possible. Describe some controls that you would implement to help...
-
Find a maximum flow for the network shown in Fig. 13.23. The capacities on the undirected edges indicate that the capacity is the same in either direction. [However, for an undirected edge a flow can...
-
Why can subject matter jurisdiction never be waived by the defendant?
-
Minott Jewelers, Ltd., purchased store fixtures, display cases, and a maximum-security commercial safe for a lump-sum price of $14,000 from a bankrupt competitor. Appraised values were as follows:...
-
Let u= (3, 5, 1) and v = (2, -2, 3). Find 8u + 7v = i 8u + 7v. i ).
-
Cary Company manufactures two models of industrial componentsa Standard model and an Advanced Model. It has provided the following information with respect to these two products: Standard Advanced...
-
Required information [The following information applies to the questions displayed below.] George and Wanda received $30,500 of Social Security benefits this year ($11,700 for George; $18,800 for...
-
A shaft made of mild steel is keyed to a cone clutch assembly. If it has a 2.5 IN diameter and rotates at 1375 RPM. What will be the contact surface size in (MM) if the shaft can take up 5 times its...
-
What should an employee do if they believe they have been subjected to workplace harassment?
-
What is the price of a bond with a coupon rate of 5%, payable semi-annually, a face value of $1000, 15 years to maturity, and a yield to maturity of 4.7%? Enter your response below. Enter your answer...
-
188. Which one of the following is not a vestigial organ? (1) Coccyx (2) Body hairs (3) Auricular muscles (4) Nipples in female 189. What is the sequence in the evolution of mammals? (1) Fish...
-
6. The depth of the water at the end of the Cocoa Beach Pier varies with the tide on any given day. Suppose the high tide occurs at 5:00 a.m. and the depth of the water is 15.0 feet) then low tide...
-
Three kinds of networks build an organization's social capital and help it grow and active impact. What are they? a. Political networks. B. bonding networks. C. Legal networks. D. Bridging networks...
-
Suppose the index goes to 18 percent in year 5. What is the effective cost of the unrestricted ARM?
-
The Department of Transportation wishes to know if states with a larger percentage of urban population have higher rates of automobile and pickup crash deaths. In addition, it wants to know if either...
-
A random variable X is normally distributed with a mean of 100 and a variance of 100, and a random variable Y is normally distributed with a mean of 200 and a variance of 400. The random variables...
-
A corporation regularly takes deliveries of a particular sensitive part from three subcontractors. It found that the proportion of parts that are good or defective from the total received were as...
-
Identify three conditions that must exist before either difference or ratio estimation can be applied.
-
Define tolerable error.
-
Briefly describe the auditor's strategy when applying mean-per-unit (MPU) estimation.
Study smarter with the SolutionInn App