Calculate how long steps would take
for different sizes of
for the various functions in the table below.
Assume you are running it on a computer
that performs one billion steps per second
(roughly on par with a current smartphone).
$$T(n)=$$ n
$$\log n$$
$$n$$
$$n\log n$$
$$n^2$$
$$n^3$$
$$2^n$$
10
?
?
?
?
?
?
20
?
?
?
?
?
?
50
?
?
?
?
?
?
100
?
?
?
?
?
?
1000
?
?
?
?
?
?
10000
?
?
?
?
?
?
(Click the table to edit!)
For what size of n does the computation time
for become too large to be practical?
Would it help if we used a computer
that was a million times faster?
Recursive Functions
Write a recursive function
boolall_even(inta[],size_tl,size_tr);
which takes an array, and the left-most and right-most indices of
the current segment of the array as arguments,
and checks if all elements in an array are even.
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?
Binary Search Trees
Insert these keys into a BST,
assuming normal integer ordering:
.
What is the height of this tree?
Delete ,
assuming we replace nodes
with the left-most node
of the right sub-tree when necessary.
What is the height of the tree after this deletion?
Show the output obtained by traversing the tree
and printing out each node in the following orders:
prefix (NLR):
postfix (LRN):
infix (LNR):
level-order:
Functions in a Binary Search Tree
Assume the following representation of a binary tree:
Assume our binary tree holds items of type int.
Write a function to recursively sum
the items of a binary tree.
Your function should have the following prototype:
intint_btree_sum(btree_node*tree);
btree_search
Write two functions that search
for a given item in a binary search tree,
returning true if the item is found,
and false otherwise.
One should be iterative;
the other should be recursive:
Write a function that will free
all the memory associated with a tree:
voidbtree_drop(btree_node*tree);
btree_insert
Write a function that
inserts an item into a binary search tree,
maintaining the search-tree property.
It should return the new root of the tree.
btree_node*btree_insert(btree_node*root,Itemit);
btree_traverse, with function pointers
Consider a function btree_traverse
that traverses a binary tree,
taking a function pointer.
What would its prototype be?
How would you call the function?