Quantitative Finance

Computer Science Concepts

Recursive functions

         

Suppose we have 2n2n "silver" coins of the same weight. One of them is however fake and it weighs less. In other words we have 2n12n - 1 silver coins of equal weight and one fake of lesser weight. We also have a balance scale. We can put any number of coins on each side of the scale at the same time, and the scale will indicate whether the two sides are the same weight or which side is lighter.

Suppose we devise an algorithm that locates the fake coin using the balance scale as few times as possible. What is the maximum number of weighing operations necessary to find the odd coin out?

How many weighing operations would be required for 243 coins if we are as unlucky as possible but we use the optimal algorithm?

Consider the task of drawing the markings on a ruler: there is a mark at the halfway point, slightly shorter marks at the quarter intervals and still shorter marks at the eighth intervals. If our desired precision is 12n\frac{1}{2^n} (arbitrary units), we put a mark at every point between 00 and 2n2^n. The middle mark should be nn units high the quarter marks should be n1n-1 high, etc. Assuming we have a function mark(x, h) to make a mark hh units high at position xx, the following program does the job of marking a ruler:

1
2
3
4
5
6
7
8
def rule(left, right, height):
    if height > 0:
        x = (left + right) / 2
        mark(x, height)
        rule(left, x, height - 1)
        rule(x, right, height - 1)
   else:
        pass

Since rule(left, right, height) is recursive we know that it will call itself. Suppose that we call rule(left=0, right=2**10, height=10). During recursive call number 99 to rule (do not include the initial user call), it will make a mark at position xx. What is the value of xx?

The Pascal triangle, shown below, has an interesting property. Every entry is equal to the sum of the two entries above it, except along the left and right edges where the value is always equal to 11.

Write a recursive algorithm that outputs the sum of the numbers on each line. For example the sum of the numbers on the 33rd line is 1+2+1=41+2+1=4. What is the sum of the numbers on the 2323rd line?

1
2
3
4
5
1  define recur(num):
2      if num > 100:
3          return num - 10
4      else:
5          return recur(recur(num + 11))

Consider the above recursive algorithm, predict what it will output when num=98\text{num}=98.

1
2
3
4
5
6
7
23 32 62 20 77 42 31
15 14 10 11 48 32 30
14 46 71 31 53 07 82
20 12 78 78 46 24 43
37 16 12 99 15 97 85
13 29 82 71 63 27 75
44 81 80 48 02 45 17

Consider the square grid above. Suppose a person wants to move from the top left corner towards the bottom right corner. To move, a person can go down or right. Let SS be the path traversed such that the sum of the cells in the path is minimized. What is the value of SS?

×

Problem Loading...

Note Loading...

Set Loading...