Problem 1
Analyze the worst case running times of the following code fragments and
express your answer as a function of n in the "Big-Oh" notation.
Show all the work that went into getting your answers
for(int i = 0; i < n; i++) for(int j = n; j > i; j--) cout << i*j << endl;
for(int i = 0; i < n; i++) for(int j = 0; j < n*i; j++) cout << i*j << endl;
for(int i = 1; i <= n; i=2*i) for(int j = 1; j <= n; j=2*j) cout << i*j << endl;
Problem 2
Express the worst case running time of this function, as a function of n in
"Big Oh" notation. Make a small modification to this function
to obtain an equivalent function (that is, a function that produces the same
answers) but is much faster.
Express the worst case running time of this faster function, as a function of
n in "Big Oh" notation.
int foo(int n){ if(n == 0) return 1; else{ return foo(n-1) + foo(n-1); } }
Problem 3
Write a recursive function that takes as input a pointer to
the root of a binary search tree
and determines if the tree is an AVL tree or not.
You should not assume that heights of nodes are stored at the nodes
and therefore the calculation of heights of nodes has to be part of
your function.
Use the following function header:
bool isAVL(bstNode * root, int & height)The function returns a boolean value to indicate if the tree is AVL or not; but in addition it also returns the height of the root of the tree.
Problem 4
10 200 5 18 70 150 50 20
Problem 5
Problem 6
Consider the binary heap shown on page 331, Figure 7.3.
Show all the steps of the algorithm that replaces the item 5 in this heap with 18.