Tutorial Exercises Week 03

Exercise 1

Function Growth Rates

Calculate how long T(n) steps would take for different sizes of n for the T(n) functions in the table below. Assume you are running it on a computer that performs one million steps per millisecond. Note: A millisecond is a thousandth of a second.

n	T(n) = log n	T(n) = n	T(n) = n log n	T(n) = n2	T(n) = n3	T(n) = 2n
10	0.003 microsec	0.01 microsec	0.03 microsec	0.1 microsec	0.001ms	0.001ms
20	0.004 microsec	0.02 microsec	0.09microsec	0.4 microsec	0.008ms	1ms
50	0.006 microsec	0.05 microsec	0.28 microsec	0.0025ms	0.125ms	13 days
100	0.007 microsec	0.1 microsec	0.67 microsec	0.01ms	1ms	4x1013 years
1000	0.01 microsec	0.001 ms	0.01 ms	1ms	1 second	very long time
10000	0.013 microsec	0.01 ms	0.13 ms	100ms	17 minutes	very very long time

For what size of n does the computation time for T(n) = 2ⁿ become too large to be practical? Would it help if we used a computer that was a million times faster?

Solution

when n >= 50, the computation time for T(n) = 2ⁿ has started to become too large to be practical. At n >= 100 it would be impossible to wait for it to finish - unless you are blessed with the gift of eternal life.

Even if we were to increase the speed of the machine by a million, 2ⁿ for n = 100, it would still take 40,000,000 years.

Exercise 2

Write a recursive function

int allEven (int a[], int l, int r);

which takes an array, the left-most and right-most index of the current segment of the array as an argument and checks if all elements in an array are even.

It must use a divide and conquer approach, by splitting the array in half, first checking if all the elements in the left half are even, and then (only if necessary) checking the right half.

int allEven(int a[], int l, int r) {
    int mid, first;
    if(r < l) return 1;
    if (l == r){
        return (a[l] % 2 == 0);
    }else{
        mid = (l + r)/2;
        first = allEven(a, l, mid);
        if(first){
           return allEven(a, mid + 1, r);
        } else {
           return 0;
        }
    }
}

What would the worst-case time complexity be in Big O notation?

In the worst case - that they are all even, all elements in the array must be checked so the time complexity ends up being O(n).

Exercise 3

Binary Search Tree Insertion, Deletion and Traversal

Insert the following keys into a BST:  10 20 5 30 15 25 24

What is the height of the resulting tree?

Delete 5 30 20 (assume we replace nodes with the left-most of the right sub-tree when necessary)

What is the height of the resulting tree?

Show the output obtained by traversing the tree and printing out each node in the following orders:

• prefix (NLR)
• postfix (LRN)
• infix (LNR)

Solution

 10
 / \
5  20
   / \
  /   \
 15   30
      /
     25
    /
   24

Height: 4

Delete 5 30 20

What is the height of the resulting tree?

Solution

After deleting 5

10 
  \ 
  20
  / \
 /   \
15   30
     / 
    25 
   / 
  24 

After deleting 30
10
  \
  20
  / \
 /   \
15   25
     /
    24

After deleting 20
       
10   
  \  
  24
  / \
 /   \
15   25
   
Height: 2

Solution Traversals of the final tree

• prefix: 10 24 15 25
• postfix: 15 25 24 10
• infix: 10 15 24 25

Exercise 4

BST Functions

Assume the following representation of a BST

typedef struct treenode *treelink;

struct treenode{
    Item item;
    treelink left;
    treelink right;
}

• Assume your tree holds items of type int. Write a function to recursively sum the items of a BST tree. Your function should have the following prototype:

  int sumItems(treelink tree);
  

  int sumItems(treelink tree);
  

  int sumItems(treelink tree){
      if(tree == NULL){
          return 0;
      } else {
          return tree->item + sumItems(tree->left) + sumItems(tree->right);
      }
  }
  

• Write a function that searches for a given item in a BST. Your function should return 1 if the item is found and 0 otherwise. You should use an iterative approach and a recursive approach

  int iterativeSearch(treelink t, Item i);
  

  int recursiveSearch(treelink t, Item i);
  

  int iterativeSearch(treelink t, Item i){
      int result = 0;
      treelink curr = t;
      while(curr != NULL && result == 0){
          if(i < curr->item){
              curr = curr->left;
          }else if(i > curr->item ){
              curr = curr->right;
          }else{ 
              result = 1;
          }
      }
      return result;
  }
  

  int recursiveSearch(treelink t, Item i){
      if (t == NULL) {
          result = 0;
      } else if( i < t->item ){
          result = search(t->left,i); 
      } else if( i > t->item ){
          result = search(t->right,i);   
      } else {
          result = 1;
      }    
      return result;
  
  }
  

• Write a function that will free all the memory associated with a tree

  void freeTree(treelink t);
  

  void freeTree(treelink t) {   
      if (t != NULL) {
          freeTree(t->left);    // must free the children first
          freeTree(t->right);
          free(t);
      }
  }
  

  Write a function to insert an item into a BST. It should return the root of the tree.

  treelink insert(treelink t, Item i);
  

  treelink insertIterative(treelink tree, Item key) {
      treelink curr = tree;
      treelink prev = NULL;
      treelink newNode = createNode(key);
      while(curr != NULL){ 
          prev = curr;       
          if ( key <= curr->item){
              curr = curr->left;
          } else {
               curr = curr->right;
          }
      }
      if(prev == NULL){
         return newNode;
      } else if(key < prev->item){
          prev->left = newNode;
      } else {
          prev->right = newNode;
      }
      return tree;
     
  }
  

  treelink insertRec (treelink tree, Item item) {
      if(tree == NULL){
          treelink newNode = createNode(item);
          return newNode; //now the root of the tree
      } else {
          if(item <= tree->item){
              tree->left = insertRec(tree->left, item); //
          } else {
              tree->right = insertRec(tree->right, item);
          }
      }
    return tree;
  }