Answers to written HW#3

Disclaimer: even if it looks like C++ code, it is supposed to be pseudo-code. I haven't compiled/run any of the below code, although I believe it to be correct modulo some possible typos. --Ami.

Chapter 11

Self-Test Exercises

Does the array:
|----------------------------------------| | 5 | 1 | 2 | 8 | 6 | 10 | 3 | 9 | 4 | 7 | |----------------------------------------|
represent a heap?
The array represents the following tree:

         __5__ 
        /     \
       /       \
      1         2
    /  \       / \
   /    \     /   \
  8      6   10    3
 / \    /
9   4  7

which is clearly not a heap.

Is the tree in figure 10-34 a heap or a semi-heap?
It is neither, as no non-leaf node is bigger than both its children.

Consider:
|-----------------------| |10 | 9 | 6 | 3 | 2 | 5 | |-----------------------|
Insert and remove 12. What heap results?
Insert(12) yields:

|----------------------------|
|12 | 9 | 10 | 3 | 2 | 5 | 6 |
|----------------------------|

Delete(12) yields:

|------------------------|
| 10 | 9 | 6 | 3 | 2 | 5 |
|------------------------|

(i.e., the same thing we started with).

The final array is: [6,4,5,1,2,3]
The final array is: [7,5,6,4,3,2]
The final array is: [10,9,5,8,7,2,3,1,4,6]

Exercises

A hash table would be best

Suppose not. Then there is some internal node that has value larger than any other. In particular, the node has a value larger than its parent, thus showing that this can't be a heap. The reason the root can have the largest value is that it has no parent.
Yes, since children are inserted left to right.
One possibility is to maintain a heap of *pointers* to objects, and subsequently swap pointers instead of actual objects. Another is to keep track of all the swaps that would have to be made and do them all at once at the end, but not in the form of swaps (a round-robin style).
The order is undetermined. To see this, consider a trivial example where you insert the value 3 twice into an initially empty heap. The first 3 will become the root, and the second 3 will be made a child of the root, and no trickling will occur, because the second 3 is not strictly greater than the first. Thus the first three will be the root and first to be deleted. On the other hand, if one inserts the values 7,5,6,4,4.5,4 into an initially empty heap, one gets:
```
         7
    5         6
  4a 4.5    4b
```
(where 4a is the first 4, and 4b is the second 4); and successive deletions give:
```
     6
  5    4b
4a 4.5

   ||
   || 
  \||/
   \/

       5
  4.5     4b
4a

   ||
   || 
  \||/
   \/

   4.5
 4a    4b

   ||
   || 
  \||/
   \/

   4b
 4a
```
so 4b will be popped before 4a.
If we wanted to force FIFO behaviour for equal valued priorities, we would have to attach a timing flag and consider both the keys *and* the timing flags when two keys are equal to decide which is greater.

Find it, change its value, and percolate it.

Chapter 12

Self-Test Exercies

T.TableDelete(SearchKey)  
    I=hash(SearchKey)
    while (T[I] occupied and T[I].Key != SearchKey) or (T[I] deleted)
        I++;
    
    if (T[I] not empty)
        Mark T[I] deleted

8,10,1,3,5,7,9,0,2,4,6

The final table looks like:

 |----|
0|    |-->NULL
 |----|
1|    |-->[15]-->[8]
 |----|
2|    |-->NULL
 |----|
3|    |-->[17]-->[24]-->[10]
 |----|
4|    |-->[32]
 |----| 
5|    |-->NULL
 |----| 
6|    |-->NULL
 |----|

Exercises

T.TableInsert(Key) 
    I=hash(Key)
    while (T[I] occupied) ++I;
    T[I]=Key;

T.TableRetrieve
    I=hash(Key)
    while (T[I] occupied) and (T[I]!=Key) 
        ++I;
    if (T[I]==Key) return true;
    return false;

T.Table Delete -- see STE #7.

T.TableDelete(SearchKey)  
    I=hash(SearchKey)

    return T[I]->remove(Key);

1. No good, because changing the order of the letters in the key doesn't change the hash value.
2. Even worse, because only 26 hash slots will actually be used (only 26 letters in the alphabet). If the keys are english words, this is even worse, because some letters begin a lot more words than others.
3. Wasteful and misleading. First, we are allocating a hash slot for every possible value, so no need for hashing. Second, the RNG only produces values less than one, meaning that the slots with low indices will be used more than the slots with high indices.
4. Misleading and expensive. It can be shown that if 0<=X<=M, then (X^N) mod M == X^(N mod (M-1)). But this function computes: HashIndex(X)==X^(2^1,000,000) mod 9999 == X^(2^1000000 mod 9998) == X^(2^(1000000 mod 9997)) == X^(2^300 mod 9998) = X^4612 mod 9999. While 4612 and 9999 are relatively prime, and so this is an acceptible hash function in terms of spreading the values around, it will take a long time to compute, and moreover, is unnecessary since all of the space is already allocated.