Question 1: Arbitrage Opportunities

An arbitrage in finance is a way to make money for sure without much risk. For instance, suppose 1 USD yields 5 Chinese RMB and 1 RMB trades for 0.4 Euros, and 1 Euro trades for 0.52 USD, you have an arbitrage opportunity wherein you can take x USD, obtain 5x RMB, and in turn trade them for 2x Euros and finally end up with 1.02x USD back. Every time you exercise this opportunity, you get a 2 cent profit (assuming you can trade for free and there is no spread in the buying and selling prices, but that is another can of worms).

In theory, arbitrage cannot exist in efficient markets but they can persist for a short amount of time. Electronic traders can then search for such opportunities in real time and rapidly exploit them.

You are given a basket of nn currencies and for each pair of currencies (Ci,Cj)(Ci,Cj), you are given a ratio Ri,jRi,j that says that one unit of currency CiCi is currently fetching Ri,jRi,j units of CjCj.

(A) Given the ratios Ri,jRi,j write an efficient algorithm that can detect if any arbitrage opportunities currently exist. What is the running time of your algorithm?

(Hint: Make a graph out of the problem data. What does the presence of arbitrage mean for this graph? )

(B) We are not just interested in finding an arbitrage opportunity, but also interested in finding the shortest length opportunity, defined as one that involves the smallest number of trades. Naturally, given that prices change and also given that there are trading fees, such opportunities are more desirable.

Write an algorithm to find the smallest length arbitrage opportunity. What is the running time for your algorithm?

(Hint: Modify the Floyd Warshall algorithm you learned this week. In particular, how do you detect if there is a negative weight cycle of length k in the graph?)

Answer 1 (Expected Length: 12 lines).

(A) Your answer here

(B) Your answer here

Question 2: Longest Paths.

Given a weighted, directed graph GG, the longest simple path from vertex ss to tt is a path that (a) goes from ss to tt, (b) cannot revisit a vertex along the path, and (c) has the maximum weight among all the paths going from ss to tt.

(A) Show using an example that for any graph GG, that the longest path problem is not equivalent to solving the shortest path problem by negating the edge weights. (Hint Negating edge weights will work but for a common problem that makes shortest paths undefined.)

(B) Show that if the graph GG is a DAG, the longest path problem can be solved by negating the edge weights and solving a shortest path problem. What is the running time cost?

Answer 2 (Expected Length: 6 lines)

(A) your answer here

(B) your answer here

Question 3: Being In the Right Place At the Right Time.

You are helping a secret agent plan a series of rendezvous in a capital. The rendezvous are happening along different stations of a subway line at precisely hours 1,2,…,n1,2,…,n. There are mm subway stations, each with an ID numbered 1,…,m1,…,m. The rendezvous at hour jj occurs at station SjSj:

For instance, The rendezvous at hour 1 might happen at station 5, the rendezvous at hour 2 might happen at station 12, and the rendezvous at hour 3 might happen at station 1. In this case, S1=5,S2=12,S1=5,S2=12, and S3=1S3=1. Note: Your answer should be for any sequence of rendezvous, not for this specific example.

The spy starts at station 11 at time 00 and further, must at all costs attend rendezvous nn. In each hour, the agent is limited to travelling no more than KK stations along the line. Thus, she must decide whether to skip some of the rendezvous in favor of others.

Provide an algorithm to calculate the maximum number of rendezvous the agent can make with the constraint that she must make rendezvous nn. What is the running time?

Hint: As usual, it comes down to defining a graph and solving a suitable problem.

Answer 3 (expected length: 6 lines)

Your answer here

Question 4: U-turn if you want to.

A N×NN×N maze is defined by a graph with vertices (i,j)(i,j) for 1≤i≤n1≤i≤n and 1≤j≤n1≤j≤n. Each node (i,j)(i,j) is connected to a subset of its four adjacent neighbors {(i+1,j),(i,j+1),(i−1,j),(i,j−1)}{(i+1,j),(i,j+1),(i−1,j),(i,j−1)}.

The grid is laid out so that (1,1)(1,1) is the south west corner and (n,n)(n,n) is the northeast corner.

The vehicle starts at (1,1)(1,1) oriented north and needs to reach (n,n)(n,n) oriented east.

It can travel along the four cardinal directions N,E,W,SN,E,W,S and rapidly change these direction by making a left or right turn. Eg., changing heading from NN to EE requires making a right turn, NN to WW requires a left turn and NN to SS requires either 2 left or 2 right turns.

Find the minimimum cost path from (1,1)(1,1) oriented north to (n,n)(n,n) oriented east, where the cost is defined as the number of edges plus 2×2× the number of left turns plus 3×3× the number of right turns.

What is the running time of your algorithm?

Hint Define a new graph that helps us track not just the vehicle location but also its current travel direction. Define edge weights appropriately so that the shortest cost problem on this new graph will solve the original problem.

Answer 4 (Expected Length: 8 lines)

Your answer here

Testing your solutions — Do not edit code beyond this point