Problems
1. (15 pts) Exercise 15.4-5 (if you did not submit it for previous HW).
2. (15 pts) Exercise 15.2-1.
3. (15 pts) Exercise 15.3-2.
4. (20 pts) Exercise 15.3-5.
5. (20 pts) Problem 15-5.
6. (30 pts) (Note: you should decide to use Greedy or DP on this problem) Prof. Curly is planning a cross-country road-trip from Boston to Seattle on Interstate 90, and he needs to rent a car. His rst inclination was to call up the various car rental agencies to nd the best price for renting a vehicle from Boston to Seattle, but he has learned, much to his dismay, that this may not be an optimal strategy. Due to the plethora of car rental agencies and the various price wars among them, it might actually be cheaper to rent one car from Boston to Cleveland with Hertz, followed by a second car from Cleveland to Chicago with Avis, and so on, than to rent any single car from Boston to Seattle.
Prof. Curly is not opposed to stopping in a major city along Interstate 90 to change rental cars; however, he does not wish to backtrack, due to time contraints. (In other words, a trip from Boston to Chicago, Chicago to Cleveland, and Cleveland to Seattle is out of the question.) Prof. Curly has selected n major cities along Interstate 90 and ordered them from East to West, where City 1 is Boston and City n is Seattle. He has constructed a table T [i; j] which for all i < j contains the cost of the cheapest single rental car from City i to City j. Prof. Curly wants to travel as cheaply as possible. Devise an algorithm which solves this problem, argue that your algorithm is correct, and analyze its running time and space requirements. Your algorithm or algorithms should output both the total cost of the trip and the various cities at which rental cars must be dropped o and/or picked up.
1
