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". Consider the following program that refers to the LookUp table and strings s1 and s2:

      void subsequence::mystery(int i, int j) {
      while (i < s1.length() && j < s2.length()) {
        if (LookUp[i+1][j] == LookUp[i][j]) i++;
        else if (LookUp[i][j+1] == LookUp[i][j]) j++;
        else {cout << s1[i]; i++; j++;}
      }
     cout << endl;
   }
   

   1. What does it output for the initial input i=0, j=2?
   2. What does it output the the initial input i=0 and j=0?
   3. State an invariant for the loop. How do you know that the loop will terminate?
   4. What is the largest number of times that the program may iterate for? Compare that number to the brute-force approach for computing a longest common subsequence.

2. Given the recursive nature of a binary tree (not necessarily a binary search tree), a good strategy for writing a C++ function that operates on a binary tree is often first to write a recursive definition of the task. Write recursive functions for the following tasks.
   1. Count the number of nodes in the tree;
   2. Determine the maximum element;
   3. Determine the sum of the elements (assuming the data items are integers);
3. (*) The partition function used in QuickSort given in lectures requires a final swap of the pivot item p. Now think of writing an alternative algorithm based on the following invariant.

   "All the items with index at least F but less than b are <= p; all the items with index greater than c, but no more than L are >=p; A[b] == p"

   Here F, L are the first and last indices of the array A, c is a counter that starts at L and should be decremented, and b is an index that should always point to the position in the array whose item is p.

   1. Using the above invariant, rewrite the partition function so that it does not require the final swap.

   2. Trace this partition function for the array A= [27, 38, 12, 39, 27, 16].

4. The partition algorithm (given in lectures) in QuickSort moves one item at a time from the unknown region into one of the two regions (A[1..LastS1] < p) and (p <= A[LastS1+1...FirstUnknown]). Sometimes the item to be swapped will be swapped with itself. When does this happen? Modify the partition algorithm from lectures so that the unecessary swap does not take place.
5. Consider an arbitrary tree where each node has an arbitrary number of children.

   struct GenNode{
     int data;
     vector < GenNode* > links;
     int number;
     };
   

   (Here number is the number of children, whose addresses are stored in links.) Write a recursive preorder traversal for such a tree.

   void GenPreorder(GenNode* t);
   //POST: Prints the data in the nodes in pre-order traversal.   
   

6. Write a FatPartition function:

     void FatPartition(int A[], int F, int L, int& b1, int& b2);
     //PRE: F <= L, and both are valid indices of A;
     //     P == A[F]
     //POST: A[F..b1] < P; A[b1+1..b2] == P; A[b2+1..L] > P 
   
   

All enquiries to Annabelle McIver