CSE326/Winter 96

Midterm Solutions:

1) a) Stack
   b) Queue
   c) Stack
   d) Queue
   e) Linked List

2) a) False.  Counterexample:  f(n)=n^3, c=2
   b) True
   c) False.  Can use AVL trees.

3)     5          4               4
      /          / \             / \
     4    ==>>  3   5    ==>>   2   5
    /          /               / \
   3          2               1   3 
             /
            1

4) Open Hashing wastes space by storing pointers as well as data.
Also, Open Hashing operations may be slow, especially those involving
memory allocation.

5) AVL trees guarantees O(log n) cost per operation, while Splay trees
only guarantee O(log n) amortized cost per operation.

6) If x^2(mod 7) equals zero, then collisions will lead to an infinite
loop.

7) All are O(n) because we may need to scan the entire table in order
to find an empty spot (for INSERT) or the specified element (for
DELETE and FIND).

8) Let d be the depth of the tree.
   Total number of nodes is 2^(d+1) - 1 of which 2^d are leaf nodes
and 2^d - 1 are non-leaf internal nodes.  Hence the ratio between
number of internal nodes and number of leaf nodes is 1 - (1/(2^d))
which is almost 1 for large d.

9) Open Hashing      -- requires lots of extra memory
   Linear Probing    -- primary clustering
   Quadratic Probing -- may fail on tables which are not full
   Double Hashing    -- requires calculation of a second hash function

10) The most confusing aspect of this question was getting your
variables right.  First, you need to differentiate the size of the set
from the range of the set.  You also need to realize that Find, Insert
and Delete all operate on one set, whereas Union and Intersection
operate on two sets.  Below let n represent the largest integer you
can have, let m represent the size of the set for Find, Insert, and
Delete, and let m1,m2 represent the sizes of the sets for Union and
Intersection.

Find, Insert and Delete all take O(m) time for a sorted linked list,
and O(log m) time for an AVL tree.  Union and Intersection can be done
in O(m1+m2) for a sorted linked list using a merge-like algorithm.  I
didn't give credit for O(m1 m2) because we have gone over this
algorithm many times in section and in the homeworks and everyone
should be familiar with it by now.  Union and Intersection can be done
in O(m1 log m2) for AVL trees.  There are actually lots of ways to do
this, and I accepted all reasonable answers here.

The mystery data structure can be an array where A[i] is 1 iff i is in
the set.  If you want to save space, you notice that you use only one
bit in each element, thus you can use a bit vector instead.  Another
reasonable answer is to use a hash table, which still yields constant
time operations for reasonable loads.  Union and Intersection are both
O(n) where n is the size of the array, bit vector or hash table.  Note
that the cost here depends on the range of allowable integers (or size
of hash table) and not on the number of integers in the set, because
there is no quick and easy way to iterate over a hash table.

I tried to be lenient when grading this even if you didn't get your
variables exactly right as long as you were consistent and your
reasoning made sense (i.e. if you put in O(n) for find on a sorted
linked list, I assumed that n is the length of the list).  However, I
wasn't as lenient on people who represented the cost of Union or
Intersection as a function of only one variable.


EXTRA CREDIT:

function level-order (Tree T)
begin
    for i = 0 to height(T)
        print-nodes-at-depth (T, i);
end


function print-nodes-at-depth (Tree T, int depth)
begin
    if (depth == 0)
        print(T->data);
    else
        print-nodes-at-depth (T->left,  depth-1);
        print-nodes-at-depth (T->right, depth-1);
end


This takes O(log n) space because the size of the stack never exceeds
the height of the tree.  It takes O(n) time to run (not O(n log n) as
some people thought) because most of the calls to print-nodes-at-depth
only visit a small part of the tree (kinda like the argument for the
linear run-time of Build Heap).

I didn't give any credit for solutions that took linear space, and was
very harsh on all other solutions too (because this is extra credit).
Very few people had the right idea, and nobody had the run-time
analysis right, so don't feel bad if you didn't get it...  This really
is a difficult exam question.