6. Houston, we have a problem! Alina and Kaitlyn decide to make the drive from Ann...

Transcribed Image Text:

6. Houston, we have a problem! Alina and Kaitlyn decide to make the drive from Ann Arbor to Houston to cheer on the Wolverines at the College Football National Championship Game! They start their drive from Ann Arbor and make their way to Houston. Along their journey, there are n hotels, located at positive distances a < a2 < < an from Ann Arbor. They can stop only at these specified hotels, but may choose which one(s) to spend their night(s) at, and which ones to skip. They must end their journey at the last hotel, located at distance an. The trip from Ann Arbor to Houston is 1300 miles. They don't want to drive too much or too little in a day, so they are aiming to go about 500 miles per day. However, due to the distance between the hotels, this may not always be possible. If they drive miles on a given day, they will face a "penalty" of (500 - x) for that day. For example, if a 450, a2 = 670, a3 = 1300, then we have the following possible choices of hotels (by their indices) and the associated penalties: 1, 2, 3 (500 450) + (500 220) + (500 630) 2,3 (500 - 670) + (500 - 630) 1,3 (500 450) + (500 - 850) (500 - 1300) 3 97800 = 45800 = 125000 = 640000 = Therefore, the minimum possible total penalty is 45,800. Alina and Kaitlyn should drive to the second hotel (at 670 miles) on the first day, then drive the remaining 630 miles to Houston on the second day. The goal in this problem is to devise an efficient algorithm that, given an array A[1...n] of the distances a,..., an, determines which hotel(s) to stop at so as to minimize the total penalty incurred on the trip. Hint: Consider a function p(j) that represents the minimum possible total penalty when start- ing from Ann Arbor and ending at hotel j. Solution: (a) Give, with justification, a recurrence relation for p(j) that is suitable for a dynamic- programming solution to the problem. Be sure to identify the base case(s). (b) Give pseudocode for a (bottom-up) dynamic programming algorithm that solves the prob- lem, and analyze its running time. 6. Houston, we have a problem! Alina and Kaitlyn decide to make the drive from Ann Arbor to Houston to cheer on the Wolverines at the College Football National Championship Game! They start their drive from Ann Arbor and make their way to Houston. Along their journey, there are n hotels, located at positive distances a < a2 < < an from Ann Arbor. They can stop only at these specified hotels, but may choose which one(s) to spend their night(s) at, and which ones to skip. They must end their journey at the last hotel, located at distance an. The trip from Ann Arbor to Houston is 1300 miles. They don't want to drive too much or too little in a day, so they are aiming to go about 500 miles per day. However, due to the distance between the hotels, this may not always be possible. If they drive miles on a given day, they will face a "penalty" of (500 - x) for that day. For example, if a 450, a2 = 670, a3 = 1300, then we have the following possible choices of hotels (by their indices) and the associated penalties: 1, 2, 3 (500 450) + (500 220) + (500 630) 2,3 (500 - 670) + (500 - 630) 1,3 (500 450) + (500 - 850) (500 - 1300) 3 97800 = 45800 = 125000 = 640000 = Therefore, the minimum possible total penalty is 45,800. Alina and Kaitlyn should drive to the second hotel (at 670 miles) on the first day, then drive the remaining 630 miles to Houston on the second day. The goal in this problem is to devise an efficient algorithm that, given an array A[1...n] of the distances a,..., an, determines which hotel(s) to stop at so as to minimize the total penalty incurred on the trip. Hint: Consider a function p(j) that represents the minimum possible total penalty when start- ing from Ann Arbor and ending at hotel j. Solution: (a) Give, with justification, a recurrence relation for p(j) that is suitable for a dynamic- programming solution to the problem. Be sure to identify the base case(s). (b) Give pseudocode for a (bottom-up) dynamic programming algorithm that solves the prob- lem, and analyze its running time.