Algorithms (CS 331H)

Posted by Ashwin Madavan on April 6, 2016

Workshop Selection

Let be the set of all possible days to hold a workshop and let be the set of people interested in attending the workshop such that each person wants to attend during . Each day costs , but each person will willing pay to attend. Suppose there is no limit to the number of people that can attend on a particular day, what days should you select to maximize profit?

Constrct a flow network as follows:

  • Create a source vertex and a sink vertex
  • Create a vertex for each person
  • Create a vertex for each day
  • Create a directed edge of capacity for all
  • Create a directed edge of capacity for all
  • Create a directed edge of capacity for all such that

For some subset , let and . Clearly, .

Find the minimum cut of . Because all paths contain edges of finite capacity by construction, the minimum cut must always be finite. Therefore, the cut-set of the minimum cut may only contain edges of the form or . Because no edges may cross the cut, all the desired days for each person in must be in . Consequently, the cut capacity is defined as:

Therefore,

Because is minimal, must be maximal. Therefore, the days generate the maximal profit of .

Detecting Arbitrage

Let be a set of currencies and let the be the set of exchange rates between currencies such that is the exchange rate between currencies and . Clearly, . Arbitrage occurs when there are opportunities for riskless profit. How do you detect arbitrage opportunities between currencies?

In the graph arbitrage occurs where there exists a cycle of currencies such that:

Therefore, detecting arbitrage opportunities in is equivalent to finding negative cost cycles in the graph , which can be found in using the Floyd-Warshall Algorithm.

Tiling

How many ways can one tile a 3 x n rectangle using 2 x 1 tiles? It is immediately clear that must be even, because it is impossible to tile an odd area with even area tiles. Therefore, and . By enumerating the various ways to tile 2 x 1 tiles on a 3 x rectangle for , I determined that the number of tilings:

By subtraction of these two equations,

Therefore, . The characteristic equation of this linear homogeneous recurrence relation is . The roots of this characteristic equation are and . Suppose the closed-form solution of the recurrence relation is of the form

Consequently, and . Therefore, the closed-form solution to the recurrence relation is and solves the problem in time and space.

How many ways can one tile a k x n rectangle using 2 x 1 tiles? Assuming we can tile the first n-1 columns of the rectangle, how many ways are there to tile the last column? We can either tile elements in the last column one-at-a-time using a horizontal tile or two-at-a-time using a vertical tile. Therefore, the number of ways to tile the last column . Because the Fibonnaci number , the number of ways to tile the last column grows exponentially with . Because there are columns in the matrix, the complexity of the algorithm is .

Cover photograph by aspireblog.