CS124 Problem Set 9

Due April 25


We often need to get to one place from another in a city, and on the way we want to visit some other places in a given order. For instance, suppose that today is your grandfather's birthday and you will go to your grandparents' house to celebrate. But you also need to go to a number of other places during the day, and you plan to visit them in the following order:
  1. Start from your home.

  2. Go to any bank ATM machine for some cash.

  3. Go to any McDonald for breakfast.

  4. Go to any Kinko's to fax an important document that is due early this morning.

  5. Go to any post office to mail your graduate school applications that are due today.

  6. Go to any Chinese restaurant for lunch.

  7. Go to any barber shop for a hair cut.

  8. Go to any Star Market to buy your grandfather a nice birthday cake.

  9. Finally, go to your grandfather's house.

The goal is to find a shortest route that allows you to reach the destination and visit all the intermediate places in order.


Your Challenge:

Suppose you are the chief designer of an online map system. The system accepts from the user the source, the destination, and an ordered list of sets of intermediate places the user has to visit, and returns a shortest route to the user.

Problem 1

Formulate the above as a graph optimization problem.

Problem 2

Describe an efficient algorithm to solve this problem. Show the running time of your algorithm.


Rule:

Please form groups of 3 to 4 among yourselves. Send email to cs124tf as soon as you form groups. If you have trouble finding partners, let us know immediately. Each group should hand in just one write up, and will give us a 10 minute presentation of their solution.