Options

You may either construct your own lab assignment (subject to approval), do the assignment found here (additional info), or do the assignment given below.

Outcomes Addressed

• apply asymptotic time complexity analysis to choose among competing algorithms.
• describe how graph and tree structures are implemented.
• list at least three engineering applications of algorithmic design and analysis.

Team Assignment

You must work with your assigned partner.

Overview

Currency exchange rates may be used to earn money. The idea is to transform currency through a series of exchanges that begin and end with the same currency and result in greater amount of currency than the initial amount. For example, suppose 1 U.S. dollar buys 12 pesos, 1 peso buys 0.2 francs, and 1 franc buys 0.5 U.S. dollars. The result of converting 1 U.S. dollar to pesos, then to francs, and then back to U.S. dollars, is 1.20 U.S. dollars... a 20% profit. This process is known as Arbitrage.

Appropriately timing the market allows currency traders to turn a profit. Unfortunately for the currency trader, each transaction usually requires a trading fee. For simplicity, you should assume a 1% fee for all trades in this assignment.

Three files are available currency.txt, exchangeSml.txt, and exchangeLrg.txt. The first file contains a key for the abbreviations used in the other two files. The other two files contain exchange rates for a number of countries. The first and last lines may be ignored. All of the remaining lines describe one exchange rate. For example,

  MYR -> USD [label="0.263227"];

indicates that 1 Malaysia ringgit is worth 0.263227 U.S. dollars. Note, these rates do not include the 1% trading fee. Accounting for the fee, 1 Malaysia ringgit could be converted to (1*0.99*0.263227) = 0.257989 U.S. dollars.

The exchange.lrg file indicates the exchange rates between many currencies for the most recent strictly odd date in history (11/29/1999). I have modified a number of exchange rates in order to make this lab assignment more interesting. The exchange.sml file contains a subset of the exchange rates listed in exchange.lrg.

You have been given 10,000 virtual U.S. dollars. Develop a program that efficiently finds the sequence of trades that produce the highest profit. Your sequence must not pass through any currency more than once (with the exception that it must begin an end with U.S. dollars). This sequence should be stored in a file along with the percent profit. Execute your program on both exchange files.

Just for Fun

Should you desire to make the assignment more realistic, you are welcome to expand your data set. You may wish to make use of currency exchange data in order to determine if there were days in history where such arbitrage was possible (consider the Xavier Finance Currency Exchange Rate API) and look for real-time opporutities (consider the Xurrency API or Multimolti's Currency Exchange Rates API).

You may implement your application in Java, php, Ruby on Rails, python, C++, or some other language of your choosing.

Demo (due beginning of week 10 lab (no grace period))

Each group will demonstrate their working program during lab. Students and instructor will rank the different programs, and the winning team will receive two prizes.

Each team can determine what they want to focus on in order make their demo stand out. You may wish to optimize your program for speed, particularly on large datasets, provide a stunningly useful user interface, or something else.

Lab report (due 4:00pm, Friday of week 10)

You may produce a PDF document for your report or use this template file as a starting point for this report.

Each pair should submit one lab report. Your report must include:

• Discussion containing:
  • An analysis of appropriate patterns (think about how the program may be extended by others in the future, identify logical patterns to consider even if you decide not to make use of them in your solution to this assignment)
  • A description of your algorithms
  • A description of the component of your application you are most proud of
  • A discussion of what you found most challenging
  • How you an your partner worked (or didn't work) together
  • Etc...
• Sample Program output or screen shots
• Documented source code

As with any report you submit, correct spelling and grammar are required. In addition, your report should be submitted electronically following the Electronic Submission Guidelines. (You may wish to consult the sample report before submitting your report.) Be sure to keep copies of all your files, in case something gets lost.

If you have any questions, consult the instructor.

Acknowledgment

This laboratory was developed by Dr. Chris Taylor.