Computers and Technology, 05.06.2020 18:01, johnbobjones
You and Alice and Bob are driving to Tijuana for spring break in Bob’s car. You are savingyour money for the trip and so you want to minimize the cost of gas on the way. In order tominimize your gas costs you have compiled the following information.
First Bob’s car can reliably travelmmiles on a tank of gas (but no further). Alice has compiledgas-station data from the web and has plotted every gas station along your route along withthe price of gas at that gas station. Specifically Alice has created a list ofngas station prices P[1, ...,n], from closest to furthest, and a list of n distances D[1, ...,n] between two adjacentgas stations (the first distance is the distance from Bob’s house to the first gas station). Gasstation numbernis the closest gas station to your hotel in Tijuana. For convenience Alicehas converted thecost of gas into price per mile traveled in Bob’s carand also computed the 5 distance d(i, j)=∑jk=i+1D[k] the distance from gas stationito gas stationjfor 0≤i
Bob ensures you will begin your journey with a full tank of gas. You have decided to minimizethe number of stops byalways filling the tank full whenever you stop. Also when you get toTijuana youwill fill up for the return trip
1. Express this problem formally with input and output conditions.
2. Alice and Bob have ideas on how to minimize the cost of gas but they dis- agree. Bob suggests driving to the furthest gas station within m miles and filling up there. Help Alice show that his algorithm is not optimal by giving a counter example.
3. Alice suggest that if a greedy algorithm won't work maybe dynamic program- ming could help. Help Alice by stating a self-reduction for this problem.
4. State a dynamic programming algorithm based off of your self-reduction that computes the minimum gas cost.
5. What is the worst case run time of your dynamic programming algorithm?
6. Use your algorithm to compute minimum cost for the following lists of gas stations, distances and gas tank capacity.
Prices (cents per mile) [17,14,21,14,17,22,11,16,17,12,30, 25, 27,24,22,15,24,23,15,21]
Distances (miles) [24,31,42,31,33, 12, 34,55,25, 34, 64,24,13,52,33, 23, 64,43,25,15]
Your car can travel 150 miles on a tank of gas.
7. Bob notices that in your solution you always fill up at the cheapest gas station in range. He still thinks a greedy algorithm will work and suggests always filling up at the cheapest gas station within range. Show that this algorithm is not correct either.
Answers: 1
Other questions on the subject: Computers and Technology
Computers and Technology, 21.06.2019 23:30, soccerhannah290
Show that there is a language a ⚆ {0, 1} â— with the following properties: 1. for all x â a, |x| ≤ 5. 2. no dfa with fewer than 9 states recognizes a. hint: you don’t have to define a explicitly; just show that it has to exist. count the number of languages satisfying (1) and the number of dfas satisfying (2), and argue that there aren’t enough dfas to recognize all those languages. to count the number of languages satisfying (1), think about writing down all the strings of length at most 5, and then to define such a language, you have to make a binary decision for each string about whether to include it in the language or not. how many ways are there to make these choices? to count the number of dfas satisfying (2), consider that a dfa behaves identically even if you rename all the states, so you can assume without loss of generality that any dfa with k states has the state set {q1, q2, . . , qk}. now think about how to count how many ways there are to choose the other four parts of the dfa.
Answers: 3
Computers and Technology, 23.06.2019 14:30, naomi20044
Select the correct answer. andy received a potentially infected email that was advertising products. andy is at risk of which type of security threat? a. spoofing b. sniffing c. spamming d. phishing e. typo-squatting
Answers: 2
Computers and Technology, 23.06.2019 16:00, keyonaemanieevans
Helen is having a meeting with her colleagues in her company. they are working on the goals and objectives for the coming year. they want to ensure that these goals and objectives of the processes involved are properly evaluated. which system can helen and her colleagues apply to evaluate this? helen and her colleagues require a blank to evaluate the goals and objectives.
Answers: 2
Do you know the correct answer?
You and Alice and Bob are driving to Tijuana for spring break in Bob’s car. You are savingyour money...
Questions in other subjects:
Mathematics, 05.10.2019 20:00
English, 05.10.2019 20:00
Computers and Technology, 05.10.2019 20:00
