Week 10 Tutorial Questions

Hashing, Heaps and Tries

Resources

Hashing
Heaps
Tries

Questions

    Hashing

  1. Hash tables are initially empty (i.e. contain no items). This fact is represented in the table by each entry having a value of NoItem.

    Suggest suitable NoItem values if Items are stored in the table elements and

    1. keys are unsigned ints
    2. keys are ints
    3. keys are strings

    How would things be different if table entries were pointers to Items (i.e. (Item *))?

  2. For a hash table of size \( N \) that uses separate chaining for collision resolution, with the chains sorted in ascending order on key value, what are the best case and worst case costs for inserting \( k = 2N \) items into the table? Assume that insertion cost is measured in terms of number of key comparisons. What will be average search cost after all the insertions are done?

  3. Consider a very small hash table with only 11 entries, and a simple hash function \( h(x) = x\ \%\ 11 \). If we start with an empty table and insert the following values in the order shown

    11  16  27  35  22  20  15  24  29  19  13

    give the final state of the table for each of the following collision resolution strategies

    1. separate chaining, with chains in ascending order
    2. linear probing
    3. double hashing, with \( h_2(x) = (x\ \%\ 3) + 1 \)

  4. Consider a hash table of size \( N = 10 \) with hash function \( h(k) = k\ \% \ 10 \) that handles collisions via linear probing. Show the result of inserting items with these keys into an initially empty table.

    1. 1, 2, 3, 4, 5, 6, 7, 8
    2. 15, 6, 20, 3, 17, 14, 33, 5, 10, 7

  5. Consider this potential hash function:

    int hash(char *key, int N) {
	int h = 0;
	char *c;
	for (c = key; *c != '\0'; c++) {
		h = h + *c;
	}
	return h % N;
}

    How does this function convert strings to ints?

    What are the deficiencies with this function and how can it be improved?

  6. Both hash tables and balanced search trees (e.g., AVL trees and 2-3-4 trees) are efficient data structures that can be used for the insertion, searching and deletion of key-value pairs. Compare the advantages and disadvantages of each.

    7. Heaps

  7. Using the heap-as-array ADT from lectures, show how an initially empty heap changes when the following values are inserted.

    S  O  R  T  I  N  G  I  S  F  U  N

    At each step, show how the fixUp() function is used.

  8. Consider the heap-as-array ADT given in lectures:

    typedef struct HeapRep {
	Item *items;   // array of Items
	int   nitems;  // #items in array
	int   nslots;  // #elements in array
} HeapRep;

typedef HeapRep *Heap;

    If a heap is created to hold up to 10 Items, and Items are integer values, and higher values have higher priority, show the state of the heap after each of the following operations:

    Heap h;
Item it;
h = newHeap(10);

insert(h, 10);
insert(h,  5);
insert(h, 15);
insert(h , 3);
insert(h, 16);
insert(h, 13);
insert(h,  6);
it = delete(h);
insert(h,  2);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);

  9. Repeat the above sequence of insertions and deletions, but this time draw the heap as a binary tree, with the highest value at the root and the values decreasing as you move down any branch.

    Reminder:

    Heap h;
Item it;
h = newHeap(10);

insert(h, 10);
insert(h,  5);
insert(h, 15);
insert(h , 3);
insert(h, 16);
insert(h, 13);
insert(h,  6);
it = delete(h);
insert(h,  2);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);

    10. Tries

  10. Consider the following trie:

    Show which nodes would be visited when searching for each of the following words:

    1. now
    2. the
    3. ant
    4. access
    5. actor
    6. action
    7. actors
    8. tang
    9. a

  11. Under what circumstances would inserting a new word into a trie not result in adding any new nodes? What would be the effect on the tree of inserting the word?

  12. Show the final trie resulting from inserting the following words into an initially empty trie.

    so   boo   jaws   boon   boot   axe   jaw   boots   sore

    Does the order that the words are inserted affect the shape of the tree?

  13. What are the two cases when deleting a word from a trie? How is each case handled?