1. A binary search tree is a binary tree T such that each internal node
   v of T stores an item e. Items stored at nodes in the left subtree of 
   v are less than or equal to e, and items stored in the right subtree of 
   T are greater than e.

 (a) Insert into an initially empty binary search tree the following
     items, in the order shown: 30, 40, 24, 58, 48, 26, 11, 13, 36. 
     Draw the tree after the insertions have been completed.
                                                                     (4 marks)
 (b) Give the preorder, inorder, and postorder traversals of the
     above tree.
                                                                     (3 marks)
 (c) Draw the tree after the node with item 30 is deleted, and describe
     the algorithm you have used for the deletion.
                                                                     (7 marks)
 (d) If we had to insert 1023 items into a binary search tree, what would be 
     the minimum and maximum height of the binary search tree, and under
     what circumstances would the maximum height occur. In your answer
     explain what we mean by the height of a tree.
                                                                     (6 marks)

-------------------------------------------------------------------------------

2. An efficient realisation of a priority queue might use the heap data
   structure, allowing insertion and removal in logarithmic time.
   The heap may be implemented as a binary tree.

 (a) What two properties are maintained by the heap data structure?
                                                                    (2 marks)
 (b) Assume we have a heap of integers. Given an empty heap H, draw the 
     heap after each insertion of the following integers: 11, 7, 9, 8, 5, 2, 
     and then 14 (that is, you must draw 7 heaps, the first with 11 in it,
     then 11 and 7, 11 and 7 and 9, ... finally with all of the integers
     inserted). Describe the algoritmic steps that must be performed when 
     inserting into the heap.
                                                                    (6 marks)
 (c) Draw the heap when we delete the minimum element, and describe
     the algorithmic steps that must be performed when deleting the
     minimum element.
                                                                    (6 marks)
 (d) Insertion and removal is performed in logarithmic time. 
     Explain why that is so, and explain how we can exploit this
     to implement an efficient sorting algorithm.
                                                                    (6 marks)

-------------------------------------------------------------------------------

3. Insertion sort takes an unordered sequence of objects S and
   delivers as a result a sequence R, where the elements of R are 
   the elements of S in non-decreasing order. Assuming that the 
   sequences S and R are both implemented as integer arrays, insertion 
   sort inserts element S[i] into position R[j], such that if j>0, R[j-1] 
   is less than or equal to R[j].

 (a) Given the class definition of Sort below, define the method
     insert, where the method makes the ithInsertion of an integer 
     x into an array R

       public class Sort {
  
        public int[] insertionSort(int [] S){
          int n = S.length;
          int [] R = new int[n];
          for (int i=0; i<n; i++)
	    insert(S[i],R,i);
          return R;
        }

        private void insert(int x, array [] R, int insertionNumber){...}
          
      }
                                                                    (10 marks)
              
 (b) What is the complexity of insertionSort? Explain your reasoning.
                                                                    (5 marks)

 (c) Under what circumstances will insertionSort perform the least
     computational effort, and under what circumstances will insertionSort
     perform the most computational effort.
                                                                    (5 marks)

-------------------------------------------------------------------------------

4. A dictionary stores key-element pairs (k,e), which we call items,
   where k is the key and e is the element. The primary use of a dictionary
   is to store elements so that they can be located quickly using keys.

 (a) We might have an unordered dictionary or an ordered dictionary. 
     Given a dictionary D, what would be the complexity of the following
     operations when D is an unordered dictionary and when D is an
     ordered dictionary: 
      - D.insertItem(k,e)
      - D.findElement(k)
      - D.size()
      - D.remove(k) 
     Explain each one of your answers in turn, and state any assumptions that 
     you make.
                                                                     (10 marks)

 (b) We might implement our dictionary using a hash table. What is a hash 
     table? How does it operate, what limitations is it subjected to, and what 
     is the complexity of the above operations on a hash table? Again, state 
     any assumptions that you make.
                                                                     (10 marks)