1. Draw the LookUp table built by the length of the longest common subsequence algorithm presented in lectures. Use the two strings s1="cgata" and s2="gtcata".

   Remember to label the horizontal and vertical axes with substrings of the two given strings.

   What is the length of the longest common subsequence?

2. Consider the following recurrence relation:

    f(1)= 1; f(2)= 1; f(3)= 1; f(4)= 3; f(5)= 5;
           f(n)= f(n-1) + 3*f(n-5) for n >5.
     

   1. Compute f(n) for n= 6,7,12,15.
   2. Which values did you need to compute again? In order to compute f(n), which values f(m) do you need? In order to compute f(n+1) which values f(m) do you need? Given N, to compute f(N) from scratch, you would need to compute all the preceeding values f(n); to save time you would store the previously computed values for looking up later. What is the smallest number of values you need to store?
   3. Write an efficient iterative program to compute f(N).

3. (*) Consider the following game played on the given square array, c[i][j].

   
     +---+---+---+---+---+
   0 | 6 | 7 | 4 | 7 | 8 |
     +---|---|---|---|---+
   1 | 7 | 6 | 1 | 1 | 4 |
     +---|---|---|---|---+
   2 | 3 | 5 | 7 | 8 | 2 |
     +---|---|---|---|---+
   3 | 2 | 6 | 7 | 0 | 2 |
     +---|---|---|---|---+
   4 | 7 | 3 | 5 | 6 | 1 |
     +---+---+---+---+---+
       0   1   2   3   4
       
   

   Each of the numbers in the squares represents an amount of money in dollars. A counter is first placed on the top left square. The player's objective is to move the counter vertically, or diagonally (always downwards) one square per move, in order to reach the bottom row. Thus if he is at position (i,j), then his possible moves are to move the counter to (i+1, j-1), (i+1,j) or (i+1, j+1).

   However, there is a snag: every time the counter lands on a square, the money is removed from that square on the board. When he reaches the bottom row, he is allowed to keep the remaining money on the board. Thus his objective is to maximise his winnings, which translates to finding a path whose total worth is as small as possible.

   An obvious recursive solution to calculate the minimimum path value is as follows

       
       int minCost(int i, int j) {
          if (i== 4)  return c[i][j];
        
           else    
           return min( minCost(i+1, j), minCost(i+1, j-1), minCost(i+1, j+1) ) + c(i, j);
       }    
       

   where "min" is thw function that computes the minimum of its inputs. As with other examples we've seen, this is not very efficient, since the same values are recomputed repeatedly.

   Use the ideas of dynamic programming to use a table LookUp[i][j], which stores the cost of the minimum path value from position (i, j) on the board to the bottom row (i.e. i==4). The following hints should help you.

   1. If the current position is (i,j) with (i==4) (ie the bottom row) then the shortest path from there to the bottom row is c[i][j]. (Why?)
   2. For all other positions, the shortest path from there is the current value (c[i][[j]) plus the minimum of the cost of the shortest path from one of the three possible new positions.

4. Consider the following tree

                         a
                       /   \
                      b     c
                     / \   / \
                    d   e  f  g
                   /   /     / \
                  h    i     j  k 
   

   For each of inorder, preorder and postorder traversals, state the order of the nodes printed.

5. Now write a function which takes a binary search tree and adds the values of the nodes into a stack so that the items are sorted. You may use the standard functions of a basic stack class. (Does your implementation place the items so that they are sorted from bottom to top, or from top to bottom?)

All enquiries to Annabelle McIver