Computers and Technology, 07.06.2020 04:00 jfox8741

Assume you are planning a canoe trip down a river. The river has n trading posts numbered 1 to n going downstream. You will start your trip at trading post number 1 and end at trading post number n. Let R(i, j) be the cost of renting a canoe at trading post i and returning it at trading post j, where j > i. Assume that you always want to go down river, so the costs if j ≤ i are irrelevant. Find the cheapest sequence of rentals that allow you to complete your trip. Aim for an algorithm running in O(n 2 ) time. For example, if n - 4 and the costs are: R(ij) 15 25 35 12 16 2 then the cheapest sequence of canoe rentals to travel the river would be to rent from 1 to 3, and then from 3 to 4 for a cost of 25 +5-30. On the other hand, if the costs were: 20 15 30 5 10 20 2 then taking one canoe all the way from 1 to 4 and renting 1 to 2 and then 2 to 4 are the cheapest solutions (both cost 30). (Note that renting from 1 to 3 is cheaper than going 1 to 2, but the 1 to 3 rental is not in any of the cheapest 1 to 4 solutions). Let C(k) be the cost of the cheapest sequence of canoe rentals starting from trading post 1 and returning the last canoe rented at trading post k. A. Assume an optimal sequence of rentals changes canoes at some trading post j. What subproblems are also solved optimally by (parts of) this rental sequence? B. Derive a recurrence for C(k) in terms of C(j) values where j < k. C. Give a bottom-up iterative algorithm for computing the C(j) values. D. Finally, show how keeping a little (i. e. O(n)) additional information allows the a cheapest sequence of canoe rentals to be printed out in O(n) time. For part (c), it may be helpful to first construct a recursive algorithm for computing the C(k) values.

Answers: 2

Show answers

Another question on Computers and Technology

Computers and Technology, 22.06.2019 11:30

What does a cascading style sheet resolve a conflict over rules for an element? a. the rule affecting the most content wins b. the rule affecting the most content loses c. the rule with the most specific selector loses d. the rule with the most specific selector wins

Answers: 2

Answer

Computers and Technology, 23.06.2019 11:30

Me dangers of social media and the internetexplain what each means: 1) social media and phones have become an addiction.2) outside people have access to you all the time.3) cyberstalking4) cyberbullying5) catphishing6) viruses7) identity theft8) credit card fraud9) hacking10) money schemes

Answers: 1

Answer

Computers and Technology, 23.06.2019 18:30

This program should be a short piece of code that prints all of the positive integers from 1 to 100 as described more fully below. the program may contain multiple methods, and if using an oo language, should be contained within a single class or object. the program should be designed so that it begins execution when invoked through whichever mechanism is most common for the implementation language. â–ş print out all positive integers from 1 to 100, inclusive and in order. â–ş print messages to standard output, matching the sample output below. â–ş in the output, state whether the each integer is 'odd' or 'even' in the output. â–ş if the number is divisible by three, instead of stating that the number is odd or even, state that the number is 'divisible by three'. â–ş if the number is divisible by both two and three, instead of saying that the number is odd, even or divisible by three; state that the number is 'divisible by two and three'. â–ş design the logic of the loop to be as efficient as possible, using the minimal number of operations to perform the required logic. sample output the number '1' is odd. the number '2' is even. the number '3' is divisible by three. the number '6' is divisible by two and three.

Answers: 1

Answer

Computers and Technology, 23.06.2019 21:30

Examine the list below. which factors positively affect lifetime income? check all that apply.

Answers: 1

Answer

You know the right answer?

Assume you are planning a canoe trip down a river. The river has n trading posts numbered 1 to n goi...

Questions