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 | ||||||
20 | ||||||
50 | ||||||
100 | ||||||
1000 | ||||||
10000 |
For what size of n does the computation time for T(n) = 2n 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);