Problem Set 7—Dynamic Programming 1

Purpose

Background

Exercise

Solve each of the following problems.

Problem 1

A certain game is played on a track of tiles, numbered 1 through n. A player starts the game by placing a marker on tile 1. Subsequently, players take turns moving their markers; if a player's marker is on tile i, they can move it to either tile i+1 or tile i+2 in their turn. Each move is awarded a score; the score for moving from tile i to j is given by s_ij (by the rules of the game, i < j ≤ i+2). Scores may be negative as well as positive. The game ends after each player’s marker has reached tile n. The object of the game is to get the highest total score, i.e., the highest sum of move scores while moving your marker from tile 1 to tile n. Design a dynamic programming algorithm that finds the highest total score that can be achieved in an instance of this game, and the sequence of moves that produces that total score.

Problem 2

Sleazy Sammy and Phineas Phoole run competing bus services between Geneseo and points east. Both bus services start their runs in Geneseo, but some other points are served by one service, some by the other, and some by both. Both services price their tickets based on trip segments between adjacent stops. Prices for similar segments can vary wildly between the services, however. The following diagram shows an example of how these services might work. The straight lines represent the bus services, Phineas Phoole’s on top and Sleazy Sammy’s below. Circles represent cities, and a black dot on a bus line within a city means that the bus service stops in that city. Dollar amounts are the costs of traveling between two stops on a particular bus line. For example, Phineas Phoole serves Geneseo, Utica, and Albany, but not Syracuse, while Sleazy Sammy serves all four cities. It costs $20 to take Phoole’s bus from Geneseo to Utica, but $25 to take Sammy’s (because to take Sammy’s bus from Geneseo to Utica you have to buy a $15 ticket from Geneseo to Syracuse, and then a $10 ticket from Syracuse to Utica).

Because of the way these bus services are priced, the cheapest way to get from one city to another will generally be to transfer from one bus line to the other at various points. For example, the cheapest way to get from Geneseo to Albany on these buses is to take Phineas Phoole’s bus from Geneseo to Utica, but then transfer to Sleazy Sammy’s bus to go from Utica to Albany. The total cost of this trip is $35, namely $20 for the Geneseo to Utica ticket plus $15 for the Utica to Albany ticket.

Suppose you want to plan a trip from Geneseo (city 1) to some other city, city n, using these buses as your only transportation. Give a dynamic programming algorithm that finds the minimum trip cost, and that lists which bus service to take between which pairs of cities. City n may or may not be served by both bus services.

Problem 3

Problem 15-8b from our textbook.

Extra Credit

For up to 3 points extra credit, code one or more of your algorithms in an actual programming language and demonstrate them working.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Schedule your meeting to last 15 minutes. Please sign up for your meeting on the schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure your meeting ends by the end of the day on the due date above.