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

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 18:30, emojigirl2824

Word vocabulary words: print, proofread, status line, graphics, font effects, left margin, justification, line spacing, copy/paste, data. review words: font point, bold, save, center, error. fill in the correct word for the definition and then transfer the letters to the appropriate spot by number. some numbers will be found multiple times. you will end up with a quotation about…… what else? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k 16 17 18 19 20 21 22 23 24 25 8 27 28 29 w 31 32 k 34 35 36 w h 39 40 41 42 8 44 45 46 47 48 49 50 51 52 53 54 55 .1. a software function that records keystrokes on a disk or drive so information can be 5 4 52 9 later retrieved. p n 2. to produce a paper copy of information. 10 7 12u n 3. a display that shows the location of the cursor, pages, etc. 45 46 18 27 36 20 42p4. pictures or images, located in clip art or other files. 6 24 44 28 34 49 555. any mis-stroke of a key. 47 41 48 2 10 n6. allows major changes to the font such as shadow, emboss, etc. 21 25 46 35 23 21 29 14 22 17 n7. a feature that centers lines of text horizontally. 49 53 46 9 51 p8. size of the font 31 16 22 b l 9. a feature that prints designated text darker than the rest to add emphasis. 32 3 . p10. to compare copy on a display screen or printout to the original 24 39 25 23 54 9 50 3 and correct errors. j un 11. a feature that allows text to be aligned at the left 11 12 7 21 16 49 40 46 34 2 and right margins. leftn 12. amount of blank space on the left side of the paper. 8 18 41 6 34 linen 13. number of blank lines between lines of text. 17 4 49 13 1914. any information inputted into the computer. 3 4 46 44 p /p15. feature that duplicates text from one location and places it in another.

Answers: 2

continue

Computers and Technology, 23.06.2019 06:30, eddsworldfrantic

You have a small company and want to keep your costs low, but it is important your employees share data. which network would provide you with the most economical solution?

Answers: 1

continue

Computers and Technology, 24.06.2019 00:30, rustjallison9928

Asecurity policy is a a. set of guidlines b. set of transmission protocols c. written document d. set of rules based on standards and guidelines

Answers: 2

continue

Computers and Technology, 24.06.2019 11:00, dirttrackr75

Which of the statements below describe the guidelines for the use of text in presentation programs? a. do not use numbered lists. b. fonts should be appropriate for your audience. c. limit the number of fonts you use to three or four. d. only use bulleted lists for sales promotions. e. select font sizes that are appropriate for your delivery method. f. use font colors that work well with your background. select all that apply

Answers: 1

continue

Do you know the correct answer?

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