CS203 FINAL

FINAL
CS203, Spring 2006

Please upload your source code and other files using CSNS at the end of the exam. Note that file uploading will be disabled automatically after 4:00PM, so please turn in your work on time. Before turn in your programs, try to compile and run them and make sure they work correctly. If your program does not even compile, you receive an automatic 50% credit deduction for that problem, no matter how "close" the program seems to be correct.

[Q&A] For the following questions, please put your answers in a text file final.txt or an MS Word file final.doc. For questions that could have multiple correct answers, giving one of the correct answers is enough.

1. (10pt) Suppose we use an array to implement a MaxHeap, and we insert the following numbers into the heap: 20, 31, 15, 21, 25, 12, 35, 14, 19, 30. Show the content of the array after we call removeMax five times.

2. (10pt) Suppose we use an array to implement a hash table for positive integers. The hash function is defined as the input value modulo the size of the array, and linear probing is used for collision resolution. For an array of size 7, show the content of the array after the following operations

insert(21), insert(25), insert(33), insert(11), remove(25), insert(32), insert(46)

You do not have to show intermediate results - just the content of the array after all the operations are performed.

3. (10pt) Give the average-case and worst-case complexities of the following sorting algorithms:

Bubble Sort
Heap Sort
Quick Sort

[Programming]

4. (15pt) Write a method boolean validateMinHeap(int a[]) which validates whether a given array is a MinHeap, or in other words, checks whether each node is smaller than its child node(s). The complexity of the method must be linear or better; otherwise you will not receive any credit. Test your method with the following two arrays: {10, 23, 18, 25, 30, 19} and {10, 23, 18, 25, 19, 30}. The method should return true for the first array and false for the second one. Note that here we assume a heap starts from array index 0.

5. (25pt) Write a method int median(int a[], int b[]) which returns the median of a[] union b[], assuming that both a[] and b[] are sorted in ascending order. The complexity of the method must be linear or better, and you may only use constant extra space (i.e. you cannot merge a[] and b[] into a temporary array); otherwise you will not receive any credit. Test your method with the following two cases:

a[] = {10, 20, 30} and b[] = {50, 60, 70, 80, 90}. The median of a[] union b[] should be 55, i.e. (50+60)/2..
a[] = {10, 20, 30, 40} and b[] = {15, 25, 35, 45, 55}. The median of a[] union b[] should be 30.

Note that median is the "middle value" in a set of values, i.e. half of the values in the set is greater than the median and the other half are less than the median. More specifically, if we sort the values, median is the value in the middle if there are odd number of values, or if there are even number of values, median is the average of the two middle values. For example, the median of {2, 1, 3} is 2, and the median of {2, 1, 3, 4} is 2.5, i.e. the average of 2 and 3.

6. Consider a Binary Search Tree implementation that uses lazy delete. Lazy delete means that when we remove an object from the tree, instead of actually removing the node that holds the object, we simply set an isDeleted flag in the node to indicate that the object has be removed. This of course greatly simplifies the remove operation, since we no longer need to restructure the tree; however, other operations may not as simple as before. For this problem, you must complete the given BSTree class by implementing the following methods:

(10pt) private BSTreeNode find(Comparable o) - finds the node that holds the given object.
(10pt) public void insert(Comparable o) - inserts an object into the tree.
(10pt) public void print() - outputs the objects in the tree in pre-order.
(+20pt extra credit) Comparable min() - returns the smallest object in the tree.

You may add more methods to the BSTree class if necessary, however, you may not add or remove any class variables, and you may not change the BSTreeNode class in any way.