Due 4/28/00 in class
1. Given the following input array (assume the array starts at index 1)
35, 12, 40, 17, 9, 83, 2, 6, 66, 41, 5, 36
a) Perform the BuildHeap operation as described in the book to turn this array into a heap. Show the resulting array.
b) How many comparisons did part a take? Show the sequence of comparisons that were performed when processing the element at index 1.
c) Insert the element 1 into the heap you built in part a. Show the final result, either in array or tree form.
2. a) Insert the following elements in order into an empty binomial queue. Show the final result.
41, 30, 80, 81, 75, 3, 8
b) Show the result of performing a DeleteMin on the following binomial queue.
c) Perform a second DeleteMin on the result of part b. Show the result.
3. a) What is the maximum number of leaf nodes that can be stored in a B-tree of depth 2, order M=6? (Recall that a tree with just a root node is depth 0.)
b) What is the minimum?
c) Delete 59 from the B-tree below. Show the result.
d) If you were to delete 21 from the B-tree above, would you need to make any changes to the root node? If so, what is the change and why is it necessary? If not, why not?
4. Consider the following function, which takes as input an array of size n, and starting and ending positions of the subarray to be processed. The initial call would be "func1(array, 0, N)", for example. A call "func1(array, 30, 40)" would process a 10 element subarray.
int func1(int *array, int start, int end)
size = end - start;
if (size < 3) return 22;
x = func1(array, start, start + size/3);
y = func1(array, start + size/3, start + 2*size/3);
z = func1(array, start + 2*size/3, end);
// for (i = start; i < end; i++)
// x = x + array[i];
return x + y + z;
a) Write the recurrence relation for func1 as a function of N, assuming the initial call is func1(array, 0, N). You do not need to solve the recurrence.
b) Write the recurrence relation for func1 if the two commented lines are uncommented.
int func2(int *array, int start, int end)
size = end - start;
if (size < 1) return 33;
else return 1 + func2(array, start + size/3, start +
2*size/3);
c) Write the recurrence relation for func2.
d) What is the asymptotic running time of func2 as a function of the initial size N? Briefly show your work.
5. Suppose that we choose the pivot for quicksort by taking the middle element (rounding down if there are an even number of elements).
a) What is the asymptotic running time if the input is sorted in ascending order? Explain why.
b) Construct a worst-case input of size 8 containing the elements 1 through 8. Show the resulting array after each partitioning step. Assume that the recursion's base case is an array of size 1.
6. Programming Section. To get a better feel for the relative expense of sorting algorithms, we are going to modify the base code from Weiss to track some simple statistics. This is known as instrumenting a program. One technique is to use functions from the C library to measure elapsed clock time. This technique is sensitive to machine differences, and can be thrown off by caching and other external factors if care is not taken. We will take a different approach and measure the number of operations required.
The BaseWeissSort2.cpp file contains the code from the book for sorting. Your task is to modify the code to track operations in four categories: comparisons, assignments, non-trivial math, and function calls. Declare four global variables (e.g. cc, ca, cm, cf). Before each sort, reset the counts to zero. After each sort, print the total and the individual values. In reality, each of these would have a different cost and be weighted differently--we will compute the total as if they all cost the same.
Comparisons: increment before every if statement, and at the top of
every for or while loop.
Assignments: increment after every assignment statement.
Math: increment after any computation more complex than increment,
decrement, or a multiply or divide by 2.
Functions: increment after any function call. Don't count calls to Swap
or LeftChild, as the compiler should simplify those small functions into inline
code.
This should not take more than an hour or so if you are careful not to introduce bugs. To run the program, do the following:
A few files are provided: a4_20.txt, a4_100.txt, a4_10000.txt, a4_50000.txt, a4_100000.txt. Those last two are about 1.5 megabytes total. If you know how to handle zip files, you can save some download time by getting a4input.zip, which has all the files and is only 500K.
For this problem, there is no online turnin. Submit a printout of your code, stapled to the rest of the assignment. Also, turn in a sheet of paper with statistics. Make a table with columns labeled N, N log N, N^2, Insert, Shell, Heap, Merge, Quick. In the first column, put the numbers 20, 100, 10000, 50000, and 100000. Calculate the second and third columns yourself. In the remaining columns, give the total amount of work that you computed for each sort, as well as the breakdown (compare/assign/math/function).
For each N, circle the best sort. It's ok to skip insertion sort on 100,000 inputs, unless you're feeling masochistic. You'll probably get integer overflows on the counts anyway.
For fun, try making some different input files to see how badly you can make the sorts perform. You might also tweak quicksort to use the first element as pivot (the code uses median-of-three), and see how it performs relative to the others on a random file and on a sorted file. If you try other inputs, go ahead and add rows to the table you turn in.
The TAs reserve the right to ask you to submit your code online, so don't throw it away after you turn in your assignment.