1. Consider the fast exponentiation algorithm given to you in lectures. Change it so that n can be at least halved after every iteration. [Hint: if n is odd, then n-1 is even.] (Make sure that you maintain the invariant.)

2. Consider the implementation below for Insertion Sort, which sorts an array into descending order. Trace the algorithm for the array A = {2,1,5,0,6}, and n=5; make sure you keep track of the array after each inner and outer iteration. In your trace, draw a rectangle around the array after each complete iteration of the OUTER loop (see (++) in the code). Verify that A[0..j-1] is sorted after each complete iteration of the outer loop. (Note that A[0..j-1] means "the portion of the array between, and including, indices 0 and j-1.) Now check that the invariant for the outer loop is established (made to be true) by the initialisation of the variable j. Finally deduce that the postcondition is satisfied after the outer loop has terminated. (Hint: what is the value of j on termination? Substitute into the invariant.)

   void insertion_sort(int array[], int n)  
    // PRE: n is the length of array
    // POST: array is sorted
   {
        int i, j, key;
          for(j = 1; j < n; j++)    //Notice starting with 1 (not 0)
        // Invariant for the outer loop: array[0..j-1] is sorted, descending order
          {
              key = array[j];
              for(i = j - 1; (i >= 0) && (array[i] < key); i--)    //Move smaller values up one position
              {
                 array[i+1] = array[i];
               }
              array[i+1] = key;    //Insert key into proper position (++)
          }
         return;
   }
     
          

3. 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);

4. * Beginning with the empty binary search tree, what binary search tree is formed when you insert the following values in the order given? Use the insertion algorithm given in lectures.

   W, T, N, J, E, B, A
   W, T, N, A, B, E, J
   A, B,W,J,N,T,E
   

   For each tree write down the sequence of letters obtained with an inorder, preorder and postorder traversal.

All enquiries to Annabelle McIver