22C:30, 22C:115 Homework 4

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

1. for(int i = 0; i < n; i++)
   	for(int j = n; j > i; j--)
   		cout << i*j << endl;
   

2. for(int i = 0; i < n; i++)
   	for(int j = 0; j < n*i; j++)
   		cout << i*j << endl;
   

3. 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)

Problem 4

1. Insert the following elements in the given order into an empty AVL tree. Show the AVL tree that results after each insertion. Indicate whether a single or a double rotation was neeeded to "fix" the AVL and restore balance to it after each insertion setp.

   10 200 5 18 70 150 50 20
   

2. Start with the AVL tree on page 432, Figure 9.11(b) and delete the element 88 from it. Show precisely how balance is restored to this tree. In other words, what operations are needed to make sure that this tree becomes an AVL tree again.

Problem 5

1. Draw all valid binary min-heaps containing the elements 1, 2, 3, 4, 5.

2. Your friend claims that outputting the elements of a min-heap by doing a pre-order traversal on it, will always produce a sorted sequence. Disprove your friend by showing a binary heap and the pre-order traversal of this heap that gives a non-sorted sequence. Also, show a min-heap with 10 elements whose pre-order traversal is indeed a sorted sequence, thus showing that your friend may be occasionally correct.

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.