This set contains practice questions on hashing, disjoint set structures and graphs.
| Question 1 | Disjoint sets. Consider an ADT "disjoint set" in which the elements are the integers from 1 through n, and the operations are makeset, findset, union, and report, where "report" returns all members in a set. If we wish the operations to take O(1), O(log n), O(log n) and O(k+1) worst-case time respectively, where k is the number of elements reported, what data structure would you suggest? |
| Question 2 | Disjoint sets, graphs. We are given an array with n entries that are supposed to be links to parents in a forest of parentpointer trees. Write an algorithm that checks in O(n) worst-case time whether these pointers indeed define a true forest of parentpointer trees. Hint: look at this as a directed graph problem. |
| Question 3 | Hashing. Explain how you could implement a data structure based on hash tables for dealing with queries in a text file of the nature: find the first occurrence of a given 4-letter word, or find all occurrences of a given 4-letter word. The text file has 10 million characters. Each character has 8 bits and thus has a numerical value between 0 and 255. Please provide specifics, including the size of a hash table, and the kind of hash function used. Note: we are not interested in k-letter words with k not equal to 4. |
| Question 4 | Hashing. Tough theoretical question: suppose I have n elements and a very good hash function. I have a hash table with m=n^(1.5) double slots, that is, each hash table slot can hold two data points. We perform insert and search in the obvious manner, checking both slots if necessary, but we do not implement any collision resolution as in open addressing. Instead, we have an overflow linked list for those elements that do not fit. This list accepts all overflow elements, regardless of where they come from. Clearly, one must search the overflow list after having inspected a slot. Show that the expected unsuccessful search time is O(1). In other words, show that the expected number of elements in the overflow list is O(1). (Don't feel too bad if you can't get this one.) |
| Question 5 | Graph traversals. A star graph is a connected undirected graph with a core node and any number of arms of arbitrary length emanating from the core node. A graph G is given to you in adjacency list format, with nodes numbered 1 through n. Give an algorithm that determines in O(n) time whether the given graph is a star graph (note: you do not know which node is the core, and the number of edges, e, may be much larger than n). |
Copyright © 1999 Luc Devroye. Email: luc@cs.mcgill.ca.