Exercises - Review C

  1. A heap of $120$ elements is represented as an array whose value at index $0$ is null. Answer the following questions:

    1. Find the index of the parent of the element at index $23$.
    2. Of the 4 grandchildren of the element at index $20$, what is the index of the left-most one?
    3. How many children does the element at index $60$ have?
    4. If the value at index $0$ was not null but we still wanted to treat the array as a heap (such as we do in heapsort), at what index would the left child of the element at index $13$ now be?

    1. 11
    2. 80
    3. 1
    4. 27

  2. During heap insertion, which action(s) may be needed to correct heap order -- a "sink", a "swim", both, or neither?

    The element inserted (as the last non-null element in the array) may need to "swim" to a higher/smaller-indexed position in the tree/array to accomplish correct heap order.

  3. Can the below tree serve as a heap? Explain your answer.

    No. The tree is not "complete" given that $M$ has no children, but $N$ does.

  4. The heapsort algorithm is applied to the array {'O','N','P','I','L','E','S'} in order to sort the characters contained therein alphabetically. Show the state of the array after each sink (or exchange-and-sink) applied. 

    Order before heapsort application:
O  N  P  I  L  E  S  

0  1  2  3  4  5  6  
---------------------
O  N  S  I  L  E  P  
S  N  P  I  L  E  O  
P  N  O  I  L  E  S  
O  N  E  I  L  P  S  
N  L  E  I  O  P  S  
L  I  E  N  O  P  S  
I  E  L  N  O  P  S  
E  I  L  N  O  P  S  

Order after heapsort application:
E  I  L  N  O  P  S

  5. Complete the rotateLeft() method shown by filling in each blank below with a single statement, so that rotateLeft() can be used (in combination with appropriate other methods) to insert elements into a red-black tree: 

    private Node rotateLeft(Node h) {
  Node x = h.right;
  h.right = x.left;
  
  ______________________;
  
  ______________________;
  h.color = RED;
  x.size = h.size;
  h.size = 1 + size(h.left) + size(h.right);
  return x;
}


    x.left = h;
x.color = h.color;

  6. Trace the state of an initially empty red-black tree as keys 'D', 'W', 'A', 'T', 'R', 'Z', and 'Y' are added to it in that order. That is to say, draw the tree after each letter has been added. Use a double-line to indicate a "red" link and a single line for "black" links. (Unimportant, but fun fact: Dwa-Trzy means "2-3" in Polish!

    inserting D:
   
 | 
-D 


inserting W:
      
    | 
 +==W 
 ‖    
-D    


inserting A:
         
    |    
 +--D--+ 
 |     | 
-A    -W 


inserting T:
            
    |       
 +--D-----+ 
 |        | 
-A     +==W 
       ‖    
      -T    


inserting R:
               
          |    
    +=====T--+ 
    ‖        | 
 +--D--+    -W 
 |     |       
-A    -R       


inserting Z:
                  
          |       
    +=====T-----+ 
    ‖           | 
 +--D--+     +==Z 
 |     |     ‖    
-A    -R    -W    


inserting Y:
                     
          |          
    +-----T-----+    
    |           |    
 +--D--+     +--Y--+ 
 |     |     |     | 
-A    -R    -W    -Z

  7. Interpret the following as a red-black tree (double lines indicate "red" links, and single lines indicate "black" links). Draw the related 2-3 tree.

  8. Recalling that x.hashCode() returns a 32-bit integer, what is the purpose of the "x.hashCode() & 0x7fffffff" in the below hash() method? 

    private int hash(Key x) {
   return (x.hashCode() & 0x7fffffff) % M;
}

    It forces the leading bit of the hash code produced to be 0, thus producing a positive integer.

  9. You may find the following table of ASCII values, a calculator, and the largest positive int value of $2147483647$ helpful as you answer this question: $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c} A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline 65&66&67&68&69&70&71&72&73&74&75&76&77\\\hline\hline N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline 78&79&80&81&82&83&84&85&86&87&88&89&90 \end{array}$$ The strings "SUP", "ERC", "ALI", "FRA", and "GIL" have been added to an initially empty hash table of size $16$ that uses linear probing to resolve collisions and resizes by doubling in size before insertions when half full. The result is shown below: $${\small \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\\hline -- & -- & -- & -- & -- & \texttt{FRA} & \texttt{ERC} & -- & -- & -- & \texttt{GIL} & -- & -- & -- & \texttt{ALI} & \texttt{SUP}\\\hline\\\\ \end{array}}$$

    1. Find the value of "IST".hashCode().
    2. At what index should "IST" appear in the array if it is added next?
    3. If "FRA" is then deleted from the hash table, how many strings must be re-hashed?
    4. Consider the sequence of strings "A", "AB", "ABC", "ABCD", ..., and so on. Which is the first such string to have a negative hash code?

    1. $72810$
    2. $11$
    3. $1$ (just "ERC")
    4. "ABCDEFG" (with hashcode equal to $-488308668$)

  10. In an initially empty hash table of size $4$ that uses separate chaining to resolve collisions (and never resizes), the keys {'F', 'O', 'U', 'R', 'C', 'H', 'A', 'I', 'N', 'S'} are added. The respective values of hashCode() are given below: $$\begin{array}{c|c|c|c|c|c|c|c|c|c} F & O & U & R & C & H & A & I & N & S\\\hline 70 & 79 & 85 & 82 & 67 & 72 & 65 & 73 & 78 & 83 \end{array}$$ Show the resulting hash table that results. (Note, draw the chains so they run horizontally with their "head" being the left-most element.) 

    0 : H
1 : I->A->U
2 : N->R->F
3 : S->C->O

  11. Which of the following are good things to do when overriding the hashCode() method of a class (indicate all that apply)?

    One should...

    1. use every non-null instance variable's value/state in the calculation of the hash code
    2. use Horner's method to calculate the contributing value of an array
    3. avoid generating hash codes that on average have more bits of 1 than bits of 0
    4. use the hashCode() methods of the instance variables of that class to build the return value for the hashCode() method being written

    All of these are good things to do in this context.

  12. Hash tables and red-black trees are often used as symbol tables (i.e., "dictionaries"). Should the keys for any symbol table be mutable or immutable? Explain.

    Keys of a symbol table (i.e., "dictionary") should always be immutable. If this were not the case, a key might change its value after being inserted into table -- which depending on the implementation of the symbol table can cause significant problems. For example, if the symbol table was implemented with a binary search tree, the tree might no longer be in symmetric order. As another example, changing the key associated with a value would invariably change the hash code to find the value in a hash table.

  13. Given the following adjacency list, draw the graph so described, and then give the edges of the breadth-first paths tree found with source 0, in the order they are added to the tree. Finally, give the shortest path, as found by the breadth-first traversal in question between 0 and 6.

    7 vertices, 10 edges
0: 5 1
1: 4 0
2: 5 6 4 3
3: 5 2
4: 6 2 1 5
5: 0 2 3 4
6: 4 2


    Edges of Breadth-first Paths Tree:
0-5
0-1
5-2
5-3
5-4
2-6

Shortest path between vertices 0 and 6:
0-5-2-6

  14. Given the following adjacency list, draw the graph so described, and then give the edges of the depth-first paths tree found with source 0, in the order they are added to the tree.

    7 vertices, 10 edges
0: 2 1 4
1: 0 5 3
2: 0 6 4
3: 1 4
4: 0 6 2 3
5: 6 1
6: 5 2 4


    Edges of Depth-first Paths Tree:
0-2
2-6
6-5
5-1
1-3
3-4