==============================================================================
     CSC 263                 Tutorial 5              Winter 2019
==============================================================================


 1. Describe how to use a hash table (or a direct-address table) to solve each
    of the following problems. Provide as much detail as possible about the
    hash table (size, hash function if possible) and analyse the complexity of
    your solution. Then, answer the following questions: Is a hash table the
    best way to solve the problem? Why or why not?

    (a) Given an unsorted list of the names of every student in a class (with
        n students), determine if two of them have the same names.

    (b) Given an unsorted list of the names of every student in a class (with
        n students), return the list of names in sorted order.
        Does a hash table even make sense in this situation? Discuss.


 2. Recall the high-level implementation of each of the dictionary operations
    for a hash table using chaining (covered in last week's lecture):

        SEARCH(k):
            search the linked list at T[h(k)] for k

        INSERT(x):
            search the linked list at T[h(x.key)] for x.key
            if found:
                replace old element with x
            else:
                insert x in a new node at the head of the linked list

        DELETE(x):
            search the linked list at T[h(x.key)] for x.key
            if found:
                remove the node with x from the linked list

    In this question, you will explore "open addressing": hashing into a table
    where every element is stored directly in the table (without using linked
    lists at each location).

    To insert into a hash table using open addressing, we examine ("probe")
    different locations until we find one that is unused. The sequence of
    locations examined is called a "probe sequence". Technically, the hash
    function is redefined to take as input both a key and a "probe number":
    h(k,i) gives the location to examine for key k and probe number i.
      - For "linear probing," define h(k,i) = (h'(k) + i) mod m, where
        h'(k) is an ordinary hash function.
      - For "quadratic probing," define h(k,i) = (h'(k) + i^2) mod m, where
        h'(k) is an ordinary hash function. It's also possible to
        define a more general quadratic form but we will not study this.
      - For "double hashing," define h(k,i) = (h'(k) + i h''(k)) mod m, where
        h'(k) and h''(k) are two different hash functions such that h''(k) is
        guaranteed to always be positive and relatively prime with m.

    (a) Insert the keys 10, 22, 31, 4, 15, 28, 17, 88, 39 into a hash table
        of size m = 11 using open addressing with the primary hash function
        h'(k) = k mod m. Illustrate the results for linear probing, quadratic
        probing, and double hashing with h''(k) = 1 + (k mod (m-1)).

    (b) Write a detailed algorithm for INSERT for a hash table using open
        addressing, in pseudocode. You may use h(k,i) for your hash function
        without worrying about how it is implemented.

    (c) Write a detailed algorithm for SEARCH for a hash table using open
        addressing, in pseudocode. You may use h(k,i) for your hash function
        without worrying about how it is implemented.

   (d) Think about how to write DELETE for a hash table using open
       addressing. Why can we not simply replace the element with NIL once we
       find it? What could we do instead and how does this affect INSERT and
       SEARCH? Discuss various options.