Log in to see any non-public content on this page

Athabasca University | AU Student/Staff Login | Invited Guest Login

Athabasca University | AU Student/Staff Login | Invited Guest Login

- Blogs
- COMP372 Design and Analysis of Algorithms
- Unit 3 Exercise 15.3-6 Discussion Question

- Public

By Danny Elliott in the group COMP372 Design and Analysis of Algorithms August 6, 2017 - 2:57pm Comments (2)

Proof that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission C_{k} = 0 for all k trades.

Let U_{1}, U_{2}, ..., U_{n} be a collection of currencies. We can represent all possible sequences from U_{1} to U_{n} as a directed graph where each node is a currency and is connected to each other node in the graph. Each directed edge represents a currency conversion value.

This problem is somewhat similar to the Unweighted Shortest Path problem only in this case, rather than hitting the fewest nodes from the start to end points, we wish to maximize the resulting value when exchanging from U_{1} along the sequence (path) to U_{n}

For simplicity, assume nodes are only visited once and that U_{1} ≠ U_{n}

Any path P from U_{1} -->_{P} U_{n} can be broken into sub-paths U_{1} -->_{P1} w -->_{P2} U_{n} (where node w can equal U_{1,} U_{n,} or some other currency in the collection). The number of edges in P equals the sum of edges in P1 and P2.

We claim that if P is the optimal path from U_{1} to U_{n} (that is, the sequence will offer the highest return of currency exchange) then P1 must be the optimal path from U_{1} to w and P2 must be the optimal path from w to U_{n}

By the cut and paste argument, if there was a more optimal path P1’ from U_{1} to w, then we could cut out P1 and past in P1’ to give U_{1} -->_{P1’} w -->_{P2} U_{n} as a more optimal path than P. However, this contradicts P’s optimality. Likewise, if there was a more optimal path P2’ from w to U_{n} , then we could cut out P2 and past in P2’ to give U_{1} -->_{P1} w -->_{P2’} U_{n} as a more optimal path than P. However, this contradicts P’s optimality.

This proves that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission C_{k} = 0 for all k trades.

When C_{k} are arbitrary values for all k trades, finding the best sequence of exchanges no longer has optimal substructure. This is because the sub-problem of finding the best return along the path is not independent from the problem of minimizing commissions based on the number of trades. What was once an optimal path when C_{k} = 0 could no longer be optimal when C_{k} is some other value.

This is for course discussion.

The Landing is a social site for Athabasca University staff, students and invited guests. It is a space where they can share, communicate and connect with anyone or everyone.

Unless you are logged in, you will only be able to see the fraction of posts on the site that have been made public. Right now you are not logged in.

If you have an Athabasca University login ID, use your standard username and password to access this site.

We welcome comments on public posts from members of the public. Please note, however, that all comments made on public posts must be moderated by their owners before they become visible on the site. The owner of the post (and no one else) has to do that.

If you want the full range of features and you have a login ID, log in using the links at the top of the page or at https://landing.athabascau.ca/login (logins are secure and encrypted)

Posts made here are the responsibility of their owners and may not reflect the views of Athabasca University.

*We block sites that track your web browsing without your permission. If a link is greyed out, click once to enable sharing, once more to share.*

## Comments

I'd say that the main reason why there is no guarantee that the sub-problems may give optimal solutions, because the commission rates are arbitrary values so as long as that is the case then the problem won't exhibit optimal substructure property.

Farzia Dilawar Khan August 7, 2017 - 12:41pm

Great proof of the optimal substructure. It is fun to also think of counterexamples for when the commission rates are nonzero!

Paul Wilson July 9, 2021 - 11:45am