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) = n² T(n) = n³ T(n) = 2ⁿ
10
20
50
100
1000
10000

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?

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.

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

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)

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);
```
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);
```
Write a function that will free all the memory associated with a tree
```
void freeTree(treelink 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);
```